2
$\begingroup$

I have a DAG and I wish to find the minimal set of vertices that have a path to all other vertices.

My solution was to simply find all the vertices that their incoming degree is 0. However, if there are two vertices in the DAG that have an indegree of 0 and that point to a common vertex then one of the two vertices is surplus.

Any help appreciated.

$\endgroup$
  • $\begingroup$ Why is the case you mention a problem? You would still need to include both original vertices as they don't reach each other. Am I understanding the problem wrong? $\endgroup$ – quicksort Dec 30 '17 at 15:52
  • $\begingroup$ If two vertices in the set represented the same group of reachable vertices then one of them can be omitted since it does not have any new vertices to reach. $\endgroup$ – Myron Dec 30 '17 at 16:03
  • $\begingroup$ I don't understand what you are saying. $\endgroup$ – quicksort Dec 30 '17 at 16:04
  • $\begingroup$ Lets say for expamle there is a spanning tree in the DAG, and there are two vertices that pointed to the source vertex of that tree. Why should you include both vertices in the minimal set if only one is needed to reach all the other vertices in the tree. $\endgroup$ – Myron Dec 30 '17 at 16:22
  • $\begingroup$ In a directed acyclic graph edges are directed. They wouldn't reach each other. $\endgroup$ – quicksort Dec 30 '17 at 16:32
2
$\begingroup$

Your algorithm is correct, provided that the following is a formal definition of your problem:

Given a DAG $D = (V, A)$, find a minimum set $C \subseteq V$ such that for every vertex $v \in V$, either $v \in C$ or there exists a vertex $c \in C$ such that $v$ is reachable from $c$.

Let's call a vertex with indegree 0 a source and any vertex set that satisfies the reachability part a cover.

Claim. The optimal solution is $C = \{v \in V \mid v \text{ is a source}\}$.

Claim 1. $C$ is a solution. Trivial since $D$ is a DAG.

Claim 2. Every vertex $c \in C$ is in every cover. Since it has indegree 0 it cannot be reached by any other vertex.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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