13
$\begingroup$

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

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).
Improve this question
$\endgroup$
1
  • $\begingroup$ check this out. Found this 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. $\endgroup$
    – R B
    Commented Apr 2, 2014 at 15:50

3 Answers 3

Reset to default
6
+50
$\begingroup$

Well, the problem is in $P$ after all. I'll keep the previous answer 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 (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.
Improve this answer
$\endgroup$
7
  • 1
    $\begingroup$ 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$. $\endgroup$
    – Chandra Chekuri
    Commented Mar 29, 2014 at 21:27
  • $\begingroup$ @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 $\endgroup$
    – R B
    Commented Mar 29, 2014 at 22:08
  • $\begingroup$ 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. $\endgroup$
    – Chandra Chekuri
    Commented Mar 30, 2014 at 2:07
  • $\begingroup$ @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. $\endgroup$
    – Lior Kogan
    Commented Mar 31, 2014 at 6:34
  • 1
    $\begingroup$ 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. $\endgroup$
    – Chandra Chekuri
    Commented Apr 1, 2014 at 14:19
1
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 3
    $\begingroup$ 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$... $\endgroup$
    – R B
    Commented Mar 29, 2014 at 20:30
  • $\begingroup$ Thanks for the correction @RB. I edited my answer to note that it's wrong. $\endgroup$
    – greg
    Commented Apr 1, 2014 at 13:22
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.