<p>I was working on bounded-depth spanning trees a few years ago, they're really interesting.  Some of my colleagues came up with message passing algorithms that did a great job, but I can't find any of their code available.  We wrote it up in a physics style here:  <a href="http://iopscience.iop.org/1742-5468/2009/12/P12010/" rel="nofollow">http://iopscience.iop.org/1742-5468/2009/12/P12010/</a>.  They've told me that it also works with degree bounds, although that didn't make it into the paper.</p>

<p>The approach you propose, which I would call Markov Chain Monte Carlo, is often a competitor to the message passing approach.  If you are interested in sampling approximately uniformly at random from the set of bounded-degree, bounded-depth spanning trees of a given graph, I suggest altering your approach to use "soft" bounds.  I.e. instead of rejecting an edge swap that makes the tree violate the depth bound, accept it, but with lower probability than a swap which does not violate the bound.  If you have a parameter that controls how much lower this probability is, you can make the constraint violating configurations less and less probable until you arrive at a feasible solution that is nearly uniformly random.</p>

<p>The big question is how long do you need to run the chain.  Since a spanning tree with degree at most 2 is a Hamiltonian path, you should expect any generic bound to be exponential in the size of the graph.  But maybe the graphs you are interested in are special in some way.</p>

CC BY-SA 2.5
2010-12-23T19:45:35.300Z
More details, plus a movie: http://healthyalgorithms.wordpress.com/2010/12/23/mcmc-in-python-custom-stepmethods-and-bounded-depth-spanning-tree-distraction
Abraham Flaxman
CC BY-SA 2.5
2010-12-23T04:34:43.460Z
2010-12-23T04:34:43.460Z
Abraham Flaxman
<p>If your problem is to uniformly sample a spanning tree from a set $S$, where $S$ is the set of all spanning trees of hight at most $h$, for some input $h$, then your strategy works (i.e., sample a random spanning tree and check if it's hight is at most $h$). </p>

<p>However, I'm not sure if the algorithm you described will generate a random spanning tree. I would recommend looking at standard algorithms instead. There are two algorithms: Wilson's algorithm and Aldous-Broder's algorithm. You can have a look <a href="http://www.maths.bath.ac.uk/~aj276/teaching/USF/USFnotes.pdf" rel="nofollow">here</a>. There is a newer (approximation) <a href="http://people.csail.mit.edu/madry/docs/randtreegen_full.pdf" rel="nofollow">algorithm</a> but it is quite complicated. </p>

<p>Also, there might be a way to generate this spanning tree with bounded hight directly. But I've never heard of such algorithms. </p>

CC BY-SA 2.5
2010-12-22T08:46:53.970Z
2010-12-22T08:46:53.970Z
Dan
<p>Use breadth-first search!  Do a BFS from every vertex in the graph, choose the resulting tree of smallest height.  A BFS always finds the path from the root to every other vertex with the fewest hops.</p>

CC BY-SA 2.5
2010-12-22T09:58:03.020Z
You are definitely right. We started doing with BFS but it did not work because of degree constraint on the vertices. I forgot to mention about this constraint (my mistake): the degree of the vertices in the tree generated should also be bounded. Your answer is correct with the current question but I think I should edit my question.
Arman
CC BY-SA 2.5
2010-12-23T07:01:51.940Z
Then your problem is almost certainly NPC by reduction from Degree Constrained Spanning Tree - http://en.wikipedia.org/wiki/Degree-constrained_spanning_tree
Peter Boothe
CC BY-SA 2.5
2010-12-21T23:10:30.307Z
2010-12-21T23:10:30.307Z
Peter Boothe
<p>For a project that I am working on, I should generate random spanning trees with bounded height. </p>

<p>Basically I do the following:
1) Generate a spanning tree
2) Check the feasibility, if feasible keep it.</p>

<p>1) Starting from a minimum spanning tree (Prim's or Kruskal's) I add a non-existing edge and this creates a cycle, I detect this cycle and remove one of the edges of this cycle that gives me a new spanning tree and I continue with this spanning tree by adding a new edge...  </p>

<p>2) Suppose there is a special vertex $v_{center}$. For every vertex $v$, the length of the path from $v$ to $V_{center}$ should be less then $\delta$, where $\delta$ is a given parameter.</p>

<p>Is there any better(clever) way of doing this?</p>

<p>P.S. I forgot to specify the other constraint (my mistake): the degree of the vertices should also be bounded.</p>

CC BY-SA 2.5
2010-12-21T13:23:06.080Z
I’m not sure if I get this right. In the first step, do you remove the edge just randomly or so that the height of the tree is (possibly) reduced?
Sacha
CC BY-SA 2.5
2010-12-21T13:37:46.880Z
I randomly add and remove edges.
Arman
CC BY-SA 2.5
2010-12-21T23:10:40.317Z
Could you sample random *shortest path* spanning trees instead? It simplifies things
Yaroslav Bulatov
CC BY-SA 2.5
2010-12-22T00:57:43.817Z
do you have any cost on the edges? are you looking for a spanning tree with height $\delta$ and minimum cost? As @pboothe wrote, you can use BFS and that's it. The only problem is that BFS uses too much memory. If you care about costs, you can try the algorithm in wikipedia for euclidean minimum spanning trees (http://en.wikipedia.org/wiki/Euclidean_minimum_spanning_tree). It has a running time of $O(n\log n)$ with $O(n)$ of space.
Marcos Villagra
CC BY-SA 2.5
2010-12-22T20:00:39.440Z
So your problem has three bounded quantities: height of the tree, degree of each vertex and distance from v_center, is that right? Just the bounded degree constraint itself makes the problem NP-hard, but I suppose you're looking for a method that is likely to produce a solution quickly and not an exact algorithm.
Jagadish
CC BY-SA 2.5
2010-12-22T20:25:12.497Z
@Jagadish, exactly. The height of the tree is minimized when we start BFS from v_center. Now the problem is to satisfy degree constraint without too much increasing the height.
Arman
<ds.algorithms><graph-algorithms><random-walks>
How can I randomly generate bounded height spanning trees?
Arman
# How can I randomly generate bounded height spanning trees?

