2
$\begingroup$

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?

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.