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