SKEDSOFT

Proof We first show that HAM-CYCLE belongs to NP. Given a graph G = (V, E), our certificate is the sequence of |V| vertices that makes up the hamiltonian cycle. The verification algorithm checks that this sequence contains each vertex in V exactly once and that with the first vertex repeated at the end, it forms a cycle in G. That is, it checks that there is an edge between each pair of consecutive vertices and between the first and last vertices. This verification can be performed in polynomial time.

We now prove that VERTEX-COVER ≤_P HAM-CYCLE, which shows that HAM-CYCLE is NP-complete. Given an undirected graph G = (V, E) and an integer k, we construct an undirected graph G' = (V', E') that has a hamiltonian cycle if and only if G has a vertex cover of size k.

Our construction is based on a widget, which is a piece of a graph that enforces certain properties. Figure 34.16(a) shows the widget we use. For each edge (u, v) ∈ E, the graph G' that we construct will contain one copy of this widget,which we denote by W_uv. We denote each vertex in W_uv by [u, v, i] or [v, u, i], where 1 ≤ i ≤ 6, so that each widget W_uv contains 12 vertices. Widget W_uv also contains the 14 edges shown in Figure 34.16(a).

Along with the internal structure of the widget, we enforce the properties we want by limiting the connections between the widget and the remainder of the graph G' that we construct. In particular, only vertices [u, v, 1], [u, v, 6], [v, u, 1], and [v, u, 6] will have edges incident from outside W_uv. Any hamiltonian cycle of G' will have to traverse the edges of W_uv in one of the three ways shown in Figures 34.16(b)-(d). If the cycle enters through vertex [u, v, 1], it must exit through vertex [u, v, 6], and it either visits all 12 of the widget's vertices (Figure 34.16(b)) or the six vertices [u, v, 1] through [u, v, 6] (Figure 34.16(c)). In the latter case, the cycle will have to reenter the widget to visit vertices [v, u, 1] through [v, u, 6]. Similarly, if the cycle enters through vertex [v, u, 1], it must exit through vertex [v, u, 6], and it either visits all 12 of the widget's vertices (Figure 34.16(d)) or the six vertices [v, u, 1] through [v, u, 6] (Figure 34.16(c)). No other paths through the widget that visit all 12 vertices are possible. In particular, it is impossible to construct two vertex-disjoint paths, one of which connects [u, v, 1] to [v, u, 6] and the other of which connects [v, u, 1] to [u, v, 6], such that the union of the two paths contain all of the widget's vertices.

The only other vertices in V' other than those of widgets are selector vertices s₁, s₂,..., s_k. We use edges incident on selector vertices in G' to select the k vertices of the cover in G.

In addition to the edges in widgets, there are two other types of edges in E', which Figure 34.17 shows. First, for each vertex u ∈ V, we add edges to join pairs of widgets in order to form a path containing all widgets corresponding to edges incident on u in G. We arbitrarily order the vertices adjacent to each vertex u ∈ V as u⁽¹⁾, u⁽²⁾,..., u^(degree(u)), where degree(u) is the number of vertices adjacent to u. We create a path in G' through all the widgets corresponding to edges incident on u by adding to E' the edges {([u, u⁽ⁱ⁾, 6], [u, u^{(i 1)}, 1]) : 1 ≤ i ≤ degree(u) - 1}. In Figure 34.17, for example, we order the vertices adjacent to w as x, y, z, and so graph G' in part (b) of the figure includes the edges ([w, x, 6], [w, y, 1]) and ([w, y, 6], [w, z, 1]). For each vertex u ∈ V, these edges in G' fill in a path containing all widgets corresponding to edges incident on u in G.

The intuition behind these edges is that if we choose a vertex u ∈ V in the vertex cover of G, we can construct a path from [u, u⁽¹⁾, 1] to [u, u^(degree(u)), 6] in G' that "covers" all widgets corresponding to edges incident on u. That is, for each of these widgets, say , the path either includes all 12 vertices (if u is in the vertex cover but u⁽ⁱ⁾ is not) or just the six vertices [u, u⁽ⁱ⁾, 1], [u, u⁽ⁱ⁾, 2],..., [u, u⁽ⁱ⁾, 6] (if both u and u⁽ⁱ⁾ are in the vertex cover).

The final type of edge in E' joins the first vertex [u, u⁽¹⁾, 1] and the last vertex [u, u^(degree(u)), 6] of each of these paths to each of the selector vertices. That is, we include the edges

			{(sj, [u, u(1), 1]) : u ∈ V and 1 ≤ j ≤ k}
                 ∪ {(sj, [u, u(degree(u)), 6]) : u ∈ V and 1 ≤ j ≤ k}.