Java Reference
In-Depth Information
17.8 A Hamiltonian cycle in graph G is a cycle that visits every vertex in the
graph exactly once before returning to the start vertex. The problem HAMIL-
TONIAN CYCLE asks whether graph G does in fact contain a Hamiltonian
cycle. Assuming that HAMILTONIAN CYCLE is NP-complete, prove that
the decision-problem form of TRAVELING SALESMAN is NP-complete.
17.9 Use the assumption that VERTEX COVER is NP-complete to prove that K-
CLIQUE is also NP-complete by finding a polynomial time reduction from
VERTEX COVER to K-CLIQUE.
17.10 We define the problem INDEPENDENT SET as follows.
INDEPENDENT SET
Input: A graph G and an integer k.
Output: YES if there is a subset S of the vertices in G of size k or
greater such that no edge connects any two vertices in S, and NO other-
wise.
Assuming that K-CLIQUE is NP-complete, prove that INDEPENDENT
SET is NP-complete.
17.11 Define the problem PARTITION as follows:
PARTITION
Input: A collection of integers.
Output: YES if the collection can be split into two such that the sum
of the integers in each partition sums to the same amount. NO otherwise.
(a) Assuming that PARTITION is NP-complete, prove that the decision
form of BIN PACKING is NP-complete.
(b) Assuming that PARTITION is NP-complete, prove that KNAPSACK
is NP-complete.
17.12 Imagine that you have a problem P that you know is NP-complete. For
this problem you have two algorithms to solve it. For each algorithm, some
problem instances of P run in polynomial time and others run in exponen-
tial time (there are lots of heuristic-based algorithms for real NP-complete
problems with this behavior). You can't tell beforehand for any given prob-
lem instance whether it will run in polynomial or exponential time on either
algorithm. However, you do know that for every problem instance, at least
one of the two algorithms will solve it in polynomial time.
(a) What should you do?
(b) What is the running time of your solution?
