3
$\begingroup$

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, for instance for plane graphs by exploiting the duality between connected partitions and unions of simple cycles, and then using the frontier based ZDD for simple cycles and the union and join operations on set families. Minato et al. managed to build a ZDD for self avoiding walks on the 26x26 grid graph, which is a closely related problem.

$\endgroup$
  • $\begingroup$ I believe sampling/counting flats is still open. A related open problem is the log-concavity of the number of flats parametrised by sizes, or the so-called Whitney number of the second kind. See e.g. Section 4.10 of arxiv.org/pdf/1705.07960.pdf $\endgroup$ – Heng Guo Apr 8 at 9:37
  • $\begingroup$ (cont.) Usually an easy to sample structure form a log-concave sequence when parameterised by sizes. (If there were two exponentially large peaks, local Markov chains are always slow.) This is the case for independent sets for matroids thanks to a sequence of great work by Huh and others. Flats are conjectured to be log-concave but we still don't know. $\endgroup$ – Heng Guo Apr 8 at 9:41
  • $\begingroup$ @HengGuo Just to clarify -- you think it's open that counting flats is #P complete, not even when restricted to the case of graphic matroids? (E.g. in the context where the Matroids are representable over some field, or the family of matroids is given by a polytime constructable circuit realizing the independence oracle.) Thanks for the interesting comments. $\endgroup$ – Lorenzo Najt Apr 14 at 17:12
  • $\begingroup$ I think approximate counting / sampling is open. I cannot recall exact counting being #P hard, but perhaps that's not too hard to show? (Just my guess and I haven't tried.) $\endgroup$ – Heng Guo Apr 15 at 9:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.