Skip to content

A New Approach To Random Spanning Trees

July 15, 2009

There is a bijective proof of Kirchhoff’s matrix theorem with applications to spanning trees

Picture 1

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?

The Bijection

Suppose that {G} is a a finite, connected multigraph with no loops. Associated with each such graph is {J(G)}, called the Jacobian of the graph. Let {T(G)} be the set of spanning trees of {G}. The group {J(G)} is always an abelian group, its cardinality is exactly the number of spanning trees of the graph {G}. Elements of {J(G)} are represented by (equivalence classes of) integer-valued functions on the vertices of {G}. Invariant factors and generators of {J(G)} can efficiently be computed.

The following theorem is due to Farbod:

Theorem: There is a bijection {\phi} that maps {J(G)} to {T(G)} 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 {J(G)}, and the elements of this group are in one-to-one correspondance with {T(G)}.

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 {x} in the group {J(G)} there is a natural map that associates with {x} 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,{\dots}

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 {r} of the group {J(G)}–which is a trivial task–and constructs {\phi(r)}, 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 {G} is a connected multigraph with no loops. Then, there is an algorithm that generates a family of pairwise random spanning trees of {G} in polynomial time and uses only {O(\log |T(G)|)} 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 {k} random spanning trees would use {k \cdot \log |T(G)|)} 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 {O(\log |T(G)|)} 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:

Picture 1

Here {[N]} is the set {\{1, \dots, N \}} where {N = |J(G)| = |T(G)|}. The map {\phi} is the bijection from Farbod’s theorem, and {i} is an injection that is easy to compute. In order to select pairwise elements from {T(G)}, we need only select pairwise elements from {[N]}. This can be done in {O(\log N)} random bits by standard methods, which proves the theorem.

Open Problems

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?

10 Comments leave one →
  1. Aaron Roth permalink
    July 15, 2009 1:50 pm

    Negative results about approaches to mathematical problems are one of the areas covered by the prestigious open-access journal Rejecta Mathematica.

    • rjlipton permalink*
      July 15, 2009 2:09 pm

      Very cool. But I was serious. Oh well.

      • JeffE permalink
        July 15, 2009 3:19 pm

        Despite initial appearances, Rejecta Mathematica is actually serious.

      • Aaron Roth permalink
        July 15, 2009 3:24 pm

        Actually, it looks like Rejecta Mathematica is somewhat serious as well. At least they have a reasonable first issue that seems to contain real papers. Unfortunately, they have the prerequisite that papers have to have been rejected from some journal or conference before being submitted to Rejecta, so its not quite the negative results journal you want. (They specifically do not allow papers that the author just assumes would be rejected) But this seems to be because they rely on the original reviewers to give a technical analysis of the paper.

  2. rjlipton permalink*
    July 15, 2009 4:39 pm

    I apologize. I understand that is a real journal. Great idea, but not exactly what I had in mind.

    Also one of the founders is from Tech, Chris Rozell. We at Tech are on the cutting edge of the new Web 2.0.

    P.S. Please read the rest of the post too, please.

  3. July 15, 2009 4:49 pm

    Farbod’s comment about the group law on q-critical configurations being “artificial” is relevant to something I’ve been thinking about: the matrix-tree theorem is a (nontrivial) corollary of the Gessel-Viennot lemma, which is also a theorem stating that a certain determinant of a matrix M counts certain paths in a graph. In other words, here there is also a bijection between a group (Z^n/M) and a set of combinatorial objects, but the group law induced on the objects here must also be “artificial,” i.e. non-canonical. Anyway, the standard proof of Gessel-Viennot is by a sign-reversing involution argument, similar to one proof of Kirchhoff’s theorem, and doesn’t explicitly give a bijection; I’m wondering whether it’s possible to generalize Farbod’s bijection to this more general case.

    • Farbod Shokrieh permalink
      July 16, 2009 3:58 am

      Let me first clarify what I mean by the group law being “artificial” on the critical configuration; the group elements in the “Jacobian” or “Picard” definition are really equivalence classes (or cosets). The group law is of course naturally defined in these constructions. Now, if one insists that the elements of the group are not actually the equivalence classes, but rather “canonical elements” (relative to a fixed vertex) of classes – as in “critical” of “sandpile” definition – then the group law looks magical (I called it artificial, for the lack of a better term). For example if you add two q-critical configurations, you won’t get an element of the group anymore, and you have to play the chip-firing game (or use my algorithm) to get the resulting group element. I am explaining this because it occurs to me that the situation is somehow different from the combinatorial objects you consider…

      Whether one can develop a similar theory for the Lindstrom-Gessel-Viennot theorem is a very nice question, and my answer at the moment is: I don’t know. I have not studied the literature about this subject. Is there a “nice” canonical representative for elements of (Z^n/Im(M)), say for the basic bipartite case? If such canonical elements are known, is there in bijection known between such canonical elements and the weighted path system? Is there a “nice” group law known on the weighted paths? I am eager to know the answer to any of these questions.

      Of course whenever you have a matrix M with non-zero determinant, you can make a finite abelian group (Z^n/Im(M)) whose order is equal to the determinant. But in order to have a bijective proof or a nice group law on your combinatorial objects, I think you need more than this…

      Of course the fact that matrix-tree theorem can be derived as a corollary of Lindstrom-Gessel-Viennot is suggestive that something more general could be going on here. I will be thinking more about this… Thanks for the comment!

  4. Páidí Creed permalink
    July 25, 2009 6:20 pm

    The other two types of algorithms for this problem (those based on determinant computations and on random walks) generalise to uniform generation of spanning arborescences of directed graphs. Is their a similar generalisation for this approach?

    • Farbod Shokrieh permalink
      July 28, 2009 7:47 pm

      Similar definitions and objects can be defined for directed graphs as well.
      I have not spent too much time on this, but my feeling is that similar techniques should also work for directed graphs…

  5. September 3, 2009 8:01 pm

    Cool site, love the info.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s