A few more reductions

Theorem: SAT is polytime reducible to 3SAT.

Proof (idea). Using the following idea clauses of length > 3 can be broken into smaller ones:

(x \lor y \lor z \lor w) \Leftrightarrow (x \lor y \lor a) \land (z \lor w \lor \bar{a})

After making all clauses of length at most 3 we can easily increase smaller clauses lengths to make all equal to 3:

(x \lor y) \Leftrightarrow (x \lor y \lor a) \land (x \lor y \lor \bar{a})

Definition: k-popsicle is a graph including a clique of size k where one of the vertices is extended by a path of length k.

Theorem: k-clique problem is polytime reducible to k-popsicle (determining whether the graph contains it or not)

Proof: Given the query graph G for k-clique, extend each of vertices by a path of length k to get a new graph H. It is easy to see that G has a k-clique if and only if H has a k-pupsicle, so we can return the answer for k-pupsicle on H as the answer for k-clique on G. Note that we increased the size of query graph by a polynomial.

We further read through Karp’s 1972 paper “Reducibility Among Combinatorial Problems”, from which here are some reductions:

Theorem: 3-SAT is polytime reducible to Directed Hamiltonian Cycle.

Proof. Given a SAT of n variables and m clauses we are going to build a directed graph that has a Hamiltonian cycle if and only if the SAT was satisfiable.

For each variable consider a subgraph (namely gadget) of an entrance and an exit vertex and a path of length 2m between them. The entrance is connected towards both ends of the path and both ends are connected towards the exit. The vertices along the path are connected to each other in both directions. Having the Hamiltonian cycle traveling through the path from left to right would be corresponding to True value for the relevant variable and vice versa (False for left-ward traversal). Pairing the 2m vertices along the path, each pair will correspond to one clause. For each clause the gadget is a single vertex that is connected by back and forth edges to its corresponding pairs from gadgets of variables appeared in it, to be along the left to right path if the variable is positive and along right to left if it is negative. Stacking the variable gadgets by directed edges and adding another edge from last exit to the first entrance one can see the final graph has a (directed) Hamiltonian cycle if and only if the SAT formula has been satisfiable. An visualized example of this reduction can be found here.

Theorem: Directed Hamiltonian cycle is polytime reducible to Hamiltonian Cycle.

Proof. Here the gadget for every vertex v \in G in the input directed graph simply consists of a path of 3 vertices, v_i, v', v_o in H. The role of v' is to make v_i and v_o to appear consecutively in a potential Hamiltonian cycle in H. For any directed edge (u,v) \in G we add undirected edges (u_o,v_i), (u_i, v_o) to H. It is easy to see that H has a Hamiltonian cycle if and only if G has a directed one.

Advertisements