9
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • $\begingroup$ 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? $\endgroup$
    – Sacha
    Commented Dec 21, 2010 at 13:23
  • $\begingroup$ I randomly add and remove edges. $\endgroup$
    – Arman
    Commented Dec 21, 2010 at 13:37
  • $\begingroup$ Could you sample random shortest path spanning trees instead? It simplifies things $\endgroup$
    – Yaroslav Bulatov
    Commented Dec 21, 2010 at 23:10
  • $\begingroup$ 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 (en.wikipedia.org/wiki/Euclidean_minimum_spanning_tree). It has a running time of $O(n\log n)$ with $O(n)$ of space. $\endgroup$
    – Marcos Villagra
    Commented Dec 22, 2010 at 0:57
  • $\begingroup$ 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. $\endgroup$
    – Jagadish
    Commented Dec 22, 2010 at 20:00

3 Answers 3

Reset to default
7
$\begingroup$

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.

Improve this answer
$\endgroup$
1
3
$\begingroup$

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. There is a newer (approximation) algorithm 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.

Improve this answer
$\endgroup$
0
1
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Arman
    Commented Dec 22, 2010 at 9:58
  • $\begingroup$ Then your problem is almost certainly NPC by reduction from Degree Constrained Spanning Tree - en.wikipedia.org/wiki/Degree-constrained_spanning_tree $\endgroup$
    – Peter Boothe
    Commented Dec 23, 2010 at 7:01

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.