World's most popular travel blog for travel bloggers.

# [Solved]: Minimum number of sets of unreachable vertices for directed acyclic graph (DAG)

, ,
Problem Detail:

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:

1. For each unreachable pair of vertices $\langle v,w \rangle$, at least one of the output sets contains both $v$ and $w$,
2. Every pair of vertices $v,w$ that are contained in the same output set must be an unreachable pair, and
3. 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.

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.)