Complexity and Geometry of Sampling Connected Graph Partitions

Elle Najt, Daryl DeFord, Justin Solomon

In this paper, we prove intractability results about sampling from the set of partitions of a planar graph into connected components. Our proofs are motivated by a technique introd…