Lecture 25: Hamiltonian Cycle Problem
Hamiltonian Cycle Problem:
Given a graph G, is there “a path that visits each vertex once and return to the start,” i.e. a Hamiltonian Cycle?
Claim: “Hamiltonian Cycle is NP-complete.”
Proof: Hamiltonian Cycle is in NP because a given list of vertices can be checked for a tour in polynomial time. Now, we want to show that 3-SAT reduces to Hamiltonian Cycle in polynomial time. Thus, we need some way of mapping the variables and clauses to a hamiltonian cycle problem graph:
While this graph is complex at first, look at how it is built. For each variable, there is a row of at most 2n nodes, where n is the number of clauses. Two of these nodes are connected to each clause if the variable appears in that clause. The ends of each row of nodes are connected to the ends of the next. Walking left to right down a row means “true,” while right to left means “false.” In this way, a Hamiltonian cycle through the graph represents an assignment of truth values to the variables in a list of 3-SAT clauses.
Claim: “The 3-SAT boolean formula is satisfiable if and only if the graph has a hamiltonian cycle.”
Proof (=>): Assume the formula is satisfiable by some truth assignment. Choose one true term in each clause, traverse the graph moving across each variable’s path in the appropriate direction, and take a diversion to a clause node for each term chosen above. This path is a Hamiltonian cycle.
Proof (<=): Suppose there exists a Hamiltonian cycle c that traverses a variable’s row either left to right or right to left. Call one way true, and the other false. Ecah clause node is visited by a side-trip from a variable row. This variable corresponds to a true term in the clause.
External Links: