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