# Finding vertices for which there either exists a path to all other vertices or other vertices have a path to them

Or in other words, find all $v \in V$ such that there exists a path $\forall w \in V$ $v \rightarrow w$ or $w \rightarrow v$. This is for a directed acyclic graph. I need to find an $O(|E| + |V|)$ algorithm for this.

I can see how to identify if a given vertex meets these traits (perform a BFS starting at that vertex, then do another BFS on the reverse of that graph and see if every vertex was visited in those BFSes). The obvious solution would be to run this on every vertex of the graph, but that will end up being $O(|E||V| + |V|^{2})$.

I've considered identifying strongly connected components, but that doesn't seem like the right approach, since a SCC requires that $v$ and $w$ are mutually reachable, whereas this homework question requires that $v$ and $w$ are only reachable one way.

• If the graph is a DAG then there is no point in computing the strongly connected components, since they are all trivial. On the other hand, for a general digraph, computing the strongly connected components reduces the problem to DAGs. – Yuval Filmus Sep 21 '14 at 4:55
• Right, I don't know what I was thinking. Since DAGs are, by definition, acyclic, each vertex must be its own strong component. Unfortunately, this doesn't really bring me any closer to figuring out how to approach the question. – BrokenBridges Sep 21 '14 at 4:57
• I'm having a hard time understanding the first sentence of your question. Can I encourage you to edit it to clarify? What's $w$? What is the order of the quantifiers? What does $(v,w)$ mean? Normally notation like $(v,w)$ is used to denote an edge. – D.W. Sep 21 '14 at 5:01
• @D.W., it should be paths (not edges) from $v \rightarrow w$ and $w \rightarrow v$, where $w$ is every vertex in the graph. So $v$ meets this property if it either has a path to every other vertex or if there's a path from every other vertex to it (or some mixture of paths to other vertices and paths from other vertices). Will edit post. – BrokenBridges Sep 21 '14 at 5:05

We can assume that the DAG is connected, since otherwise the solution is trivial. Consider some topological ordering of the vertices. A vertex $v$ satisfies your condition if (1) $v$ can be reached from all vertices preceding $v$ in the ordering and (2) all vertices following $v$ in the ordering are reachable from $v$. We can check conditions (1) and (2) separately.
• Consider a graph with three vertices $x,y,z$ and edges $(x,y),(x,z)$. Given the order $x,y,z$, vertex $z$ satisfies property (2) but not property (1), since it cannot be reached from $y$. – Yuval Filmus Sep 21 '14 at 17:03
• You're right about that, but since we started at $x$ (since it's the source), then we'll remove $x$ before we even observe $y$ and $z$. With $x$ removed, there's no unique source, so the algorithm can stop. – BrokenBridges Sep 21 '14 at 17:08
• It can't stop, it has to continue. Imagine there is one more vertex $w$ and edges $(y,w),(z,w)$. The vertex $w$ does satisfy property (1). – Yuval Filmus Sep 21 '14 at 17:11
• Just to be sure, when you say that we can't stop here, you're referring to the algorithm as a whole, right? It seems that we could stop trying to satisfy property (2) once we notice a non-unique source, and then try and solve property (1). This would work because the vertex meets this property if it satisfies (1) or (2) (although the premise of your question says "and"). That would work properly for the graph with $E = {(x,y), (x,z), (y,w), (z,w)}$. – BrokenBridges Sep 21 '14 at 17:20