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
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?
(From suggested exercises 2)
2007 p5q12, part c
2005 p5q10, part b-d
2002 p5q122009 p6q1