You are given a directed acyclic graph G = (V, E) in which each node has one “left” out-arc and one “right” out-arc, with a distinguished source node s and sink node t. You are also given a list of “ties” (u, v) which say that if you take the left [right] edge out of u, then you must also take the left [right] edge out of v. Is there a path from s to t subject to the ties? Show that this decision problem is NP-complete.

For this I know we can reduce a 3SAT to a problem of checking whether a path exists or not between 's' and 't'. But I am finding difficult to add the constraints of "ties" into it


closed as unclear what you're asking by Evil, David Richerby, Luke Mathieson, Juho, vonbrand Dec 19 '15 at 3:34

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ So you know there is a reduction, but you don't know how it works? $\endgroup$ – G. Bach Dec 4 '15 at 14:09
  • $\begingroup$ I know the reduction for 3SAT to Check whether there exists a path between 's' and 't' but this problem is a variant of it. As, there are constraints on the nodes in terms of "ties". $\endgroup$ – letsBeePolite Dec 4 '15 at 14:14
  • $\begingroup$ Hint: The ties represent pairs (or, by symmetry and transitivity, sets) of decisions for which you are required to make the same choice. Similarly, in 3SAT, for all occurrences of a given variable $x$ in a CNF you have to assume the same value. $\endgroup$ – Klaus Draeger Dec 4 '15 at 15:33
  • 1
    $\begingroup$ @Check I rolled back your edit. If you want to ask a completely different question, ask it as a new question, not an edit of an existing one. $\endgroup$ – David Richerby Dec 4 '15 at 21:12
  • 1
    $\begingroup$ Assuming that P$\,\neq\,$NP, you cannot reduce 3SAT to $s$-$t$-connectivity (at least, not with deterministic polynomial-time many-one reductions), since the former is NP-complete and the latter is in P. Do you have the reduction the wrong way round? $\endgroup$ – David Richerby Dec 4 '15 at 21:14

Suppose you are given a CNF $C_1\wedge\dots\wedge C_k$, with clauses of the form $C_i = L_i^1\vee L_i^2\vee L_i^3$, each literal $L_i^j$ being either $x_i^j$ or $\neg x_i^j$ for some variable $x_i^j\in V$. Construct a graph as follows:

  • Set of nodes is $N=\{n_i^j\ |\ 1\le i\le k, 1\le j\le 3\}\cup\{\top,\bot\}$.
  • For all $i,j$: let the "sat" successor be $n_{i+1}^1$ for $i<k$, and $\top$ otherwise; let the "unsat" successor be $n_i^{j+1}$ for $j<3$, and $\bot$ otherwise. If $L_i^j=x_i^j$, the left and right edge from $n_i^j$ go to the sat and unsat successor, respectively; if $L_i^j=\neg x_i^j$, it is the other way around.
  • Add ties between all pairs of nodes $(n_i^j,n_p^q)$ with $x_i^j=x_p^q$.

Then a valuation of the variables in $V$ corresponds exactly to a choice of left or right such that for all nodes belonging to the same variable, the same direction is chosen; a satisfying valuation corresponds to a choice of directions which leads from $s=n_1^1$ to $t=\top$.


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