3
$\begingroup$

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.

Advice?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Sep 21 '14 at 4:55
  • $\begingroup$ 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. $\endgroup$ – BrokenBridges Sep 21 '14 at 4:57
  • 1
    $\begingroup$ 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. $\endgroup$ – D.W. Sep 21 '14 at 5:01
  • $\begingroup$ @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. $\endgroup$ – BrokenBridges Sep 21 '14 at 5:05
1
$\begingroup$

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.

To check condition (2), traverse the topological ordering in order, and for each vertex encountered, remove the vertex. Since this is a topological ordering, when a vertex is removed, it is a source, that is, it has no incoming edges. Condition (2) is satisfied for the vertex iff it is the unique source at that point. Condition (1) can be checked similarly by traversing the topological ordering in reverse.

$\endgroup$
  • $\begingroup$ This seems to put me on the right track. I can't find any situation in which I'd have to check condition (1), though. It seems sufficient to do condition (2), only. Find the source, mark and remove it, check if there's a unique source, and if so, mark and remove it. If there's no unique source, stop, as no further vertex will be able to access all other vertices. The marked vertices meet the described property. $\endgroup$ – BrokenBridges Sep 21 '14 at 17:00
  • $\begingroup$ 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$. $\endgroup$ – Yuval Filmus Sep 21 '14 at 17:03
  • $\begingroup$ 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. $\endgroup$ – BrokenBridges Sep 21 '14 at 17:08
  • $\begingroup$ 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). $\endgroup$ – Yuval Filmus Sep 21 '14 at 17:11
  • $\begingroup$ 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)}$. $\endgroup$ – BrokenBridges Sep 21 '14 at 17:20
1
$\begingroup$

Just to make sure. If,a graph is strongly connected then it has a cycle. which in turn means you cannot have topological sort.

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