Sampling from partitions of graph vertices into connected subsets

Question

Suppose I have a connected graph $G=(V,E)$, where $E\subseteq V\times V$ contains undirected edges. For $V'\subseteq V$, denote $G_{V'}$ as the induced subgraph $G_{V'}:=(V',E\cap(V'\times V')).$

Denote $S$ as the set of partitions into two connected components: $$ S:=\{V'\subseteq V : G_{V'}\textrm{ and }G_{V\backslash V'}\textrm{ are connected subgraphs}\}. $$ Is it tractable to sample from $S$ with uniform probability for each element?

---

Apologies for clunky notation. Some ideas that sample non-uniformly include:

• Randomly draw a spanning tree and cut one edge
• Merge pairs of vertices together until two clusters are left

Answer 1

1.5 years later, I can confidently return to this StackExchange post and answer: No, it is not tractable.

In fact, this question led to a research paper with our intern Lorenzo, who appears in the comments of this question.

As outlined in that paper, uniformly sampling graph partitions is dual to uniformly sampling simple cycles in a graph, which even on planar and bounded-degree domains is intractable thanks to a classical result by Jerrum, Valiant, and Vazirani. The basic construction to prove intractability is to replace each edge in $E$ with a subdivision "gadget" that looks like the following:

Each simple cycle in the subdivided graph either is a two-edge cycle $v\to w\to v$ (the loops shown above) or it corresponds to a simple cycle in the original graph. The number of times a cycle in the original graph is "lifted" to a cycle in the subdivided graph is proportional to its length. Hamiltonian cycles get copied the most times --- by an exponential factor!

Hence, uniformly sampling cycles in the subdivided graph gives a randomized algorithm for computing Hamiltonian cycles in the original graph that works with high probability.

The research paper details extensions of this proof for planar, bounded-degree graphs, for which the problem remains intractable. It also contains some qualitative descriptions of the space of graph partitions inspired by literature in statistical physics.

Answer 2

Some form of rejection sampling would probably work reasonably well. We need to be able to compute two things:

1. The probability, $p(V',\overline{V'})$, that a given partition is obtained.

2. A lower bound, $p*$, for the probability that any partition is obtained.

Then we just generate a partition $(V',\overline{V'})$, accept it with probability $\frac{p^*}{p(V',\overline{V'})}$, and otherwise start over.

In the case of the spanning tree method, let $\tau(H)$ denote the number of spanning trees of a graph $H$. Then $$ p(V', \overline{V'}) \ge \frac{\tau(G[V']) \cdot \tau(G[\overline{V'}]) \cdot |E(V',\overline{V'})|}{\tau(G) \cdot (|V(G)|-1)}. $$ One possible choice of $p^*$ is to just set the numerator to $1$. By finding a better lower bound, we improve the efficiency of the algorithm, reducing the probability that we start over.