Graph algorithm to find all subgraphs that connect N arbitrary vertices - MathOverflow

Graph algorithm to find all subgraphs that connect N arbitrary vertices

2010-04-28T18:01:15Z

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

Answer by Tony Huynh for Graph algorithm to find all subgraphs that connect N arbitrary vertices

2010-04-28T18:46:17Z

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

Answer by Ondra for Graph algorithm to find all subgraphs that connect N arbitrary vertices

2011-07-14T14:28:39Z

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.