Uniformly sampling or counting connected graph partitions with any number of blocks

Question

Question: Is it possible to uniformly sample in polynomial time from the set of all connected partitions of a graph? Or is there a JVV type argument that proves this to be NP-hard?

To clarify: By a connected partition of $G = (V,E)$ I mean a partition of the nodes of $V$ into blocks $A_1, \ldots, A_m$, where each $A_i$ induces a connected subgraph. There are no constraints on the number of blocks. In different language, I am asking about uniformly sampling from the flats of the graphic matroid of $G$.

I thought about this for a while, but couldn't figure it out. Maybe someone knows the answer or can suggest something to try? The question of counting the number of connected partitions is closely related and also interesting to me.

Here are some related things I know:

• If you fix the number of blocks of the partition, then this is NP-hard to sample. For example, in the $2$ block case, this follows by reducing to uniformly sampling simple cycle in the plane dual graph. (Both the NP-hard optimization problem and the probability concentration gadget do not carry over meaningfully to the any number of blocks case.)

• Enumeration is possible in total linear time. For instance this follows from this: https://arxiv.org/pdf/1107.4301.pdf

• The idea of the previously linked paper also lets you sample low rank flats somewhat efficiently. That is, by picking weights $2^k$ so that each flat has a unique min basis, and then using that a rank $r$ flat in the graphic matroid of a plane graph will have $O(6^{2r})$ basis ( https://arxiv.org/abs/0912.0712 ) to obtain a bound on the rejection rate obtained by sampling a nearly uniform rank r independent set (using basis-exchange walk) and then checking if it is the min-weight basis of its span.

• There is natural family of Glauber dynamics type Markov chains to try: Any connected partition can be identified with the corresponding flat in the graphic matroid (i.e. the edges with both endpoints in the same block), and one can introduce a Metropolis-Hasting's score function that measures deviation of a subset of edges from being a flat. For instance, for any set of edges, $J \subset E$, and some fixed $\lambda > 0$, the score can be $\lambda^{ loops(G/J)}$, where $loops$ measures the number of self loops, that is, edges in $E \setminus J$ that go between the same connected components of $G[J]$. For $\lambda = 1$ this mixes rapidly, but the stationary distribution is not concentrated on the flats.

• For $\lambda$ very small the stationary distribution in the chain of the previous bullet is concentrated on the flats. However, there are examples where the mixing slows down when decreasing $\lambda$ (for instance, a $d$-dipole graph will have a hard time leaving the flat containing all edges). I couldn't figure out cases like the grid graph.

• Describing connected partitions as flats as in the Markov chain two bullets above leads to another total linear time enumeration algorithm; you can tell whether it is possible to extend a set of deleted and a set of included edges to a flat by checking whether there are any contradictions. Checking whether there are any such contradictions is straightforward to do efficiently, and so one can use backtracking to enumerate.

• Somewhat surprisingly, for small grid graphs, say $8 \times 8$, rejection sampling for flats from subsets of edges is reasonably efficient. This can be used to test the Markov chain in the previous bullet for grid graphs, and it seems to work ok. Empirically, a typical connected partition of a grid graph appears to consist of many small blocks.

• Another Markov chain uses spanning trees to parametrize partitions. Versions of this have been written about in a few places: https://arxiv.org/abs/1908.07176 (see the thesis of Tien Vo on "Large-Scale Statistical Inference for Graph-Associated data" for details on the Markov chain mentioned in that paper), https://arxiv.org/abs/1808.00050, https://arxiv.org/abs/1911.05725.

• The complete graph case is already interesting and non-trivial: https://www.sciencedirect.com/science/article/pii/0097316583900092

• For purposes of counting or sampling connected partitions on smaller graphs, ZDDs are a natural structure to use. The python package Graphillion should be able to handle this -- I spoke with one of the developers recently and they apparently have been working on adding connected partitions: https://github.com/takemaru/graphillion/issues/43

Answer 1

The generalized question about exact counting of flats of a matroid has an answer.

Let $G$ be a graph, and let $G^{\circ}$ be the same graph with a loop at every vertex. Then, the flats of the bicircular matroid of $G^{\circ}$ are exactly the forests of $G$; see Bicircular geometry and the lattice of forests of a graph.

It is known, on the other hand, that counting the number of spanning forests in a graph is a $\#$P-hard problem. See for instance Fast exponential-time algorithms for the forest counting and the Tutte polynomial computation in graph classes.

Putting these together shows that exact counting of flats is in general $\#$P-hard.

Remark: The approach that led to finding this example was to search through examples of matroids on wikipedia, and reading the section on flats until I saw one that I knew to be related to NP-hard problems.

Remark: Additionally, it is known that the forest counting problem remains hard when parametrized by the number of edges. See here. (Although that paper points out that the problem is fixed parameter tractable for plane graphs, because of this algorithm: https://arxiv.org/abs/cs/9911003 .)

Sampling or approximate counting: I'm not sure about sampling or approximate counting flats from a matroid.

There appears to be a long line of work on the problem of approximately counting forests: see Forests, colorings and acyclic orientations of the square lattice or A Randomised Approximation Algorithm for Counting the Number of Forests in Dense Graphs. Perhaps another matroid would provide a more tractable example of hardness of approximation / sampling. I will update this answer if I learn about one.