MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Given a graph $G$, I would like to determine a method for randomly generating subgraphs $G'$ with the following properties:

  1. Each edge of $G$ has at least some probability $p$ of going into $G'$

  2. The tree-width of $G'$ is bounded.

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?

share|cite|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.