Graph algorithm to find all subgraphs that connect N arbitrary vertices - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T04:52:35Z http://mathoverflow.net/feeds/question/22884 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/22884/graph-algorithm-to-find-all-subgraphs-that-connect-n-arbitrary-vertices Graph algorithm to find all subgraphs that connect N arbitrary vertices russtbarnacle 2010-04-28T18:01:15Z 2011-07-14T14:28:39Z <p>I have an graph with the following attributes:</p> <ul> <li>Undirected</li> <li>Not weighted </li> <li>Each vertex has a minimum of 2 and maximum of 6 edges connected to it. </li> <li>Vertex count will be &lt; 100</li> <li>Graph is static and no vertices/edges can be added/removed or edited.</li> </ul> <p>I'm looking for <strong>all</strong> subgraphs between a random subset of the vertices (at least 2). </p> <p>I've created a (warning! programmer art) animated gif to illustrate what i'm trying to achieve: <a href="http://imgur.com/mGVlX.gif" rel="nofollow">http://imgur.com/mGVlX.gif</a></p> <p>My end goal is to have a set of subgraphs that allow moving from one of the subset vertices (blue nodes) and reach <strong>any</strong> of the other subset vertices (blue nodes).</p> http://mathoverflow.net/questions/22884/graph-algorithm-to-find-all-subgraphs-that-connect-n-arbitrary-vertices/22888#22888 Answer by Tony Huynh for Graph algorithm to find all subgraphs that connect N arbitrary vertices Tony Huynh 2010-04-28T18:46:17Z 2010-10-25T21:04:09Z <p>It looks like the paper </p> <p><em>Generating all the Steiner trees and computing Steiner intervals for a fixed number of terminals</em> </p> <p>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 <em>minimal</em> (under subgraph inclusion) subgraphs connecting the blue vertices (from which it is easy to obtain all such subgraphs). </p> http://mathoverflow.net/questions/22884/graph-algorithm-to-find-all-subgraphs-that-connect-n-arbitrary-vertices/70329#70329 Answer by Ondra for Graph algorithm to find all subgraphs that connect N arbitrary vertices Ondra 2011-07-14T14:28:39Z 2011-07-14T14:28:39Z <p>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. </p>