(Asked by: username_0 on 2010-12-21)

For a project that I am working on, I should generate random spanning trees with bounded height.

Basically I do the following:
1) Generate a spanning tree
2) Check the feasibility, if feasible keep it.

1) Starting from a minimum spanning tree (Prim's or Kruskal's) I add a non-existing edge and this creates a cycle, I detect this cycle and remove one of the edges of this cycle that gives me a new spanning tree and I continue with this spanning tree by adding a new edge...

2) Suppose there is a special vertex $v\_{center}$. For every vertex $v$, the length of the path from $v$ to $V\_{center}$ should be less then $\delta$, where $\delta$ is a given parameter.

Is there any better(clever) way of doing this?

P.S. I forgot to specify the other constraint (my mistake): the degree of the vertices should also be bounded.

**Tags:** ds.algorithms, graph-algorithms, random-walks

> **Comments:**
> **username_1**: I’m not sure if I get this right. In the first step, do you remove the edge just randomly or so that the height of the tree is (possibly) reduced?  
> **username_0**: I randomly add and remove edges.  
> **username_2**: Could you sample random *shortest path* spanning trees instead? It simplifies things  
> **username_3**: do you have any cost on the edges? are you looking for a spanning tree with height $\delta$ and minimum cost? As @pboothe wrote, you can use BFS and that's it. The only problem is that BFS uses too much memory. If you care about costs, you can try the algorithm in wikipedia for euclidean minimum spanning trees (http://en.wikipedia.org/wiki/Euclidean_minimum_spanning_tree). It has a running time of $O(n\log n)$ with $O(n)$ of space.  
> **username_4**: So your problem has three bounded quantities: height of the tree, degree of each vertex and distance from v_center, is that right? Just the bounded degree constraint itself makes the problem NP-hard, but I suppose you're looking for a method that is likely to produce a solution quickly and not an exact algorithm.  
> **username_0**: @username_4, exactly. The height of the tree is minimized when we start BFS from v_center. Now the problem is to satisfy degree constraint without too much increasing the height.  

---

## 3 answers

### Answer by username_5 on 2010-12-23. Score: 7 | Accepted answer

I was working on bounded-depth spanning trees a few years ago, they're really interesting. Some of my colleagues came up with message passing algorithms that did a great job, but I can't find any of their code available. We wrote it up in a physics style here: <http://iopscience.iop.org/1742-5468/2009/12/P12010/>. They've told me that it also works with degree bounds, although that didn't make it into the paper.

The approach you propose, which I would call Markov Chain Monte Carlo, is often a competitor to the message passing approach. If you are interested in sampling approximately uniformly at random from the set of bounded-degree, bounded-depth spanning trees of a given graph, I suggest altering your approach to use "soft" bounds. I.e. instead of rejecting an edge swap that makes the tree violate the depth bound, accept it, but with lower probability than a swap which does not violate the bound. If you have a parameter that controls how much lower this probability is, you can make the constraint violating configurations less and less probable until you arrive at a feasible solution that is nearly uniformly random.

The big question is how long do you need to run the chain. Since a spanning tree with degree at most 2 is a Hamiltonian path, you should expect any generic bound to be exponential in the size of the graph. But maybe the graphs you are interested in are special in some way.

> **Comments:**
> **username_5**: More details, plus a movie: http://healthyalgorithms.wordpress.com/2010/12/23/mcmc-in-python-custom-stepmethods-and-bounded-depth-spanning-tree-distraction  

---

### Answer by username_6 on 2010-12-22. Score: 3

If your problem is to uniformly sample a spanning tree from a set $S$, where $S$ is the set of all spanning trees of hight at most $h$, for some input $h$, then your strategy works (i.e., sample a random spanning tree and check if it's hight is at most $h$).

However, I'm not sure if the algorithm you described will generate a random spanning tree. I would recommend looking at standard algorithms instead. There are two algorithms: Wilson's algorithm and Aldous-Broder's algorithm. You can have a look [here](http://www.maths.bath.ac.uk/~aj276/teaching/USF/USFnotes.pdf). There is a newer (approximation) [algorithm](http://people.csail.mit.edu/madry/docs/randtreegen_full.pdf) but it is quite complicated.

Also, there might be a way to generate this spanning tree with bounded hight directly. But I've never heard of such algorithms.


---

### Answer by username_7 on 2010-12-21. Score: 1

Use breadth-first search! Do a BFS from every vertex in the graph, choose the resulting tree of smallest height. A BFS always finds the path from the root to every other vertex with the fewest hops.

> **Comments:**
> **username_0**: You are definitely right. We started doing with BFS but it did not work because of degree constraint on the vertices. I forgot to mention about this constraint (my mistake): the degree of the vertices in the tree generated should also be bounded. Your answer is correct with the current question but I think I should edit my question.  
> **username_7**: Then your problem is almost certainly NPC by reduction from Degree Constrained Spanning Tree - http://en.wikipedia.org/wiki/Degree-constrained_spanning_tree  

---

