Efficiently finding "unfounded edges" in a strongly connected graph While implementing a debugger I've encountered a problem I need to solve concerning dependency graphs. I've simplified it as follows:

Consider a strongly connected graph G = (V,E).


We define a subset of vertices S ⊆ V as source vertices.
We call an edge e = (a,b) unfounded if there is no simple path from any source vertex to b that includes e. In other words, all paths from a source vertex that include edge e, must include vertex b at least twice.


The problem:


Find all unfounded edges in G.


There are some obvious ways to solve this inefficiently (e.g. a depth-first traversal for each edge in G), but I was wondering if there was any O(|E|) approach. I've been struggling with this for a while and I keep "almost" solving it in linear time. Perhaps that's impossible? I have no idea what the lower bound on efficiency is, and I was hoping some readers here could help me discover some efficient approaches.

An illustrative example is a simple 3-cycle.  Pick any one vertex as the source vertex. The edge coming into the source vertex is unfounded.
I believe that computing graph dominators will solve your problem. This can be done in $O(|E|\log |V|)$ time (or even faster, though they describe the faster algorithm as "sophisticated") using a 1979 algorithm by Lengauer and Tarjan, which is (at least currently) described here (21 pages -- I have only read the first few pages myself).

Add a new "start" node with an out-edge to every source node, run the dominator algorithm to determine dominators for every node, and then check each edge $uv$: $uv$ is unfounded if and only if $v$ dominates $u$. (Each of these checks can be done in constant time using a lowest common ancestor (LCA) algorithm, although that may be overkill here -- for an edge $uv$, we only care about whether or not $LCA(u, v) = v$.)