The Hamiltonian-cycle Problem

Next, we show that the size of G' is polynomial in the size of G, and hence we can construct G' in time polynomial in the size of G. The vertices of G' are those in the widgets, plus the selector vertices. Each widget contains 12 vertices, and there are k ≤ |V| selector vertices, for a total of

vertices. The edges of G' are those in the widgets, those that go between widgets, and those connecting selector vertices to widgets. There are 14 edges in each widget, or 14 |E| in all widgets. For each vertex u ∈ V, there are degree(u) - 1 edges between widgets, so that summed over all vertices in V, there are

edges between widgets. Finally, there are two edges for each pair consisting of a selector vertex and a vertex of V, or 2k |V| such edges. The total number of edges of G' is therefore

Now we show that the transformation from graph G to G' is a reduction. That is, we must show that G has a vertex cover of size k if and only if G' has a hamiltonian cycle.

Suppose that G = (V, E) has a vertex cover V* ⊆ V of size k. Let V* = {u₁, u₂,..., u_k}. As Figure 34.17 shows, we form a hamiltonian cycle in G by including the following edges for each vertex u_j ∈ V*. Include edges degree(u_j), which connect all widgets corresponding to edges incident on u_j. We also include the edges within these widgets as Figures 34.16(b)-(d) show, depending on whether the edge is covered by one or two vertices in V*. The hamiltonian cycle also includes the edges

By inspecting Figure 34.17, the reader can verify that these edges form a cycle. The cycle starts at s₁, visits all widgets corresponding to edges incident on u₁, then visits s₂, visits all widgets corresponding to edges incident on u₂, and so on, until it returns to s₁. Each widget is visited either once or twice, depending on whether one or two vertices of V* cover its corresponding edge. Because V* is a vertex cover for G, each edge in E is incident on some vertex in V*, and so the cycle visits each vertex in each widget of G'. Because the cycle also visits every selector vertex, it is hamiltonian.

Conversely, suppose that G' = (V', E') has a hamiltonian cycle C ⊆ E'. We claim that the set

is a vertex cover for G. To see why, partition C into maximal paths that start at some selector vertex s_i, traverse an edge (s_i, [u, u⁽¹⁾, 1]) for some u ∈ V, and end at a selector vertex s_j without passing through any other selector vertex. Let us call each such path a "cover path." From how G' is constructed, each cover path must start at some s_i, take the edge (s_i, [u, u⁽¹⁾, 1]) for some vertex u ∈ V, pass through all the widgets corresponding to edges in E incident on u, and then end at some selector vertex s_j. We refer to this cover path as p_u, and by equation (34.4), we put u into V*. Each widget visited by p_u must be W_uv or W_vu for some v ∈ V. For each widget visited by p_u, its vertices are visited by either one or two cover paths. If they are visited by one cover path, then edge (u, v) ∈ E is covered in G by vertex u. If two cover paths visit the widget, then the other cover path must be p_v, which implies that v ∈ V*, and edge (u, v) ∈ E is covered by both u and v. Because each vertex in each widget is visited by some cover path, we see that each edge in E is covered by some vertex in V*.