6
$\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 -- 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

$\endgroup$
4
  • $\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 '20 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 '20 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 '20 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 '20 at 9:58
0
$\begingroup$

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.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.