# Find all paths between specially paired nodes in a DAG in linear time

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
\
D_2


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?

• 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. Aug 30, 2020 at 0:15