You are given a directed acyclic graph G = (V, E) in which each node has oneleft 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
Reduction from 3SAT
complexity theory;np complete;reductions;np hard