# Find minimum set of vertices that are reachable from all other vertices

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.

• 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? – quicksort Dec 30 '17 at 15:52
• 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. – Myron Dec 30 '17 at 16:03
• I don't understand what you are saying. – quicksort Dec 30 '17 at 16:04
• 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. – Myron Dec 30 '17 at 16:22
• In a directed acyclic graph edges are directed. They wouldn't reach each other. – quicksort Dec 30 '17 at 16:32

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