Linear time algorithm to determine whether a DAG has a vertex reachable from every other vertex?

Question

I have the following homework question: DAG: Design a linear-time algorithm (O(|E|+|V|)) to determine whether a DAG has a vertex that is reachable from every other vertex, and if so, find one.

Now my approach to solving this question is as follows: ->First find the vertex that comes last in the topological ordering(call it V).

->Now, determine if every vertex of the reverse graph is reachable from this vertex V.

-> If every vertex is reachable, then the vertex V is the required vertex, otherwise there is no vertex in the graph that is reachable from every other vertex.

Is this approach correct?

PS. The hint for this question's solution says that I should compute the outdegree of each vertex. But I cannot understand how computing the outdegree helps.

Answer 1

Consider an arc (u, v) ∈ E. Since the graph is acyclic, u is not reachable from v. Thus u cannot be the solution to the problem. From this it follows that only a vertex of outdegree zero can be a solution.

Furthermore, there has to be exactly one vertex with outdegree zero, or the problem has no solution.

I leave the rest as an exercise for the reader.

Answer 2

The solution would be computing the out-degrees of all vertices to see if there is one single sink vertex (a vertex with 0 out-degree), here is the proof.

Statement: A DAG has a vertex that is reachable from every other vertex if and only if there is one single vertex with 0 out-degrees.

This statement can be proven in two steps.

Proof of necessity: If a DAG contains a vertex u that is reachable from every other vertex, it must be the only sink vertex (a vertex with 0 out-degree)

• u have 0 out-degree, otherwise cycle forms, contradicting DAG.
• There can't be another sink vertex v with 0 out-degree, otherwise u is not reachable from v

Proved.

Proof of sufficiency: If a DAG contains one single sink vertex u, then u should be reachable from every other vertex.

Assume there exist vertices in the DAG that can't reach u. Let's divide all vertices in the DAG into the set of vertices that can reach u ($V_y$), and those cannot reach u ($V_n$), then there do not exist any edges from vertices in $V_n$ pointing to vertices in $V_y$.

Lemma: Any DAG must contain at least one sink vertices.

This is easy to prove by contradiction. Assume every vertex in the DAG has non-zero out-degrees, so starting from one vertex, we can keep traversing along the out-going edges of each vertex. Since DAG contains a finite number of vertices, we will return to a previously visited vertex eventually, i.e. cycle is detected, contradicting DAG definition.

Consider the graph formed by vertices in $V_n$ and edges between them, it must also be a DAG, otherwise, the original graph cannot be a DAG. Suppose v is a sink vertex in this sub-DAG, so v doesn't have any outgoing edge pointing to vertices in $V_n$.

As mentioned above, there can't be any edges from v pointing to any vertex in $V_y$ either, otherwise, v can reach u.

So the overall out-degrees of v in the original DAG is also 0, contradicting the assumption that the DAG contains a single sink vertex. Proved.

Answer 3

As a hint, consider than you can divide a DAG into source nodes (indegree 0), intermediate nodes and sink nodes (outdegree 0) - with the usual definitions.

If a DAG does contain such a node (reachable from every other vertex), what type of node would it be?

Draw an example of a graph with two nodes with outdegree 0, that has one vertex reachable from every vertex.