Complexity 2

1. Given a graph G = (V , E), a set U ⊆ V of vertices is called a vertex cover

of G if, for each edge (u, v) ∈ E, either u ∈ U or v ∈ U . That is, each edge

has at least one end point in U . The decision problem V-COVER is deﬁned

as:

given a graph G = (V , E), and an integer K, does G contain a

vertex cover with K or fewer elements?

(a) Show a polynomial time reduction from IND to V-COVER.

(b) Use (a) to argue that V-COVER is NP-complete.

(a) Give a polynomial time reduction from the Hamiltonian cycle problem to HamPath.

(b) Give a polynomial time reduction from HamPath to the problem of determining whether a graph has a Hamiltonian cycle.

Hint: consider adding a vertex to the graph.

(From suggested exercises 2)

2007 p5q12, part c

2005 p5q10, part b-d

2002 p5q12

2009 p6q1