2
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • $\begingroup$ As far as I can see, $\{V\}$ is an answer to your problem. It meets all three of your properties. If two vertices have no path between them, they're definitely both in $V$; there's only one set, so none is a subset of any other; you can't do it in fewer sets! Did you also mean to include the criterion that you're not allowed to have a path between any pair of vertices in the same set? $\endgroup$
    – David Richerby
    Aug 4, 2016 at 8:38
  • $\begingroup$ Yes you are right. Even if not formally, this is obvious from the question definition and from the examples themselves. So we are not expecting the question definition to be compiled by a compiler, are we? $\endgroup$
    – mas
    Aug 4, 2016 at 8:50
  • $\begingroup$ No, I certainly did not find that obvious from the question definition. If you have a requirement, you need to state it explicitly. (An example is not a substitute for a problem specification; you still need to specify your problem carefully.) I've edited the question for you, but for future reference, that's your job to make sure to state all requirements explicitly. $\endgroup$
    – D.W. ♦
    Aug 4, 2016 at 16:53
  • $\begingroup$ Anyway, thanks for the edits! Now that we have a clear problem statement, the next question is: What have you tried? What approaches have you already tried, and what challenge did you run into? What's the fastest algorithm you've found so far? Have you found any polynomial-time algorithm at all, no matter how inefficient? Have you tried looking for a reduction that proves NP-completeness? We expect you to try everything you can think of to solve the problem on your own, and to tell us in the question what you've tried and what the best solution you've found so far is. $\endgroup$
    – D.W. ♦
    Aug 4, 2016 at 16:55
  • $\begingroup$ Also, what counts as "efficient" for you? Is polynomial-time sufficient to count as "efficient"? If not, what are your criteria? $\endgroup$
    – D.W. ♦
    Aug 4, 2016 at 16:59

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.