0
$\begingroup$

So I came across this problem in my textbook. I was wondering how to develop a reduction from the Graph Reachability problem to SAT (CNF) problem. (i.e. formula is satisfiable iff there exists a path in graph G from start to end node)

1) I can't wrap my head around how to go from something that can be solved in polynomial time (Graph Reachability) to something that is NP (SAT).

2) I can't seem to find a way to formulate these nodes/edges of Graph into actual clauses in CNF that correspond to reachability.

I tried to think about algorithms like Floyd-Warshall that determine if a path exists from start to end node but I can't seem to formulate that idea into actual CNF clauses. Help would be much appreciated!

$\endgroup$
1
$\begingroup$

Maybe the solution is to use the 2-SAT problem which does have a polynomial solution.

For a 2-SAT problem, you can indeed build an implication graph. Basically a clause $(a \vee b)$ leads to the implications $\neg a \implies b$ and $\neg b \implies a$. The problem is satisfiable if there is no variable $x$ such that $x$ and $\neg x$ are in the same SCC of the implication graph. Being in same SCC is equivalent to double reachability:

  • it exists a path from $x$ to $\neg x$
  • it exists a path from $\neg x$ to $x$

So for any skew-symmetric (required property) graph, you can build a 2-SAT problem for which it is the implication graph.

$\endgroup$
1
$\begingroup$

1) I can't wrap my head around how to go from something that can be solved in polynomial time (Graph Reachability) to something that is NP (SAT).

Note that, if the notion of reduction you use allows any function which can be computed in polynomial time (and not, say, log-space), we can use a trivial reduction function. Write $A$ for the P problem (e.g., graph reachability). Take any formula $q_1$ in SAT (say, $p$) and any formula $q_0$ not in SAT (say, $p\land\lnot p$). Then:

$$ f(x) = \begin{cases} q_1 & \mbox{if } x \in A \\ q_0 & \mbox{otherwise} \end{cases} $$

This function can be computed in polynomial time: we only have to decide $x\in A$, which we can since $A$ is in $P$, and then return one constant formula between $q_1$ and $q_0$.

The point is: we don't have to actually encode the problem in SAT, since we can solve the problem in the reduction function. (This may feel like "cheating", at first.)

Another general method for such a reduction is given by the proof of the NP-completeness of SAT, which generates a large circuit (or formula) from any instance of any NP problem (including those in P). (This is usually way more complex than needed, though.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.