If I have a DAG with 2n nodes partitioned into n pairs of nodes with e edges, is there a linear-time (O(n + e)) way to find the subset of all pairs for which there exists a path from one to the other?

So for instance, in the DAG (letting \ and / be downward-pointing edges):

   A_1     C_2
  /   \   /   \
A_2    B_1     D_1
  \       \   /
   B_2     C_1

I want to return the set {A_2, C_1} since there exists a path from A_1 to A_2 and from C_2 to C_1, but there's no (directed) path between B_1 and B_2 or between D_1 and D_2.

Does it help to add the constraint that the graph be symmetric under reversing all the edges and swapping each node with its partner?

  • $\begingroup$ Context: I want to quickly identify all forced literals in a large 2-sat problem. I've already replaced each of the SCC's with a single representative which is why the graph is acyclic. $\endgroup$
    – dspyz
    Aug 30, 2020 at 0:15


Your Answer

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

Browse other questions tagged or ask your own question.