Counting and Sampling: Algorithms and Complexity

Immanants are matrix functionals that generalize determinants and permanents by allowing general irreducible characters of the symmetric group as permutations weights rather than merely the sign function (which yields the determinant) or the all-ones function (which yields the permanent). In this talk, we give an introduction to immanants and describe a recent classification of their complexity. In a second part, we give a simple proof that shows how determinants can be expressed in terms of homomorphism counts from cycle covers, leaving open similar expressions for general immanants.

We study the computational complexity of the problem #IndSub($\mathrm{\Phi }$) of counting $k$-vertex induced subgraphs of a graph $G$ that satisfy a graph property $\mathrm{\Phi }$. Our main result establishes an exhaustive and explicit classification for all hereditary properties, including tight conditional lower bounds under the Exponential Time Hypothesis (ETH): If a hereditary property $\mathrm{\Phi }$ is true for all graphs, or if it is true only for finitely many graphs, then #IndSub($\mathrm{\Phi }$) is solvable in polynomial time. Otherwise, #IndSub($\mathrm{\Phi }$) is #W[1]-complete when parameterised by $k$, and, assuming ETH, it cannot be solved in time $f(k)\cdot {|G|}^{o(k)}$ for any function $f$. This classification features a wide range of properties for which the corresponding detection problem (as classified by Khot and Raman [TCS 02]) is tractable but counting is hard. Moreover, even for properties which are already intractable in their decision version, our results yield significantly stronger lower bounds for the counting problem. As additional result, we also present an exhaustive and explicit parameterised complexity classification for all properties that are invariant under homomorphic equivalence. By covering one of the most natural and general notions of closure, namely, closure under vertex-deletion (hereditary), we generalise some of the earlier results on this problem. For instance, our results fully subsume and strengthen the existing classification of #IndSub($\mathrm{\Phi }$) for monotone (subgraph-closed) properties due to Roth, Schmitt, and Wellnitz [FOCS 20]. A full version of our paper, containing all proofs, is available at https://arxiv.org/abs/2111.02277.

We study the performance of Markov chains for the $q$-state ferromagnetic Potts model on random regular graphs. While the cases of the grid and the complete graph are by now well-understood, the case of random regular graphs has resisted a detailed analysis and, in fact, even analysing the properties of the Potts distribution has remained elusive. It is conjectured that the performance of Markov chains is dictated by metastability phenomena, i.e., the presence of “phases” (clusters) in the sample space where Markov chains with local update rules, such as the Glauber dynamics, are bound to take exponential time to escape, and therefore cause slow mixing. The phases that are believed to drive these metastability phenomena in the case of the Potts model emerge as local, rather than global, maxima of the so-called Bethe functional, and previous approaches of analysing these phases based on optimisation arguments fall short of the task.

Our first contribution is to detail the emergence of the two relevant phases for the q-state Potts model on the $d$-regular random graph for all integers $q,d\ge 3$, and establish that for an interval of temperatures, delineated by the uniqueness and a broadcasting threshold on the $d$-regular tree, the two phases coexist (as possible metastable states). The proofs are based on a conceptual connection between spatial properties and the structure of the Potts distribution on the random regular graph, rather than complicated moment calculations. This significantly refines earlier results by Helmuth, Jenssen, and Perkins who had established phase coexistence for a small interval around the so-called ordered-disordered threshold (via different arguments) that applied for large $q$ and $d\ge 5$.

Based on our new structural understanding of the model, our second contribution is to obtain metastability results for two classical Markov chains for the Potts model. We first complement recent fast mixing results for Glauber dynamics by Blanca and Gheissari below the uniqueness threshold, by showing an exponential lower bound on the mixing time above the uniqueness threshold. Then, we obtain tight results even for the non-local and more elaborate Swendsen-Wang chain, where we establish slow mixing/metastability for the whole interval of temperatures where the chain is conjectured to mix slowly on the random regular graph. The key is to bound the conductance of the chains using a random graph “planting” argument combined with delicate bounds on random-graph percolation.

A backoff protocol is a simple and elegant randomised algorithm for communicating in a Multiple Access Channel. Aldous conjectured in 1987 that, for any positive arrival rate, every backoff protocol is unstable. I will report on new work with John Lapinskas towards proving this conjecture. (This will appear in SODA 2023.)

