Subgraphs of bounded tree-width and preserving edges of original graph - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T12:00:04Z http://mathoverflow.net/feeds/question/91503 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/91503/subgraphs-of-bounded-tree-width-and-preserving-edges-of-original-graph Subgraphs of bounded tree-width and preserving edges of original graph David Harris 2012-03-18T02:01:17Z 2012-03-18T02:01:17Z <p>Given a graph \$G\$, I would like to determine a method for randomly generating subgraphs \$G'\$ with the following properties:</p> <ol> <li><p>Each edge of \$G\$ has at least some probability \$p\$ of going into \$G'\$</p></li> <li><p>The tree-width of \$G'\$ is bounded.</p></li> </ol> <p>I would like to find a method of generating \$G'\$ so that \$p\$ is as large as possible. Note that any \$p = 1/n\$ is possible. if you select a random spanning tree. Are there larger values of \$p\$ which are possible to achieve?</p>