NP Complete, Finding a Hamiltonian Circuit

Search Site map Contact us Operation Clog

Main Page

Languages

Complexity Theory

NP Complete Problems

Use the arrows

below to step through NP Problems.

Custom Links:

Finding a Hamiltonian Circuit

In a digraph, a hamiltonian circuit is a path that travels through every vertex once, and winds up where it started. Clearly the graph must be strongly connected.

The problem of finding such a circuit can be reduced to 3-sat, hence it is np complete.

Given an instance of 3-sat, construct a subgraph for each variable and a subgraph for each clause; then tie variables to the clauses that contain them via additional arcs. Here goes.

For each variable, such as x, build a structure that looks something like a ladder. The rungs are bidirectional arcs. You can travel from left to right or right to left along any rung. Instead of vertical rails, the rungs are cross connected going down. You can go from the left end of one rung to the right end of the rung below, or from the right end of one rung to the left end of the run below.

If the circuit enters the ladder at the top left, and leaves at the bottom, it must traverse the top rung going right, drop diagonally to the left of the next rung, cross it going right, drop diagonally to the left of the next rung, and so on. If the circuit enters from the right it takes the reflected path down the ladder. When the entire graph is constructed, the circuit will start from the right if x is true, and from the left if x is false.

Arrange the variables in an arbitrary, cyclic order. If y follows x, the botton rung of x connects to the top rung of y, using four arcs. In other words, either end of the bottom run of x drops down to either end of the top rung of y. Thus y can be true or false, regardless of the value of x. At this point all boolean variables are independent. A hamiltonian circuit selects a value, true or false, for each variable.

How many rungs are required? The ladder associated with x has one rung for each x in the expression, and one rung for each ~x, and one more rung for good measure.

For each clause, connect three input nodes in a one-way triangle, and connect three output nodes in a one-way triangle. Tie each input node to a corresponding output node, so that the triangles run in opposite directions. If our circuit enters an input node, and leaves from an output node, the two nodes must correspond. In so doing, the path consumes 2, 4, or all 6 nodes. Any other path, whose input and output do not correspond, will leave at least one vertex inaccessible.

If the clause is x|y|~z, associate a pair of nodes, input and output, with x, and another pair with y, and another pair with ~z.

Finally we need to connect the clause to its three variables. Continue the above example, x|y|~z. Find the ladder that defines x, and add an arc from this ladder to the input node associated with x, and from the corresponding output node back to the ladder. Since x is true in the clause, the connection should parallel a left-right diagonal drop from one rung to the next. Thus if x is true, we can drop down, or run through the clause, consuming 2 4 or 6 of its nodes along the way. When a variable is negated, such as ~z, the connection parallels a right-left diagonal drop.

For any given clause, its six nodes can be completely traversed iff at least one of the three variables is able to run through that clause, iff the clause is satisfied by the configuration of the variables. There is a hamiltonian circuit iff the 3-sat expression can be solved.

Traditional Graphs

It is no easier to find hamiltonian circuits in graphs (rather than digraphs). Given a digraph, like the one above, convert it to a graph by replicating each vertex three times. Thus v yields v₀, v₁, and v₂, with edges v₀-v₁ and v₁-v₂. Add an edge v₂-w₀ if v→w in the digraph.

Start at v₁ and build a hamiltonian circuit for the graph. If the first arc is v₁→v₂, the path defines a hamiltonian circuit on the aforementioned digraph. If the first arc is v₁→v₀, the circuit is run in reverse. Either way, the circuit is identified, and satisfiability is established. Therefore the hamiltonian problem remains np complete for graphs.

Open Circuit

If you want a path between two different points that hits every vertex exactly once, tie the start and end points to a new home vertex h via two edges and look for a hamiltonian circuit that starts and ends at h. Conversely, remove h, and search for a path between two vertices adjacent to h. One can be found iff the other can be found, and the problems are equivalent.

Finding Trails of a Given Length

Given a graph g, a starting point s, and a length l, is there a trail (no edge repeated) that starts and ends at s and contains l edges?

Let h be a hamiltonian graph, with a hamiltonian circuit. Assume h has e edges and v vertices. Construct a new graph g as follows. Each vertex in h produces a cycle of length e+1 in g. One point in each cycle is designated "external". Each edge in h produces an edge connecting the external points of the corresponding cycles in g. (These can be directed edges, if you're dealing with digraphs.) Label any vertex of g as s. The graph h has a Hamiltonian circuit iff g has a trail of length l = (e+2)×v. Leave even one cycle out of the trail, and there aren't enough intercycle edges (inherited from h) to make up the difference. The trail covers all cycles, and defines the hamiltonian circuit.

Custom Links: