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

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