A New Approach To Random Spanning Trees
There is a bijective proof of Kirchhoff’s matrix theorem with applications to spanning trees
Farbod Shokrieh is one of my current PhD students, who is also being co-advised by Matt Baker of the mathematics department at Georgia Institute of Technology. Farbod has done some very pretty work, mostly on his own, on computational graph theory. In particular he has studied an abelian group that is attached to every graph, which is usually called the Jacobian of the graph.
Today I would like to discuss some of Farbod’s work as it relates to the structure of the spanning trees of a graph. I think he has discovered a very neat result about the cost of generating many random spanning trees at once.
Farbod is a delight to work with and he is likely, in my biased opinion, to have a very successful research career. He and I spent many hours trying to work on integer factoring–one of my favorite topics. He was able to show that several conjectures that I made were wrong, others are still open. The proof of these results, since they are negative, are likely to never be published. However, the proofs are hard and use quite sophisticated algebraic number theory.
This raises a question that I have often run into when working on a hard problem. If I have an approach that fails, but the reason it fails is quite interesting will anyone want to read a paper about it? I have usually guessed that the answer is no. But, perhaps we should have some mechanism for such results.
I searched and discovered the following: The Journal of Negative Results in Biomedicine. I think it not a web joke–can anyone check for me? The site says:
“The Journal of Negative Results in Biomedicine is an Open Access, peer-reviewed, online journal that promotes a discussion of unexpected, controversial, provocative and/or negative results in the context of current tenets.”
Perhaps we need “The Journal of Negative Results in Computational Complexity Theory”–what do you think?
Suppose that is a a finite, connected multigraph with no loops. Associated with each such graph is , called the Jacobian of the graph. Let be the set of spanning trees of . The group is always an abelian group, its cardinality is exactly the number of spanning trees of the graph . Elements of are represented by (equivalence classes of) integer-valued functions on the vertices of . Invariant factors and generators of can efficiently be computed.
The following theorem is due to Farbod:
Theorem: There is a bijection that maps to that is computable in polynomial time.
One can think of his theorem as the generalization of Kirchhoff’s matrix-tree theorem; the matrix-tree theorem only computes the order of the group and forgets the structure. Alternatively, his theorem gives a new bijective proof, with an efficiently computable bijection, of the matrix-tree theorem; what really is going on in the famous matrix-tree theorem is that the “magical” determinant gives the order of , and the elements of this group are in one-to-one correspondance with .
I will not explain the details of his proof–see the paper. The bijection was previously known, but it was not known how to compute the bijection in polynomial time. The difficulty was that the proofs of the bijection went like this: Given an in the group there is a natural map that associates with a labeling of the vertices with integer values. Unfortunately, it is not easy to go from this labeling to a spanning tree. However, if the labeling is in a certain “canonical form” then it is easy to find the spanning tree. Farbod’s contribution is to show how to find the canonical form in polynomial time. For those in the know, this makes contact with various combinatorial objects: chip-firing games, G-parking functions, sandpiles,
Saving Random Bits
Farbod mentions some applications of his work in his paper. One application is generating random spanning trees; as a corollary to his theorem, if one picks a random element of the group –which is a trivial task–and constructs , then one gets a random spanning tree. This yields a new and algebraic approach for sampling a random spanning tree uniformly from the set of spanning trees of the graph.
His current upper bound on the running-time of the algorithm does not beat the current best known. But there is something more going on here; unlike previous methods for generating random spanning trees, his approach actually captures the “structure” of the set of spanning trees.
For example, with this approach, it is very easy to sample multiple spanning trees with certain “joint” distribution. Here is one concrete example of what he can now do:
Theorem: Suppose that is a connected multigraph with no loops. Then, there is an algorithm that generates a family of pairwise random spanning trees of in polynomial time and uses only random bits.
The point of the theorem is that very few random bits are required to generate the pairwise spanning trees. The obvious method of generating random spanning trees would use random bits. The theorem is a huge improvement, if only pairwise randomness is required.
It is not clear to me that the usual methods for generating random spanning trees also can generate a family of pairwise spanning trees, and use only random bits. More generally, can previous approaches to the random spanning tree problem easily handle other joint distributions?
The proof is quite simple and relies on the following insight:
Here is the set where . The map is the bijection from Farbod’s theorem, and is an injection that is easy to compute. In order to select pairwise elements from , we need only select pairwise elements from . This can be done in random bits by standard methods, which proves the theorem.
The open problem is to find other applications for Farbod’s bijection. Can we solve some known open problems using this neat result? Are there other types of random distributions that might be useful?