Note:
Quite similar to my previously posted question. This time however, the graph is undirected.
Given
- An undirected graph $G$ with no multiple-edges or loops,
- A source vertex $s$,
- A target vertex $t$,
- Maximal path length $l$,
I am looking for $G'$ - A subgraph of $G$ that contains any vertex and any edge in $G$ (and only those), that are part of at least one simple path from $s$ to $t$ with length $\leq l$.
Note that I don't need to enumerate the paths.
Finding the nodes of $G'$ is fast:
- Generate $G_1$:
(a) Any vertex that its distance from s is up to $\lceil \frac{l}{2}\rceil$, and any edge along a path from $s$ to this vertex.
(b) Any vertex that its distance from t is up to $\lfloor \frac{l}{2}\rfloor$, and any edge along a path from $t$ to this vertex.
- Add an edge between $s$ and $t$ (if such edge doesn't exist)
- Construct $G'$: Find the biconnected component in $G_1$ that contains $s$ and $t$ (linear-time, DFS-based). (see here)
All $G'$ nodes are on at least one simple $s$-$t$ path with length $\leq l$, but not necessarily all of its edges are.
- For each edge $uv$ in $G'$ check if it is on a simple path with length $\leq l$: that is, if $d(s,u)+1+d(v,t) \leq l$ or $d(s,v)+1+d(u,t) \leq l$, where $d(x,y)$ are shortest path distance between $x$ and $y$.
This last step is expensive $O(V^3)$ (Moreover, I'm not convinced that it won't find non-simple paths). I wonder if there is a better solution.
