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.

Given a graph G=(V,E),a source vertex s∈V and a target vertex t∈V, a Hamiltonian Path from s to t in G is a path that begins at s, ends at t and visits every vertex in V exactly once. We define the decision problem HamPath as: given a graph G = (V, E) and vertices s, t ∈ V , does G contain a Hamiltonian path from s to t?
(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