Welcome to MathOverflow

Question

1

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

flag	asked Apr 28 2010 at 18:01 russtbarnacle 13●3

Tony Huynh · Accepted Answer · 2010-10-25 21:04:09Z UTC

4

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

edited Oct 25 2010 at 21:04

answered Apr 28 2010 at 18:46

Tony Huynh
8,963●1●22●62

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

1

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

Ondra · Answer 2 · 2011-07-14 14:28:39Z UTC

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.

Graph algorithm to find all subgraphs that connect N arbitrary vertices

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

2 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.