Find every edge for which every s,t-path in a DAG goes through that edge 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 &quot;bottleneck set&quot;, 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?
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.