That's more or less what I got out of it as well, though I came at it from the other direction...
If you skip the first part about pre-processing, and instead look at the graph that is generated, you can come up with following:
1. There exists a graph consisting of potential truth assignments on N unknowns in M clauses consisting of 7M nodes, and <48M2 edges.
2. Label each node uA,uB,uC,vA,vB,vC where u? is the unknown number, and v? is whether that unknown is true or false.
3. Edges exist between node I and node J if either nodes I and J share zero unknowns, OR both I and J share at least one variable AND all shared variables have the same value.
4. For there to be an assignment that causes the full statement to be correct, you must find an M-clique (a complete graph on M nodes within the 7M node graph).
Solving part 4 is NPC.
His claim is, basically, that if you permute/partition the input (to construct the tables), you can construct a disconnected graph with far fewer edges (get rid of the first part of #3 above), then add links graphs in such a way that if you can find a path from a tier-1 node to a tier-2 node, ..., to a tier-M node, examining the labels is sufficient to solve the problem. The two nasty parts are finding an efficient permutation/partition step, then managing to properly link the disconnected graphs. As you say, the two steps that the author hand-waves.
If you skip the first part about pre-processing, and instead look at the graph that is generated, you can come up with following:
1. There exists a graph consisting of potential truth assignments on N unknowns in M clauses consisting of 7M nodes, and <48M2 edges.
2. Label each node uA,uB,uC,vA,vB,vC where u? is the unknown number, and v? is whether that unknown is true or false.
3. Edges exist between node I and node J if either nodes I and J share zero unknowns, OR both I and J share at least one variable AND all shared variables have the same value.
4. For there to be an assignment that causes the full statement to be correct, you must find an M-clique (a complete graph on M nodes within the 7M node graph).
Solving part 4 is NPC.
His claim is, basically, that if you permute/partition the input (to construct the tables), you can construct a disconnected graph with far fewer edges (get rid of the first part of #3 above), then add links graphs in such a way that if you can find a path from a tier-1 node to a tier-2 node, ..., to a tier-M node, examining the labels is sufficient to solve the problem. The two nasty parts are finding an efficient permutation/partition step, then managing to properly link the disconnected graphs. As you say, the two steps that the author hand-waves.