Vitaly Parnas - Hamiltonian Cycle hardness and gadgets

One of my preferred types of NP hardness proofs involves gadgets. Some publications prefer the more general terminology components, but I’ll use the former. Gadget-based proofs, with the proper gadget framework established, beyond being more visually intuitive, are quiet pleasing to work with. The term gadget also sounds less mathematically abstract. Developing the intuition to conjure such a gadget framework from scratch, however, still continues to bewilder me.

I’ll provide an example of a gadget-based proof through a classic example of the Hamiltonian Cycle problem.

Hamiltonian Cycle (HC)

A graph contains a Hamiltonian cycle when it can be traversed in such a way that each vertex is visited exactly once, with the exception of the starting/terminating vertex, hence the term cycle. The mathematical formulation follows.

Instance: A graph G=(V,E) with n vertices.

Question: Does G contain a HC, or an ordering {v₁,v₂,…,v_n} of vertices such that (v_i,v_i+1) ∈ E and (v_n,v₁) ∈ E, 1≤i≤(n-1).

We’ll also refer to the Vertex Cover problem shortly, which I’ll take a moment to introduce.

Vertex Cover (VC)

Instance: A graph G=(V,E) and a positive integer K≤|V|.

Question: Is there a vertex cover of size K or less, that is V' ⊆ V such that |V'| ≤ K and for each edge (u,v) ∈ E, one of u or v belongs to V'?

A practical scenario of the VC problem might involve different two-person groups, where the same person is allowed to occupy multiple groups. Each person is a vertex and each group is an edge. The smallest vertex cover for this graph then corresponds to the smallest delegation we can form among these group members to represent all groups.

Hamiltonian Cycle is NP-Complete

HC ∈ NP

First, we can demonstrate that HC is an NP problem since a Nondeterministic Turing Machine need but (nondeterministically) select a permutation of V and verify in polynomial time that each successive vertex follows a path in G, the path ultimately forming a cycle.

What follows is the NP Hardness proof, which, once combined with the above, proves that HC is an NP-Complete problem.

HC is NP-Hard.

Proof:

We’ll reduce the NP-Complete Vertex Cover (VC) to HC.

VC polynomially reduces to HC (VC≤_pHC)

Let G=(V,E) and K≤|V| represent an instance of VC. We’ll construct G'=(V',E') such that G' has a Hamiltonian cycle if and only if G has a vertex cover of size ≤ K.

As much as I would desire for G' to be some augmentation of G, it’s nothing of the sort. Rather, it starts with gadgets that combine a into a greater structure comprising G', which meets the above property.

Cover-testing gadget

The gadget integral to this reduction is the cover-testing gadget. We refer to it as a gadget, but really, it’s a small component of G'. We build one for every edge e=(u,v) ∈ E.

To build the gadget, we can use a more complex structure of more vertices and edges (for a more visually impressive but unnecessarily complex proof), or the simpler version consisting of but four vertices and edges. See the two varieties below.

It doesn’t matter which variety you choose, since both (and other variants not demonstrated here) meet the following properties:

We traverse each vertex exactly once throughout our full Hamiltonian Cycle.
We enter the gadget via a specific entry for either vertices u or v, and exit via the opposite, corresponding vertex.

From here on I’ll display the gadget in the following simpler form.

Connect the cover-testing gadgets

For every vertex v ∈ V, we traverse each edge incident (connected) to v in any arbitrary order, and sequentially connect the cover-testing gadgets corresponding to those edges. We connect them by introducing a new edge connecting v_out of one gadget with v_in of the next. Also, for now, we leave unconnected the entry and exit points of the respective first and last gadgets in this sequence.

Obviously each cover-testing gadget will have inbound/outbound connections for both vertices it covers, with the exception of those degree-1 vertices incident to only one edge, which remain unconnected for now.

See the G' construction up to this point for following simple example below:

Complete G' with the selector gadget

We complete our construction as follows.