We present a new framework to derandomise certain Markov chain Monte Carlo (MCMC) algorithms. As in MCMC, we first reduce counting problems to sampling from a sequence of marginal distributions. For the latter task, we introduce a method called coupling towards the past that can, in logarithmic time, evaluate one or a constant number of variables from a stationary Markov chain state. Since there are at most logarithmic random choices, this leads to very simple derandomisation. We provide two applications of this framework, namely efficient deterministic approximate counting algorithms for hypergraph independent sets and hypergraph colourings, under local lemma type conditions matching, up to lower order factors, their state-of-the-art randomised counterparts.

We study the SIRS process, a continuous-time Markov chain modelling the spread of infections on graphs. In this process, vertices are either susceptible, infected, or recovered. Each infected vertex becomes recovered at rate 1 and infects each of its susceptible neighbours independently at rate $\lambda$, and each recovered vertex becomes susceptible at a rate $\rho$, which we assume to be independent of the graph size. A central quantity of the SIRS process is the time until no vertex is infected, known as the survival time. The survival time of the SIRS process is studied extensively in a variety of contexts. Surprisingly though, to the best of our knowledge, no rigorous theoretical results exist so far. This is even more surprising given that for the related SIS process, mathematical analysis began in the 70s and continues to this day.

We address this imbalance by conducting the first theoretical analyses of the SIRS process on various graph classes via their expansion properties. Our analyses assume that the graphs start with at least one infected vertex and no recovered vertices. Our first result considers stars, which have poor expansion. We prove that the expected survival time of the SIRS process on stars is at most polynomial in the graph size for any value of $\lambda$. This behaviour is fundamentally different from the SIS process, where the expected survival time is exponential already for small infection rates. Due to this property, for the SIS process, stars constitute an important sub-structure for proving an expected exponential survival time of more complicated graphs. For the SIRS process, this argument is not sufficient.

Our main result is an exponential lower bound of the expected survival time of the SIRS process on expander graphs. Specifically, we show that on expander graphs $G$ with $n$ vertices, degree close to $d$, and sufficiently small spectral expansion, the SIRS process has expected survival time at least exponential in $n$ when $\lambda \ge c/d$ for a constant $c>1$. This result is complemented by established results for the SIS process, which imply that the expected survival time of the SIRS process is at most logarithmic in $n$ when $\lambda \le c/d$ for a constant . Combined, our result shows an almost-tight threshold behaviour of the expected survival time of the SIRS process on expander graphs. Additionally, our result holds even if $G$ is a subgraph. This allows, for the SIRS process, the use of expanders as sub-structures for lower bounds, similar to stars in the SIS process. Notably, our result implies an almost-tight threshold for Erdős–Rényi graphs and a regime of exponential survival time for hyperbolic random graphs, one of the most popular graph models, as it incorporates many properties found in real-world networks. The proof of our main result draws inspiration from Lyapunov functions used in mean-field theory to devise a two-dimensional potential function and applying a negative-drift theorem to show that the expected survival time is exponential.

We present a number of complexity results concerning the problem of counting vertices of an integral polytope defined by a system of linear inequalities. The focus is on polytopes with small integer vertices, particularly 0/1-polytopes and half-integral polytopes (ones whose vertices are contained in ${\{0,1\}}^n$ and ${\{0,\frac{1}{2},1\}}^n$, respectively). Such polytopes are ubiquitous in the field of combinatorial optimisation.

Suppose a polytope $P$ is defined by linear inequalities $Ax\le b$. If the matrix $A$ is ‘totally unimodular’ then $P$ is guaranteed to be integral; many integral polytopes that are encountered in practice arise in this way. Network matrices and their transposes are particular kinds of totally unimodular matrices. Our main results are the following.

• $\mathrm{■}$

  Counting the vertices of a 0/1-polytope exactly is #P complete, even when restricted to the case when $A$ is a network matrix or the transpose of one. (This is nothing more than an observation, given that the problems of counting perfect matchings or independent sets in a bipartite graph are both #P-complete.)

• $\mathrm{■}$

  Approximately counting the vertices of a half-integral polytope is NP-hard, as witnessed by the ‘perfect 2-matching polytope’.

