Minimum number of sets of unreachable vertices for directed acyclic graph (DAG) 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. &lt;A, B&gt;
2. &lt;A, C&gt;
3. &lt;B, C&gt;
4. &lt;C, D&gt;
5. &lt;D, E&gt;


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.
The problem is fixed-parameter tractable, where the parameter is the number of output sets.

Define an undirected graph $G'$ with an edge $(v,w)$ for each unreachable pair of vertices in the original graph.  Now you want to find a minimal edge clique cover of $G'$.  The minimal edge clique cover problem is fixed-parameter tractable, where the parameter is the number of cliques.

I don't know if there is a polynomial-time algorithm.  The minimal edge clique cover problem is NP-complete for general graphs.  I don't know if $G'$ has any special properties that makes the minimal edge clique cover problem easy on it.  (It's not necessarily chordal, unfortunately.)