<p>Well, the problem is in $P$ after all.
I'll keep the <a href="https://cstheory.stackexchange.com/questions/20137/subgraph-containing-all-nodes-and-edges-that-are-part-of-length-limited-simple-s/21861#21861">previous answer</a> as it also works for the directed case (which is NPC, as answered on the other question), and shows it is $FPT$ with respect to $l$.</p>

<p>In the undirected case, it is solvable, deterministically via <a href="http://en.wikipedia.org/wiki/Minimum-cost_flow_problem" rel="nofollow noreferrer">minimum cost flow</a> (this might not work on the scales you are referring to in the question, but its better than exponential algorithm.</p>

<p>The following procedure will decide whether some edge $e=(u,v)\in E$ should be a part of the output graph. In order to answer the original problem just loop over all edges.</p>

<p>In order to create the flow network, do as follows:</p>

<p>Step 1:
Expand $e$ to have a vertex $x_e$ and replace $e$ with the edges $(u,x_e),$$(x_e,u),(v,x_e),(x_e,v)$  (they are directed as a part of the flow network), set their cost to 0.</p>

<p>Step 2: replace every vertex $t$, except for $x_e$ by two vertices $t^-$ and $t^+$, and add an edge $(t^-,t^+)$. Set the cost of these edges to 1.</p>

<p>Step 3: Replace of every edge $\{a,b\}\in E$ with the edges $(a^+,b^-),(b^+,a^-)$. Set the cost of these edges to 0.</p>

<p>Step 4: Add a new vertex $y_e$ and add the edges $(s,y_e),(t,y_e)$ with cost 0.</p>

<p>Step 5: set all capacities to 1.</p>

<p>Now run the min cost flow algorithm, searching for a flow of value 2 from $x_e$ to $y_e$.</p>

<hr>

<p>Analysis:</p>

<ul>
<li>Every 2-valued flow from $x_e$ to $y_e$ is a union of a path $x_e\leadsto s\to y_e$ and a path $x_e\leadsto t\to y_e$. </li>
<li>The paths are disjoint, since for every vertex $t$ there's only 1 capacity in the $(t^-,t^+)$ arc.</li>
<li>The returned paths are the two paths whose sum of distances is minimal, and that's also the cost of the found flow. This allows us to add $e$ to the output graph or delete otherwise.</li>
</ul>

CC BY-SA 3.0
2014-03-29T21:27:23.890Z
It is easier to understand the argument in the above answer by stripping away the reduction to directed flow. There is a simple path from $s$ to $t$ containing a node $v$ iff there is a path $P$ from $v$ to $s$ and a path $Q$ from $v$ to $t$ such that $P$ and $Q$ are node disjoint except at $v$. This crucially uses the undirectedness. This can be checked via flow and the cost version can also be done via min-cost flow. One can check whether there is a simple path from $s$ to $t$ containing $e$ by introducing a node in the middle of $e$.
Chandra Chekuri
CC BY-SA 3.0
2014-03-29T22:08:16.297Z
@ChandraChekuri - that is correct, but keep in mind that if the problem doesn't have the length constraint, there's a lot simpler algorithm for deciding it - [see here](http://stackoverflow.com/questions/10825249/find-all-vertices-on-all-simple-paths-between-two-vertices-in-an-undirected-gr)
R B
CC BY-SA 3.0
2014-03-30T02:07:31.960Z
Sure, I am aware of that solution too - conceptually it is good to understand biconnected components via disjoint paths even though one can find cut-vertices and biconnected components directly via DFS.
Chandra Chekuri
CC BY-SA 3.0
2014-03-31T06:34:00.830Z
@RB: Thank you. The suggested algorihm may be effective when l is relatively large, but it is probably suboptimal for relatively small values of l. I guess I can trim G first by removing any vertex farther than floor(l/2) from s and ceil(l/2) from t.
Lior Kogan
CC BY-SA 3.0
2014-03-31T06:42:36.840Z
@RB: Is there some preprocessing that would allow us not to run a full min cost flow algorithm |E| times?
Lior Kogan
CC BY-SA 3.0
2014-03-31T09:24:59.933Z
@LiorKogan - if you wish to implement it in practice, try the following trick:

Assume that for some $e\in E$ the cost of the flow ( / the length of the shortest s-t path that includes $e$) is $l'\leq l$.

1. All of the edges on the found path are a part of the output graph.
2. Pick a short subpath (of length, say, 1-3), $y$ such that the original path was $P=x\cdot y\cdot z$. Delete $y$ and search for a path/s that connect $x$ with $z$.

3.Repeat for multiple $y$'s. This should create create a "tunnel" of edges around $P$ which need not be examined by themselves.
R B
CC BY-SA 3.0
2014-04-01T14:19:59.633Z
Try adapting the successive shortest path algorithm (also called Surballe's algorithm for the case of 2 paths which is of interest here). You want to find shortest 2-paths from $y$ (it is better to call it $y$ instead of $y_e$ since it is the same for all edges) to every $x_e$. I think this is doable efficiently by first computing a shortest path tree from $y$ and then implementing the second path computation with some care.
Chandra Chekuri
CC BY-SA 3.0
2014-03-29T15:04:19.630Z
2014-04-08T11:43:35.990Z
2017-04-13T12:32:28.053Z
R B
<p>This is intended as a comment, but it's too long to post as a comment.</p>

<p>You might also be interested in graph spanners or emulators for your purposes.  A <em>spanner</em> of a graph $G = (V, E)$ is a subgraph $H = (V, E')$ with few edges, but approximately preserved distances.  An emulator is a graph $H = (V, E', w)$ whose edges are allowed to be weighted.</p>

<p>The best result for spanners is $O(n^{4/3})$ edges and an additive error of +6 on distance estimates in the graph.  The best result for emulators is $O(n^{4/3})$ edges and an additive error of +4.  It is not known for either if we can beat $O(n^{4/3})$, even if the error is allowed to be polylogarithmic.</p>

<p>If this sounds useful, I can try and dig up the relevant constructions for you.</p>

CC BY-SA 3.0
2014-04-01T15:32:03.660Z
2014-04-01T15:32:03.660Z
GMB
<p>Here is a <strong>wrong</strong> answer: it outputs some vertices that are part of non-simple paths from $s$ to $t$ and that are not a part of any simple path from $s$ to $t$ of length $\le \ell$. The answer might still be relevant to the asker's application, so I'm leaving it here.</p>

<p>Here is an algorithm that runs in time $O(|V|+|E|)$ (and actually is faster than this when $\ell$ is small).</p>

<p>The algorithm runs a BFS search from $s$ that terminates at depth $\ell$. This BFS gives a set $V_s$ of all vertices reachable from $s$ with a path of length at most $\ell$, and it also computes the distances $dist(s,v)$ for each $v \in V_s$. Then I'd do the same from $t$ and get the set $V_t$ and distances from $t$. Finally, the vertices you're looking for are exactly $V_{solution}=\{ v : v \in V_s \cap V_t, dist(s,v)+dist(t,v) \le \ell \}$. The edges are exactly those edges in $E[V_{solution}]$ ($=(v,u) \in E : u,v \in V_{solution}$).</p>

<p>The running time of this algorithm is surely $O(|V|+|E|)$ because it just does two BFSs. But the running time is actually $O(|V_s| + |V_t| + |E[V_s]|+|E[V_t]|)$ which will be much smaller than the size of the graph when the $\ell$-radius neighborhoods of $s$ and $t$ are small.</p>

<p>Edit: there's probably a somewhat faster algorithm in practice that does a BFS from $s$ and $t$ of depth only $\ell/2$ rather than $\ell$. This discovers all the paths, and then with a bit of bookkeeping you can find all the vertices. This cuts the running time by a square root for the case of a large random-looking graph when $\ell$ is small.</p>

CC BY-SA 3.0
2014-03-29T20:30:05.637Z
This does not force the path to be simple. Consider the simple path graph $t-u-s-v-x$ and $l=4$. You will return $v$ as part of the output, although there's no simple s-t path that goes through $v$...
R B
CC BY-SA 3.0
2014-04-01T13:22:47.093Z
Thanks for the correction @RB. I edited my answer to note that it's wrong.
greg
CC BY-SA 3.0
2014-03-29T20:05:47.807Z
2014-04-01T13:22:09.080Z
2014-04-01T13:22:09.080Z
greg
<p>Quite similar to my <a href="https://cstheory.stackexchange.com/questions/20137/subgraph-containing-all-nodes-and-edges-that-are-part-of-length-limited-simple-s">previously posted question</a>. This time however, the graph is undirected.</p>

<p>Given </p>

<ul>
<li>An <strong>undirected</strong> graph $G$ with no multiple-edges or loops,</li>
<li>A source vertex $s$,</li>
<li>A target vertex $t$,</li>
<li>Maximal path length $l$,</li>
</ul>

<p>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$.</p>

<p>Notes:</p>

<ul>
<li>I don't need to enumerate the paths.</li>
<li>I'm looking for an efficient algorithm (both time and memory), as I need to execute it over very large graphs (10^8 vertexes, 10^9 edges).</li>
</ul>

CC BY-SA 3.0
2014-04-02T15:50:57.587Z
check this out.
Found [this](http://onlinelibrary.wiley.com/doi/10.1002/net.3230140209/pdf) paper, which seems to do a similar min cost flow reduction, but uses the special characteristics of the network to solve it faster then the general MCF algorithms.
R B
<ds.algorithms><graph-algorithms><shortest-path>
Subgraph containing all nodes and edges that are part of length-limited simple s-t paths in an undirected graph
Lior Kogan
# Subgraph containing all nodes and edges that are part of length-limited simple s-t paths in an undirected graph

(Asked by: username_0 on 2013-12-12)

Quite similar to my [previously posted question](https://cstheory.stackexchange.com/questions/20137/subgraph-containing-all-nodes-and-edges-that-are-part-of-length-limited-simple-s). 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$.

Notes:

* I don't need to enumerate the paths.
* I'm looking for an efficient algorithm (both time and memory), as I need to execute it over very large graphs (10^8 vertexes, 10^9 edges).

**Tags:** ds.algorithms, graph-algorithms, shortest-path
> **Comments:**
> **username_1**: check this out. Found [this](http://onlinelibrary.wiley.com/doi/10.1002/net.3230140209/pdf) paper, which seems to do a similar min cost flow reduction, but uses the special characteristics of the network to solve it faster then the general MCF algorithms.  

---

## 3 answers

### Answer by username_1 on 2014-03-29. Score: 6 | Accepted answer

Well, the problem is in $P$ after all.
I'll keep the [previous answer](https://cstheory.stackexchange.com/questions/20137/subgraph-containing-all-nodes-and-edges-that-are-part-of-length-limited-simple-s/21861#21861) as it also works for the directed case (which is NPC, as answered on the other question), and shows it is $FPT$ with respect to $l$.

In the undirected case, it is solvable, deterministically via [minimum cost flow](http://en.wikipedia.org/wiki/Minimum-cost_flow_problem) (this might not work on the scales you are referring to in the question, but its better than exponential algorithm.

The following procedure will decide whether some edge $e=(u,v)\in E$ should be a part of the output graph. In order to answer the original problem just loop over all edges.

In order to create the flow network, do as follows:

Step 1:
Expand $e$ to have a vertex $x\_e$ and replace $e$ with the edges $(u,x\_e),$$(x\_e,u),(v,x\_e),(x\_e,v)$ (they are directed as a part of the flow network), set their cost to 0.

Step 2: replace every vertex $t$, except for $x\_e$ by two vertices $t^-$ and $t^+$, and add an edge $(t^-,t^+)$. Set the cost of these edges to 1.

Step 3: Replace of every edge $\{a,b\}\in E$ with the edges $(a^+,b^-),(b^+,a^-)$. Set the cost of these edges to 0.

Step 4: Add a new vertex $y\_e$ and add the edges $(s,y\_e),(t,y\_e)$ with cost 0.

Step 5: set all capacities to 1.

Now run the min cost flow algorithm, searching for a flow of value 2 from $x\_e$ to $y\_e$.

---

Analysis:

* Every 2-valued flow from $x\_e$ to $y\_e$ is a union of a path $x\_e\leadsto s\to y\_e$ and a path $x\_e\leadsto t\to y\_e$.
* The paths are disjoint, since for every vertex $t$ there's only 1 capacity in the $(t^-,t^+)$ arc.
* The returned paths are the two paths whose sum of distances is minimal, and that's also the cost of the found flow. This allows us to add $e$ to the output graph or delete otherwise.

> **Comments:**
> **username_2**: It is easier to understand the argument in the above answer by stripping away the reduction to directed flow. There is a simple path from $s$ to $t$ containing a node $v$ iff there is a path $P$ from $v$ to $s$ and a path $Q$ from $v$ to $t$ such that $P$ and $Q$ are node disjoint except at $v$. This crucially uses the undirectedness. This can be checked via flow and the cost version can also be done via min-cost flow. One can check whether there is a simple path from $s$ to $t$ containing $e$ by introducing a node in the middle of $e$.  
> **username_1**: @ChandraChekuri - that is correct, but keep in mind that if the problem doesn't have the length constraint, there's a lot simpler algorithm for deciding it - [see here](http://stackoverflow.com/questions/10825249/find-all-vertices-on-all-simple-paths-between-two-vertices-in-an-undirected-gr)  
> **username_2**: Sure, I am aware of that solution too - conceptually it is good to understand biconnected components via disjoint paths even though one can find cut-vertices and biconnected components directly via DFS.  
> **username_0**: @RB: Thank you. The suggested algorihm may be effective when l is relatively large, but it is probably suboptimal for relatively small values of l. I guess I can trim G first by removing any vertex farther than floor(l/2) from s and ceil(l/2) from t.  
> **username_0**: @RB: Is there some preprocessing that would allow us not to run a full min cost flow algorithm |E| times?  
> **username_1**: @LiorKogan - if you wish to implement it in practice, try the following trick:  Assume that for some $e\in E$ the cost of the flow ( / the length of the shortest s-t path that includes $e$) is $l'\leq l$.  1. All of the edges on the found path are a part of the output graph. 2. Pick a short subpath (of length, say, 1-3), $y$ such that the original path was $P=x\cdot y\cdot z$. Delete $y$ and search for a path/s that connect $x$ with $z$.  3.Repeat for multiple $y$'s. This should create create a "tunnel" of edges around $P$ which need not be examined by themselves.  
> **username_2**: Try adapting the successive shortest path algorithm (also called Surballe's algorithm for the case of 2 paths which is of interest here). You want to find shortest 2-paths from $y$ (it is better to call it $y$ instead of $y_e$ since it is the same for all edges) to every $x_e$. I think this is doable efficiently by first computing a shortest path tree from $y$ and then implementing the second path computation with some care.  

---

### Answer by username_3 on 2014-04-01. Score: 1

This is intended as a comment, but it's too long to post as a comment.

You might also be interested in graph spanners or emulators for your purposes. A *spanner* of a graph $G = (V, E)$ is a subgraph $H = (V, E')$ with few edges, but approximately preserved distances. An emulator is a graph $H = (V, E', w)$ whose edges are allowed to be weighted.

The best result for spanners is $O(n^{4/3})$ edges and an additive error of +6 on distance estimates in the graph. The best result for emulators is $O(n^{4/3})$ edges and an additive error of +4. It is not known for either if we can beat $O(n^{4/3})$, even if the error is allowed to be polylogarithmic.

If this sounds useful, I can try and dig up the relevant constructions for you.


---

### Answer by username_4 on 2014-03-29. Score: 1

Here is a **wrong** answer: it outputs some vertices that are part of non-simple paths from $s$ to $t$ and that are not a part of any simple path from $s$ to $t$ of length $\le \ell$. The answer might still be relevant to the asker's application, so I'm leaving it here.

Here is an algorithm that runs in time $O(|V|+|E|)$ (and actually is faster than this when $\ell$ is small).

The algorithm runs a BFS search from $s$ that terminates at depth $\ell$. This BFS gives a set $V\_s$ of all vertices reachable from $s$ with a path of length at most $\ell$, and it also computes the distances $dist(s,v)$ for each $v \in V\_s$. Then I'd do the same from $t$ and get the set $V\_t$ and distances from $t$. Finally, the vertices you're looking for are exactly $V\_{solution}=\{ v : v \in V\_s \cap V\_t, dist(s,v)+dist(t,v) \le \ell \}$. The edges are exactly those edges in $E[V\_{solution}]$ ($=(v,u) \in E : u,v \in V\_{solution}$).

The running time of this algorithm is surely $O(|V|+|E|)$ because it just does two BFSs. But the running time is actually $O(|V\_s| + |V\_t| + |E[V\_s]|+|E[V\_t]|)$ which will be much smaller than the size of the graph when the $\ell$-radius neighborhoods of $s$ and $t$ are small.

Edit: there's probably a somewhat faster algorithm in practice that does a BFS from $s$ and $t$ of depth only $\ell/2$ rather than $\ell$. This discovers all the paths, and then with a bit of bookkeeping you can find all the vertices. This cuts the running time by a square root for the case of a large random-looking graph when $\ell$ is small.

> **Comments:**
> **username_1**: This does not force the path to be simple. Consider the simple path graph $t-u-s-v-x$ and $l=4$. You will return $v$ as part of the output, although there's no simple s-t path that goes through $v$...  
> **username_4**: Thanks for the correction @RB. I edited my answer to note that it's wrong.  

---

