I have a DAG with vertices $V$ and edges $E$. If $v,w \in V$ are vertices such that $v$ is not reachable from $w$ and $w$ is not reachable from $v$, I will say that $\langle v,w \rangle$ is an unreachable pair.
I want to implement an efficient algorithm which takes this DAG as input, and produces as output a list of sets of pvertices such that:
- For each unreachable pair of vertices $\langle v,w \rangle$, at least one of the output sets contains both $v$ and $w$,
- Every pair of vertices $v,w$ that are contained in the same output set must be an unreachable pair, and
- The number of output sets must be the minimum possible.
Is there a polynomial-time algorithm for this problem?
As an example, we have the following DAG with topologically ordered vertices
A,B,C,D,E:
A is connected to [D, E]
B is connected to [D, E]
C is connected to [E]
D is connected to []
E is connected to []
which means that we have the following unreachable vertex pairs:
1. <A, B>
2. <A, C>
3. <B, C>
4. <C, D>
5. <D, E>
The expected output is composed of the following three vertex sets:
1. {A, B, C}
2. {C, D}
3. {D, E}
The output was not {A,B} {A,C} {B,C} {C,D} {D,E} because the minimum number of possible output sets is 3 instead of 5 as given above. Otherwise it would satisfy the first two conditions, but not the third condition.
As another example, consider the same DAG vertex set V but where the edge set E is empty. Since all vertex pairs would be unreachable, the expected output is the vertex set V itself.
