Application of Computer Graphics

Tutorial Exercise (NP-Completeness) CS3381 Design and Analysis of Algorithms

Helena Wong, 2001

1. State whether each of the followings is true or false.

a.  If a decision problem is easy, then the related optimization problem (if any) is easy as well.

b.  Given a problem Q and CIRCUIT-SAT £P Q. Every problem P in NP are also polynomial-time reducible to Q.

2. What is meant by a “Tractable” problem?

3. What are the features of a verification algorithm?

4. Define the undirected hamiltonian cycle problem (UHC) as:

For a given undirected graph, decide whether there is a simple cycle containing each vertex of the graph.

Define the directed hamiltonian cycle problem (DHC) as:

For a given directed graph, decide whether there is a simple cycle containing each vertex of the graph.

Given that the DHC problem is NP-complete. Prove the UHC problem is NP-complete.

Hint: For a directed graph G, create a corresponding undirected graph G’ :

Step 1. Start with an empty undirected graph G’.

Step 2. For each vertex vi in G, create the followings in G’: 3 vertices: vi,a, vi,b, and vi,c, two edges: (vi,a, vi,b) and (vi,b, vi,c)

Step 3. For each directed edge (vi,vj) in G, create a corresponding undirected edge (vi,c,vj,a) in G’

Invent an example and draw it. Observe what you get.