Subgraphs of bounded tree-width and preserving edges of original graph - MathOverflow most recent 30 from http://mathoverflow.net2013-05-24T12:00:04Zhttp://mathoverflow.net/feeds/question/91503http://www.creativecommons.org/licenses/by-nc/2.5/rdfhttp://mathoverflow.net/questions/91503/subgraphs-of-bounded-tree-width-and-preserving-edges-of-original-graphSubgraphs of bounded tree-width and preserving edges of original graphDavid Harris2012-03-18T02:01:17Z2012-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>