Find all *vertices* on all simple paths between two vertices in an undirected graph

Question

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

Answer 1

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.