Find every edge for which every s,t-path in a DAG goes through that edge

Question

Given a connected sourced/sinked directed acylic graph $G = (V, E \subseteq V^2, s \in V, t \in V)$, we want to enumerate the edges $e \in \mathsf{Bottleneck}(G) \subseteq E$ for which every $s$,$t$-path contains $e$. I don't actually know the real name for this notion; so I'm calling it the "bottleneck set", but when I google that I get unrelated concepts.

An obvious solution is for each edge $e \in E$, run DFS on $G$ to get all $s$,$t$-paths, and check each one for whether it contains $e$. If all of them do, then $e$ is part of $\mathsf{Bottleneck}(G)$. However, this has runtime $O(E(V + E))$. Is there a faster way?

Answer 1

For a DAG, a simple linear-time algorithm is all that is needed.

First, prune all vertices not reachable either from $s$ or to $t$. Let $G' = (V', E')$ be the pruned graph. Then, compute any topological ordering $\pi$ of $G'$.

Let $(u, v) \in E'$ be an edge. I assert the edge $(u, v)$ is a bottleneck if and only if $\pi(u) + 1 = \pi(v)$ and there doesn't exist any other edge which interval contains $[\pi(u), \pi(v)]$ in the topological ordering. The latter condition can be checked for all edges in linear total-time by maintaining the number of edges containing the current vertex, in the topological order (+1 at the start vertex of each edge, and -1 at the end vertex of each edge).

We have $\mathsf{Bottleneck}(G) = \mathsf{Bottleneck}(G')$. For each $x \in V'$, arbitrary paths from $s$ to $x$ and $x$ to $t$ are denoted by $s_x$ and $t_x$, respectively (both exist because of the pruning). I use the symbol ($\circ$) to denote the composition of the paths.

Indeed, if we have $\pi(u) + 1 < \pi(v)$, then there exists a vertex $w \in V'$ such that $\pi(u) < \pi(w) < \pi(v)$, and the path $s_w \circ t_w$ cannot use the edge $(u,v)$. Or, if we have another edge $(x,y)$ such that $\pi(x) \le \pi(u) \lt \pi(v) \le \pi(y)$, the path $s_x \circ (x, y) \circ t_y$ doesn't use the edge $(u,v)$.

The converse is also true because if the edge is removed we obtain a cut $(\{x \mid \pi(x) \le \pi(u)\}, \{x \mid \pi(v) \le \pi(x)\})$.

Answer 2

Compute the dominator tree of the flow graph $(G,s)$, i.e., the graph $G$ with source node $s$. Let $s=v_0,v_1,\dots,v_{k-1},v_k=t$ be the sequence of nodes in the path from $s$ to $t$ in the dominator tree. Check each pair $(v_i,v_{i+1})$ of consecutive nodes in this sequence; if it is an edge of $G$, it is visited on every $s,t$-path, so output it. It is possible to see that this enumerates all such edges.

The running time is nearly linear time. It is possible to compute the dominator tree in nearly linear time, and then the rest of the algorithm clearly runs in linear time. In particular, the Lengauer-Tarjan algorithm computes the dominator tree in $O(E \alpha(E,V))$ time, where $\alpha(E,V$) is an inverse Ackerman's function -- thus nearly linear. There is also an $O(V+E)$ time algorithm by Buchsbaum, Kaplan, Rogers, and Westbrook and by Georgiadis and Tarjan, but it is more complex to implement in practice. If you are interested in ease of implementation, you might also be interested in work by Cooper, Harvey, and Kennedy.