Sampling tree-weighted balanced graph partitions in polynomial time.

Abstract: 

When judging the fairness of a political redistricting map, it is useful to be able to generate a large ensemble of “random” alternative maps. Formally, this is a graph partitioning problem. The objective is to output random partitions of the vertex set into k equal-sized pieces inducing connected subgraphs. Numerous algorithms have been developed to sample either exactly or approximately from the so-called “spanning tree distribution,” where each partition is weighted by the product of the numbers of spanning trees in each part. However, none of these algorithms had been shown to run in polynomial time, even on very tame families of graphs. In a recent paper, Charikar, Liu, Liu, and Vuong proposed a simple algorithm, and conjectured that it runs in polynomial time on grid graphs for constant k. We prove this conjecture, and extend to a wide class of “grid-like” planar graphs encapsulating the kinds of graphs typically encountered in real geographical data

Posted on Mar 31, 2025 in ACGO, Seminars