Out: Monday November 12, 2007.
Due: Monday November 26, 2007, start of class.
Solutions will be judged on correctness, clarity, quality of explanation,
readability. Please don't use other sources for your write-up. Work on the
problems and talk to me if you are having problems.
Please be very neat, preferably type.
(1):
AB 2.32
(2):
A core set in an undirected graph is a subset of vertices such that:
every vertex in the graph is either in the subset, or adjacent to a vertex
in the subset. Prove CS = { < G , k > | G has a core set of size k } is NP-complete.
(3):
Prove that P is not equal to DSPACE(n).
(Hint: assume true and use padding to get a contradiction to the space hierarchy theorem.)
(4): Approximation:
Some kinds of NP-complete problems can be approximated fairly closely in polynomial time,
but there are other similar problems which cannot be polynomial time approximated at all unless P=NP.
i
In the travelling salesman problem we are given a set
of n cities, and a n by n cost matrix C, where C(i,j) is a nonnegative
integer specifying the cost of travelling from city i to city j.
(We assume C is symmetric, so C(i,j) = C(j,i).) A tour is a trip
which starts at city 1, visits every other city exactly once and
returns to city 1. The cost of a tour is the sum of the costs for
each intercity trip. TSP = { < C, t > | there is a tour of n cities
with cost matrix C that has total cost <= t.}
(a) Show TSP is NP-complete by reduction from undirected hamilton cycle (UHC). (Hint: In reducing an n vertex graph G to an instance of TSP, use costs C(i,j) = 1 if (i,j) is an edge in G, and 2 otherwise.)
(b) Part(a) shows also that the Triangle traveling salesman problem
is NP complete, since the costs of edges all satisfy the following
triangle inequality:
For all i,j,k, C(i,j) <= C(i,k) + C(k,j).
Sketch a polynomial time approximation algorithm for the
Triangle TSP problem, which, given a cost matrix satisfying the triangle inequality, returns a tour
which costs no more than twice the cost of the minimum tour.
Hint: A minimum spanning tree costs less than the minimum tour,
and it can be adapted into a "bad" tour which costs only twice
as much using DFS. The bad tour visits every
edge of the MST twice, and it repeats some cities.
Using the triangle inequality, the tour can be modified to
get rid of repeats without increasing costs.
(c) Show in contrast that,
for the original version of TSP
(ie where costs need not satisfy the triangle inequality),
for any positive constant k, there is no
approximation algorithm which is guaranteed to find a tour with cost
less than a factor k of the minimum cost tour,
unless P = NP.
Hint: Show how to use the existence of such an algorithm
to solve UHC in polynomial time.
(5):Sipser problem 7.45
Please:
Give explanations and correctness arguments for all algorithms.
Take time to prepare clear and convincing proofs.
Clearly label and display your answer to each problem, starting on a separate page for each.
Don't use outside sources in your proofs.
List collaborators, and write up all solutions on your own.
Reminder: No outside consultants, books or online resources allowed.