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.

  • $\begingroup$ 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). $\endgroup$ – j_random_hacker Apr 2 '20 at 19:22
  • $\begingroup$ 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. $\endgroup$ – 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$.)

  • $\begingroup$ This seems promising, thank you! I'll verify whether this works. It's interesting to see a relationship to control flow graphs (the graphs in my problem domain are data dependency graphs). $\endgroup$ – ecl3ctic Apr 6 '20 at 7:44
  • $\begingroup$ You're welcome :) $\endgroup$ – j_random_hacker Apr 6 '20 at 9:01

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.