Source code online books for professionals by professionals

Figure 11-4.  The rows are linked so the Hamilton cycle can maintain or switch its direction when going from one 
variable to the next, letting A and B be true or false, independently of each other
Figure 11-3.  A single “row,” representing the variable A the Boolean expression we’re trying to satisfy. If the cycle passes 
through from left to right, the variable is true; otherwise, it’s false
If we have only a set of rows connected as shown in Figure 
11-4
, there will be no Hamilton cycle in the graph.  
We can pass only from one row to the next and have no way of getting up again. The final touch to the basic row structure, 
then, is to add one source node s at the top (with edges to the left and right anchors of the first row) and a sink node t 
at the bottom (with edges from the left and right anchors of the last row) and then to add an edge from t to s.
Before moving on, you should convince yourself that this structure really does what we want it to. For k variables, 
the graph we have constructed so far will have 2
k
 different Hamilton cycles, one for each possible assignment of truth 
values to the variables, with the truth values represented by the cycle going left or right in a given row.
Now that we’ve encoded the idea of assigning truth values to a set of logical variables in our Hamilton machine, 
we just need a way of encoding the actual formula involving these variables. We can do that by introducing a single 
node for each clause. A Hamilton cycle will then have to visit each of these exactly one time. The trick is to hook these 
clause nodes onto our existing rows to make use of the fact that the rows already encode truth values. We set things up 
so that the cycle can take a detour from the path, via the clause node, but only if it’s going in the right direction. So, for 
example, if we have the clause (A or not B), we’ll add a detour to the A row that requires the cycle to be going left to 
right, and we add another detour (via the same clause node) to the B row, but this time from right to left (because of 
the not). The only thing we need to watch out for is that no two detours can be linked to the rows in the same places—
that’s why we need to have multiple nodes in each row, so we have enough for all the clauses. You can see how this 
would work for our example in Figure 
11-5
.

---

Chapter 11 
■
 hard problems and (lImIted) sloppIness
238
After encoding the clauses in this way, each clause can be satisfied as long as at least one of its variables has the 
right truth value, letting it take a detour through the clause node. Because a Hamilton cycle must visit every node 
(including every clause node), the and-part of the formula is satisfied. In other words, the logical formula is satisfiable 
if and only if there is a Hamilton cycle in the graph we’ve constructed. This means that we have successfully reduced 
SAT (or, more specifically, CNF-SAT) to the Hamilton cycle problem, thereby proving the latter to be NP-complete! 
Now, was that so hard?
All right, so it was kind of hard. At least thinking of something like this yourself would be pretty challenging. 
Luckily, a lot of NP-complete problems are a lot more similar than SAT and the Hamilton cycle problem, as you’ll see 
in the following text.