Graph algorithm to find all subgraphs that connect N arbitrary vertices

I have an graph with the following attributes:

• Undirected
• Not weighted
• Each vertex has a minimum of 2 and maximum of 6 edges connected to it.
• Vertex count will be < 100
• Graph is static and no vertices/edges can be added/removed or edited.

I'm looking for all subgraphs between a random subset of the vertices (at least 2).

I've created a (warning! programmer art) animated gif to illustrate what i'm trying to achieve: http://imgur.com/mGVlX.gif

My end goal is to have a set of subgraphs that allow moving from one of the subset vertices (blue nodes) and reach any of the other subset vertices (blue nodes).

-

It looks like the paper

Generating all the Steiner trees and computing Steiner intervals for a fixed number of terminals

by Costa Dourado, de Oliveira, and Protti is what you want (available from ScienceDirect). I think the paper gives an algorithm for generating all the minimal (under subgraph inclusion) subgraphs connecting the blue vertices (from which it is easy to obtain all such subgraphs).

-
My understanding was that Steiner trees introduce intermediate vertices and edges? My graph is fixed, does this algorithm give the subgraphs without adding vertices or edges? – russtbarnacle Apr 28 2010 at 20:21
You're a little vague on exactly what kind of subgraphs you're looking for, but the examples in your image seem to be including intermediate vertices. – Dylan Thurston Apr 28 2010 at 20:29
I'm rapidly moving out of my depth it appears but my understanding was that Steiner trees create vertices that would not of been in the original graph. Is a Steiner node (in relation to graphs) in fact any node that is in the original graph but not a terminal node? – russtbarnacle Apr 28 2010 at 21:49
Given a graph G and a subset of terminal vertices X of G, a Steiner tree is a connected subgraph of G which contains X. Thus, you simply want to enumerate all Steiner trees where X is your set of blue vertices. And yes, the Steiner nodes are nodes in the original graph which are not terminal nodes. – Tony Huynh Apr 28 2010 at 23:12
russtbarnacle, a Steiner tree in geometry is a slightly different concept than a Steiner tree in a graph, and what you're looking for is indeed a Steiner tree in a graph. (The Wikipedia page on Steiner trees describes both.) – Andrew D. King Oct 26 2010 at 3:40

I am not sure whether you are looking only for (cardinality) minimal such subgraphs -those are Steiner trees - or for all subgraph connecting selected vertices - you can expect to have an incredible amount of such graphs. The paper cited is wrong (but not that hard to repair) and claims to enumerate all Steiner subgraph.

-