16

Enumerating all simple paths between two vertices in an arbitrary graph takes exponential time in general, because there may be an exponential number of simple paths between the vertices. But what about if we're only interested in the vertices that are on at least one simple path between the two end vertices?

That is: Given an undirected graph and two distinct vertices, is there a polynomial-time algorithm which finds every vertex which is on at least one simple path between the two vertices? This is not the same as connectivity; dead-ends and cul-de-sacs are excluded. Branching and joining paths, however, are permissible.

I've found that it's very easy to write an algorithm which looks like it solves this problem, but either fails in some case, or takes exponential running time in pathological cases.

More generally: Given two disjoint sets of vertices in a graph, is there a polynomial-time algorithm which finds all vertices which lie on a simple path from a vertex in one set to a vertex in the other set?

(Forgive me if there's a really obvious solution to this. It certainly feels like there should be.)

5
  • You could possibly modify Floyd-Warshall for the first problem. It's n^3. Just keep track off the vertices as you go through it, then see which other vertices have a path to both the target and source.
    – Jan Gorzny
    May 30, 2012 at 22:42
  • You should consider posting this kind of question to the new computer science stackexchange site.
    – hugomg
    May 30, 2012 at 23:48
  • @JanGorzny- The problem with that approach is that this will only tell you if there's a shortest path in a subgraph that goes through those nodes. I might have a node on a non-shortest path in some subgraph that would get skipped over. May 31, 2012 at 0:18
  • @templatetypedef but then you could cycle through all nodes (assuming you have a list, in linear time in the size of the nodes) and check each one if there is SOME shortest path to both (and you could rule out cases where at least one of those paths use the two designated nodes--though this would require storing a lot of information). Ultimately I concede it's not perfect, but I thought it might be a starting point!
    – Jan Gorzny
    May 31, 2012 at 0:57
  • Of course, any polynomial-time solution to the two-ends problem implies a polynomial-time solution to the N-ends problem, since you can just union the results from all pairs of vertices in the two sets. My question only requested polynomial-time, not asymptotically optimal. There could be a faster algorithm for N-ends, though. May 31, 2012 at 1:25

2 Answers 2

18

Here is a linear-time deterministic solution. Inserting an edge between your two end vertices (let's call them a and b), if such an edge doesn't already exist, turns your problem into the problem of finding a maximum set of vertices v that lie on any simple cycle through a and b. You can convince yourself that such a set corresponds to the maximal subgraph containing a and b that cannot be disconnected by removal of any of its nodes (also called biconnected component). This page describes the concept and the classic linear-time (DFS-based) algorithm of Hopcroft and Tarjan to identify all biconnected components (you only need the one containing a and b).

Your second question about simple paths between two sets (let's call them A and B) can reduced to the first question by creating a new vertex a with edges to all vertices in A, and a vertex b with edges to all vertices in B, and then solving your first question for a and b.

2
2

Do you mind a probabilistic solution? That is, it won't guarantee finding all of the vertices, but it usually does first try, and is overwhelmingly likely to after 2 or 3 tries?

If you're OK with that, randomly assign every edge a resistance, and solve for the voltages of every node if you put the source at a voltage of 1 and the sink at a voltage of 0. Any edge where the two nodes connecting it are at different voltages is clearly on a simple path (the path is easy to construct, just go through ascending voltages from one end, and descending from the other). An edge where the two nodes connecting it are at the same voltage is extremely unlikely to be on a simple path, though that theoretically can happen.

Repeat with several randomly assigned sets of resistances, and you're overwhelmingly likely to have found all edges that are on simple paths. (You haven't proven this answer, but the odds of being wrong are vanishingly small.)

Of course once you know all of the edges that are on simple paths, it is trivial to get all of the vertices that are on simple paths.

Update

I believe that the following is true, but have no proof. Suppose that we take a set of resistances and work out voltages. For every edge which is in a simple path, there is another edge (maybe the same) such that varying the resistance of only that edge will cause the voltage across the first edge to vary. If so, it is possible in polynomial time to identify every edge in a simple path.

Intuitively it makes sense to me, but I have no idea how I would prove it.

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.