• $\mathrm{■}$

  The vertex-counting problem for 0/1-polytopes defined by transposes of network matrices is equivalent, under approximation-preserving reductions, to counting independent sets of a bipartite graph (#BIS). No efficient approximation algorithm is known for #BIS, but neither is approximating #BIS known to be NP-hard. Many natural counting problems are known to be equivalent to #BIS under polynomial-time approximation-preserving reductions.

• $\mathrm{■}$

  For a natural subclass of polytopes defined by network matrices, it is possible to approximate the number of vertices in polynomial time. The complexity for network matrices in general is, however, unknown,

We study a query model of computation in which an n-vertex k-hypergraph can be accessed only via its independence oracle or via its colourful independence oracle, and each oracle query may incur a cost depending on the size of the query. In each of these models, we obtain oracle algorithms to approximately count the hypergraph’s edges, and we unconditionally prove that no oracle algorithm for this problem can have significantly smaller worst-case oracle cost than our algorithms.

We study a nearest-neighbor Markov chain over biased permutations of $[n]$. We build on previous work that analyzed the spectral gap of the chain when $[n]$ is partitioned into $k$ classes. There, the authors iteratively decomposed the nearest neighbor chain into simpler chains, but incurred a multiplicative penalty of $n^{-2}$ for each application of the decomposition theorem. We introduce a new decomposition theorem which allows us to avoid this penalty (in certain cases) and prove the first inverse-polynomial bound on the spectral gap of the chain when $k$ is as large as $\mathrm{\Theta }(n/\log n)$. The previous best known bound assumed $k$ was at most a constant.

Gibbs point processes are a popular way to model particle distributions of fluids and gasses in Euclidean space. Similar to spin systems on graphs, which might be seen as their discrete counterparts, sampling the Gibbs distribution and computing its normalizing constant, the partition function, of such point processes is highly relevant. However, until recently, very few rigorous computational results existed. In this talk, we give a brief introduction to Gibbs point processes and present recent algorithmic results. In particular, we focus on discretization-based algorithms, which reduce the algorithmic tasks at hand to related problems for discrete spin systems, making use of the rich literature in that area. Our main focus will be on a recent approach that employs hard-core models on carefully constructed families of geometric random graphs to obtain sampling and approximation algorithms for Gibbs point processes. This results in efficient algorithms for arbitrary repulsive pair potentials $\varphi$ up to a fugacity of , where $C_{\varphi }$ is the temperedness constant of $\varphi$.

I will discuss how one can (approximately and quickly) sample configurations from the ferromagnetic Potts model with underlying graph $G$ at low temperatures using a Markov chain on flows. The use of flows allows one to work with certain types of graphs that can have unbounded degree.

Building on work of Williams (CCC’16) and Björklund & Kaski (PODC’16) on fine-grained noninteractive proof systems in the context of deterministic counting problems, we study verifiable randomized approximation schemes for hard counting problems such as the permanent. We show that sample-average-based Monte Carlo estimators such as the Godsil-Gutman and the Chien-Rasmussen-Sinclair estimators for the permanent admit verifiable randomized approximation with verifier complexity scaling essentially as the square root of the prover/estimator complexity.

[This work is to appear in NeurIPS’22.]

In this talk I will explain that for any non-real algebraic number $q$, approximately computing the absolute value of the chromatic polynomial evaluated at $q$ is as hard as computing it exactly and hence is #P-hard. The proof is based on constructing series-parallel gadgets that “implement” a dense set of edge interactions and is inspired by Sokal’s result saying that chromatic roots are dense in the complex plane.

We study the problem of counting the copies of a small directed pattern graph $H$ in a large directed host graph $G$. Motivated by the recent surge on pattern counting in degenerate graphs, we focus on host graphs with small outdegree $d(G)$. Formally, we choose $|H|+d(G)$ as the problem parameter and ask for which classes of patterns the problem is fixed-parameter tractable.

This talk presents a complete parameterised complexity classification of the problem and provides an overview of the technical challenges in proving this result – among others, those challenges include a careful analysis of a variety of width measures on hypergraphs encoding the reachability structure of directed graphs.

We investigate how efficiently a well-studied family of domination-type problems can be solved on bounded-treewidth graphs. For sets $\sigma ,\rho$ of non-negative integers, a $(\sigma ,\rho )$-set of a graph $G$ is a set $S$ of vertices such that $|N(u)\cap S|\in \sigma$ for every $u\in S$, and $|N(v)\cap S|\in \rho$ for every $v\notin S$. The problem of finding a $(\sigma ,\rho )$-set (of a certain size) unifies standard problems such as Independent Set, Dominating Set, Independent Dominating Set, and many others.

For all pairs of finite or cofinite sets $(\sigma ,\rho )$, we determine (under standard complexity assumptions) the best possible value $c_{\sigma ,\rho }$ such that there is an algorithm that counts $(\sigma ,\rho )$-sets in time $c_{\sigma ,\rho }^{\text{tw}}\cdot n^{O(1)}$ (if a tree decomposition of width tw is given in the input). Let $s_{top}$ denote the largest element of $\sigma$ if $\sigma$ is finite, or the largest missing integer $+1$ if $\sigma$ is cofinite; $r_{top}$ is defined analogously for $\rho$. Surprisingly, $c_{\sigma ,\rho }$ is often significantly smaller than the natural bound $s_{top}+r_{top}+2$ achieved by existing algorithms [van Rooij, 2020]. Toward defining $c_{\sigma ,\rho }$, we say that $(\sigma ,\rho )$ is $m$-structured if there is a pair $(\alpha ,\beta )$ such that every integer in $\sigma$ equals $\alpha$ mod $m$, and every integer in $\rho$ equals $\beta$ mod $m$. Then, setting

• $\mathrm{■}$

  $c_{\sigma ,\rho }=s_{top}+r_{top}+2$ if $(\sigma ,\rho )$ is not $m$-structured for any $m\ge 2$,

• $\mathrm{■}$

  $c_{\sigma ,\rho }=\max \{s_{top},r_{top}\}+2$ if $(\sigma ,\rho )$ is 2-structured, but not $m$-structured for any $m\ge 3$, and $s_{top}=r_{top}$ is even, and

• $\mathrm{■}$

  $c_{\sigma ,\rho }=\max \{s_{top},r_{top}\}+1$, otherwise,

we provide algorithms counting $(\sigma ,\rho )$-sets in time $c_{\sigma ,\rho }^{\text{tw}}\cdot n^{O(1)}$. For example, for the Exact Independent Dominating Set problem (also known as Perfect Code) corresponding to $\sigma =\{0\}$ and $\rho =\{1\}$, this improves the $3^{\text{tw}}\cdot n^{O(1)}$ algorithm of van Rooij to $2^{\text{tw}}\cdot n^{O(1)}$.

Despite the unusually delicate definition of $c_{\sigma ,\rho }$, we show that our algorithms are most likely optimal, that is, for any pair $(\sigma ,\rho )$ of finite or cofinite sets where the problem is non-trivial, and any $\epsilon >0$, a ${(c_{\sigma ,\rho }-\epsilon )}^{\text{tw}}\cdot n^{O(1)}$-algorithm counting the number of $(\sigma ,\rho )$-sets would violate the Counting Strong Exponential-Time Hypothesis (#SETH). For finite sets $\sigma$ and $\rho$, our lower bounds also extend to the decision version, showing that our algorithms are optimal in this setting as well. In contrast, for many cofinite sets, we show that further significant improvements for the decision and optimization versions are possible using the technique of representative sets.

Recently, a number of algorithmic methods for approximately counting the number of independent sets of a given size $k=\lfloor \alpha n\rfloor$ in $n$-vertex bounded-degree graphs have been discovered. In [2] the sharp hardness threshold in the density $\alpha$ was uncovered, and the algorithm in the tractable region of densities is based on rejection sampling from the hard-core model. Alternative approaches based local central limit theorems that yield faster algorithms were given in [3].

There is a natural Markov chain whose stationary distribution is uniform on independent sets of size $k$, namely the down-up walk that from a state $I$ takes a uniform random element $v\in I$ and moves to a uniform random independent set of size $k$ containing $I\setminus \{v\}$. This was shown using path coupling [1] to mix rapidly at densities up to roughly $\alpha \sim 1/(2d)$ in graphs of maximum degree $d$. The hardness threshold from [2] is slightly larger: ${\alpha }_c\sim e/(1+e)\cdot 1/d$.

This working group focused on the question of whether the down-up walk mixes rapidly up to the hardness threshold. Emerging techniques that seem pertinent include spectral independence and localization schemes, but there is a rather significant obstacle to apply these techniques associated with the global constraint of a fixed size $k$. We did not overcome the main obstacle, and instead explored alternative approaches and familiarised ourselves with topics such as correlation decay, computation trees, and zeros of partition functions for the fixed-size model. One starting point is an idea due to Heng Guo that provides a computation tree for the ratios $r_k(v)={\mathrm{Pr}}_k(v\in I)/{\mathrm{Pr}}_k(v\notin I)$ where ${\mathrm{Pr}}_k$ is over the uniform independent set of size $k$, but it remains unclear how to use this insight to study the mixing time of the down-up walk. We thank Guus Regts for an interesting discussion on techniques for finding zero-free regions.

A key component of the approximate counting algorithm for independent sets in bounded degree graphs by Patel-Regts is a fixed parameter tractable algorithm for exactly counting them with the size being the parameter. The natural question is then if there is a corresponding lower bound. There are various hardness results when the degree bound goes to $n$, namely for general graphs. We have worked on reducing from those cases. However, there is a main difficulty, in that for general graphs, the size of the maximum independent set can be arbitrary, and yet for bounded degree graphs it is linear in the number of vertices. This makes such reductions difficult to construct.

The computational complexity of approximately counting the number of proper colorings with say a million colors of planar graphs is unclear. On the one hand as soon as we replace the number a million by any non-real number close arbitrarily to it and look at the evaluation of the chromatic polynomial at this point, this problem becomes #P-hard on planar graphs, as was recently proved in [1]. On the other hand a planar graph can be colored with 4 colors, which could possibly lead to the suspicion that for some large enough number of colors approximately counting the number of proper colorings should not be computational hard.

We have met in various compositions throughout the week and discussed the problem. Unfortunately we have not really made any progress. Some of the things we looked at include: the use of standard decomposition techniques for planar graphs and reductions to partition function of the ferromagnetic Potts model. The main conclusion from our initial discussions has been that this appears to be a difficult problem for which the current techniques are not powerful enough to make progress. Perhaps a useful question is to see if there exist sub exponential algorithms. For example Nederlof [2] designed an exact $2^{O(\sqrt{k})}\text{poly}(n)$ algorithm for counting the number of independent sets of size $k$ in a planar $n$-vertex graph.

The goal of this working group was to improve the understanding of the structure of the so-called homomorphism basis of counting problems: Well-known transformations dating back to early works of Lovász allow the expression of a wide range of counting problems (including problems arising in database theory and network sciences) as a finite linear combination of homomorphism counts. For example, it is known that for every graph $H$ there exists a finitely supported function $a$ from graphs to rationals such that, for every graph $G$ the following is true:

where $\mathrm{\#}\mathrm{𝖲𝗎𝖻}(H\to G)$ denotes the number of subgraphs of $G$ that are isomorphic to $H$, and $\mathrm{\#}\mathrm{𝖧𝗈𝗆}(F\to G)$ denotes the number of graph homomorphisms (edge-preserving mappings) from $F$ to $G$. In other words, the problem of counting copies of $H$ in a graph $G$ can be cast as computing a finite linear combination of homomorphism counts.

In 2017, Curticapean, Dell and Marx [1] established a remarkable property, sometimes called “complexity monotonicity”, of linear combinations as in (2): They are exactly has hard to compute as their hardest term $\mathrm{\#}\mathrm{𝖧𝗈𝗆}(F\to G)$ with a non-zero coefficient ($a(F)\ne 0$).⁶⁶6This property is very special to homomorphism counts, as it does not hold for computing linear combinations of general counting problems: For example, computing the number of satisfying assignments plus the number of unsatisfying assignments of an $n$-variable CNF is always $2^n$, i.e., easy to compute, although computing the individual terms is $\mathrm{\#}\mathrm{P}$-hard. Since the complexity of computing individual homomorphism counts is reasonably well-understood due to a result of Dalmau and Jonsson [2], this discovery enabled a general strategy for studying the complexity of counting problems: Cast the problem as a linear combination of homomorphism counts and investigate which terms cancel out, i.e., for which graphs $F$ the coefficient $a(F)$ becomes $0$. In recent years, this strategy has seen significant success in classifying counting problems arising e.g. in database theory [3, 4], subgraph and induced subgraph counting [1, 5, 6], modular counting [7, 8], fine-grained homomorphism counting [12], and pattern counting in degenerate graphs [9, 10, 11].

The purpose of this working group was to gather and unify the many different tools that have been established for analysing the homomorphism basis, to enhance the methods to tackle new problems, and to find common grounds for future collaborations.