# 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.

• One optimisation that might get rid of many founded edges quickly: Run a BFS from some source node $r$, and discard every edge $uv$ for which $d(r, v) = d(r, u) + 1$ -- all such edges strictly increase the distance from $r$. Optionally repeat for other source nodes if edges remain. You will still need to check each edge $uv$ that remains (by, e.g., reversing all edge directions, deleting $v$, and running a DFS from $u$ to see if any source is reachable). – j_random_hacker Apr 2 '20 at 19:22
• Two improvements: (1) Whenever the BFS encounters another source node, do not add any of its out-edges to the queue. Running this modified BFS from all source vertices is as good as running the original BFS from all source vertices, but now takes only $O(|E|)$ total time :-) (2) In the absence of self-loops, you can also delete edges $uv$ for which $d(r, u) = d(r, v)$, since there must exist some path of strictly increasing-distance vertices from $r$ to $u$, and the final edge cannot point back to itself or any of these earlier vertices. – j_random_hacker Apr 2 '20 at 19:48

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