Deploy K ‘selector’ vertices. Recall, K belongs to the instance of VC.
Connect each selector vertex to each unconnected vertex in our above network of cover-testing gadgets. That is to say, connect each of the k selector vertexes to the unconnected entry and exit points of each sequence of gadgets from above.

This completes G'. You will notice that G' now has full cycles and no dangling (degree-1) vertices (which would make a Hamiltonian cycle impossible).

For the sake of compactness, I’ll make one more simplification. While the physical G' contains K selector vertices, each meticulously wired to all of those unconnected entry/exit points, we can facilitate our abstraction by replacing the *K' vertices with one selector gadget of degree K, labeled as S^K.

See the completed example for the above graph with the selector gadget deployed.

Do you see why I enjoy working with gadgets? The reduction actually resembles something I haphazardly wired in a garage.

Reduction correctness

We can consider our reduction efficient, constructible in time polynomial with respect to K|V||E|.
G has a vertex cover of size ≤ K implies G' has a Hamiltonian cycle.

First, let’s assume a vertex cover of exactly K, since we can always incorporate a larger cover into a graph. K vertices of V are sufficient to cover all edges. Let’s take one such vertex cover A={v₁,v₂,…,v_k} ⊆ V. How do we form a Hamiltonian cycle in G'?

We start and end with our selector gadget S^K. Now, in the physical graph, we would start at any one of the K selector vertices and end the cycle at the same vertex, covering all other selector vertices and cover-testing gadgets in the process. However, since all selector vertices exhibit the same connections, S^K abstracts this complex networking and requires that we simply pass through it exactly K times to form our cycle. Convince yourself to this equivalence of representations.

For each vertex v ∈ A, we’ll perform one pass through S^K and the entire series of cover-testing gadgets representing v. Each respective gadget also represents the other vertex in the edge, let’s say u.

In one case, u is not part of the cover, that is, edge (v,u) is only covered by vertex v. Entering the gadget via v_in, we traverse each vertex comprising the gadget exactly once before exiting via v_out. Convince yourself, regardless of gadget impelentation chosen above, that such a traversal is possible. Conseqently, that gadget will not be traversed again.

In the second case, both v and u cover the edge. We then enter the gadget via v_in and proceed straight down towards v_out, without covering the u vertices. In effect, we enable a second pass through the gadget for the vertex u. Once we reach vertex u ∈ A and proceed down the path of respective gadgets, we’ll eventually encounter the same (v,u) gadget, this time proceeding straight down via u_in to u_out, still available for our traversal.

Ultimately, we’ll traverse K such paths, each time proceeding through S^K and the respective series of cover-testing gadgets representing the edges covered by the current v ∈ A. This traversal forms our Hamiltonian Cycle.
G' has a Hamiltonian cycle implies G has a vertex cover of size ≤ K.

We traverse S^K a total of K times. (Again, we appeal to the equivalency of the G' physical representation and the selector-gadget abstraction.) In each of these traversals, the HC passes through a series of cover-testing gadgets corresponding to all edges incident to a particular and distinct vertex v ∈ V. Moreover, each pass through a cover-testing component can occur in only one of two ways mentioned in the previous step of the proof. In both occasions, it must enter and exit via a point corresponding to v, connecting it to the next component representing another edge incident to v, or ultimately back to S^K. Since the HC covers all vertices of V', all cover-testing gadgets, and consequently all edges in E, this set of K paths we traverse corresponds to the K vertices that cover G.

End of proof.

We’ve shown that HC belongs to NP, and we’ve shown that it’s NP-Complete by a reduction from another NPC problem, demonstrating the reduction correctness and efficiency. We’ve also showcased a gadget-based reduction, a type that tends to reoccur in a number of set and graph oriented hardness proofs.

References

Garey, Michael R. and Johnson, David S. Computers and Intractability; A Guide to the Theory of NP-Completeness. 1979.

Questions, comments? Connect.

Hamiltonian Cycle hardness and gadgets