• ### Approximation via Correlation Decay when Strong Spatial Mixing Fails(1510.09193)

Feb. 1, 2019 cs.DM, cs.CC
Approximate counting via correlation decay is the core algorithmic technique used in the sharp delineation of the computational phase transition that arises in the approximation of the partition function of anti-ferromagnetic two-spin models. Previous analyses of correlation-decay algorithms implicitly depended on the occurrence of strong spatial mixing (SSM). This means that one uses worst-case analysis of the recursive procedure that creates the sub-instances. We develop a new analysis method that is more refined than the worst-case analysis. We take the shape of instances in the computation tree into consideration and amortise against certain "bad" instances that are created as the recursion proceeds. This enables us to show correlation decay and to obtain an FPTAS even when SSM fails. We apply our technique to the problem of approximately counting independent sets in hypergraphs with degree upper-bound Delta and with a lower bound k on the arity of hyperedges. Liu and Lin gave an FPTAS for k>=2 and Delta<=5 (lack of SSM was the obstacle preventing this algorithm from being generalised to Delta=6). Our technique gives a tight result for Delta=6, showing that there is an FPTAS for k>=3 and Delta<=6. The best previously-known approximation scheme for Delta=6 is the Markov-chain simulation based FPRAS of Bordewich, Dyer and Karpinski, which only works for k>=8. Our technique also applies for larger values of k, giving an FPTAS for k>=Delta. This bound is not substantially stronger than existing randomised results in the literature. Nevertheless, it gives the first deterministic approximation scheme in this regime. Moreover, unlike existing results, it leads to an FPTAS for counting dominating sets in regular graphs with sufficiently large degree. We further demonstrate that approximately counting independent sets in hypergraphs is NP-hard even within the uniqueness regime.
• ### Asymptotically Optimal Amplifiers for the Moran Process(1611.04209)

Aug. 1, 2018 math.CO, math.PR, cs.DM, q-bio.PE, cs.SI
We study the Moran process as adapted by Lieberman, Hauert and Nowak. This is a model of an evolving population on a graph or digraph where certain individuals, called "mutants" have fitness r and other individuals, called non-mutants have fitness 1. We focus on the situation where the mutation is advantageous, in the sense that r>1. A family of digraphs is said to be strongly amplifying if the extinction probability tends to 0 when the Moran process is run on digraphs in this family. The most-amplifying known family of digraphs is the family of megastars of Galanis et al. We show that this family is optimal, up to logarithmic factors, since every strongly-connected n-vertex digraph has extinction probability Omega(n^(-1/2)). Next, we show that there is an infinite family of undirected graphs, called dense incubators, whose extinction probability is O(n^(-1/3)). We show that this is optimal, up to constant factors. Finally, we introduce sparse incubators, for varying edge density, and show that the extinction probability of these graphs is O(n/m), where m is the number of edges. Again, we show that this is optimal, up to constant factors.
• ### Uniqueness for the 3-State Antiferromagnetic Potts Model on the Tree(1804.03514)

The antiferromagnetic $q$-state Potts model is perhaps the most canonical model for which the uniqueness threshold on the tree is not yet understood, largely because of the absence of monotonicities. Jonasson established the uniqueness threshold in the zero-temperature case, which corresponds to the $q$-colourings model. In the permissive case (where the temperature is positive), the Potts model has an extra parameter $\beta\in(0,1)$, which makes the task of analysing the uniqueness threshold even harder and much less is known. In this paper, we focus on the case $q=3$ and give a detailed analysis of the Potts model on the tree by refining Jonasson's approach. In particular, we establish the uniqueness threshold on the $d$-ary tree for all values of $d\geq 2$. When $d\geq3$, we show that the 3-state antiferromagnetic Potts model has uniqueness for all $\beta\geq 1-3/(d+1)$. The case $d=2$ is critical since it relates to the 3-colourings model on the binary tree ($\beta=0$), which has non-uniqueness. Nevertheless, we show that the Potts model has uniqueness for all $\beta\in (0,1)$ on the binary tree. Both of these results are tight since it is known that uniqueness does not hold in the complementary regime. Our proof technique gives for general $q>3$ an analytical condition for proving uniqueness based on the two-step recursion on the tree, which we conjecture to be sufficient to establish the uniqueness threshold for all non-critical cases ($q\neq d+1$).
• ### Sampling in Uniqueness from the Potts and Random-Cluster Models on Random Regular Graphs(1804.08111)

April 22, 2018 math.PR, cs.DM, cs.DS
We consider the problem of sampling from the Potts model on random regular graphs. It is conjectured that sampling is possible when the temperature of the model is in the uniqueness regime of the regular tree, but positive algorithmic results have been for the most part elusive. In this paper, for all integers $q\geq 3$ and $\Delta\geq 3$, we develop algorithms that produce samples within error $o(1)$ from the $q$-state Potts model on random $\Delta$-regular graphs, whenever the temperature is in uniqueness, for both the ferromagnetic and antiferromagnetic cases. The algorithm for the antiferromagnetic Potts model is based on iteratively adding the edges of the graph and resampling a bichromatic class that contains the endpoints of the newly added edge. Key to the algorithm is how to perform the resampling step efficiently since bichromatic classes may induce linear-sized components. To this end, we exploit the tree uniqueness to show that the average growth of bichromatic components is typically small, which allows us to use correlation decay algorithms for the resampling step. While the precise uniqueness threshold on the tree is not known for general values of $q$ and $\Delta$ in the antiferromagnetic case, our algorithm works throughout uniqueness regardless of its value. In the case of the ferromagnetic Potts model, we simplify the algorithm significantly by utilising the random-cluster representation of the model. In particular, we show that a percolation-type algorithm succeeds in sampling from the random-cluster model with parameters $p,q$ on random $\Delta$-regular graphs for all values of $q\geq 1$ and $p<p_c(q,\Delta)$, where $p_c(q,\Delta)$ corresponds to a uniqueness threshold for the model on the $\Delta$-regular tree. When restricted to integer values of $q$, this yields a simplified algorithm for the ferromagnetic Potts model on random $\Delta$-regular graphs.
• ### Boolean approximate counting CSPs with weak conservativity, and implications for ferromagnetic two-spin(1804.04993)

April 13, 2018 cs.DM, cs.CC
We analyse the complexity of approximate counting constraint satisfactions problems $\mathrm{\#CSP}(\mathcal{F})$, where $\mathcal{F}$ is a set of nonnegative rational-valued functions of Boolean variables. A complete classification is known in the conservative case, where $\mathcal{F}$ is assumed to contain arbitrary unary functions. We strengthen this result by fixing any permissive strictly increasing unary function and any permissive strictly decreasing unary function, and adding only those to $\mathcal{F}$: this is weak conservativity. The resulting classification is employed to characterise the complexity of a wide range of two-spin problems, fully classifying the ferromagnetic case. In a further weakening of conservativity, we also consider what happens if only the pinning functions are assumed to be in $\mathcal{F}$ (instead of the two permissive unaries). We show that any set of functions for which pinning is not sufficient to recover the two kinds of permissive unaries must either have a very simple range, or must satisfy a certain monotonicity condition. We exhibit a non-trivial example of a set of functions satisfying the monotonicity condition.
• ### Phase Transitions of the Moran Process and Algorithmic Consequences(1804.02293)

April 6, 2018 math.CO, math.PR, cs.DM, q-bio.PE, cs.SI
The Moran process is a randomised algorithm that models the spread of genetic mutations through graphs. If the graph is connected, the process eventually reaches "fixation", where every vertex is a mutant, or "extinction", where no vertex is a mutant. Our main result is an almost-tight bound on the expected running time of the algorithm. For all epsilon > 0, we show that the expected running time on an n-vertex graph is o(n^(3+epsilon)). In fact, we show that it is at most n^3 * exp(O((log log n)^3)) and that there is a family of graphs where it is Omega(n^3). In the course of proving our main result, we also establish a phase transition in the probability of fixation, depending on the fitness parameter r of the mutation. We show that no similar phase transition occurs for digraphs, where it is already known that the expected running time can also be exponential. Finally, we give an improved FPRAS for approximating the probability of fixation. Its running time is independent of the size of the graph when the maximum degree is bounded.
• ### Inapproximability of the independent set polynomial in the complex plane(1711.00282)

Feb. 18, 2018 cs.DM, cs.CC
We study the complexity of approximating the independent set polynomial $Z_G(\lambda)$ of a graph $G$ with maximum degree $\Delta$ when the activity $\lambda$ is a complex number. This problem is already well understood when $\lambda$ is real using connections to the $\Delta$-regular tree $T$. The key concept in that case is the "occupation ratio" of the tree $T$. This ratio is the contribution to $Z_T(\lambda)$ from independent sets containing the root of the tree, divided by $Z_T(\lambda)$ itself. If $\lambda$ is such that the occupation ratio converges to a limit, as the height of $T$ grows, then there is an FPTAS for approximating $Z_G(\lambda)$ on a graph $G$ with maximum degree $\Delta$. Otherwise, the approximation problem is NP-hard. Unsurprisingly, the case where $\lambda$ is complex is more challenging. Peters and Regts identified the complex values of $\lambda$ for which the occupation ratio of the $\Delta$-regular tree converges. These values carve a cardioid-shaped region $\Lambda_\Delta$ in the complex plane. Motivated by the picture in the real case, they asked whether $\Lambda_\Delta$ marks the true approximability threshold for general complex values $\lambda$. Our main result shows that for every $\lambda$ outside of $\Lambda_\Delta$, the problem of approximating $Z_G(\lambda)$ on graphs $G$ with maximum degree at most $\Delta$ is indeed NP-hard. In fact, when $\lambda$ is outside of $\Lambda_\Delta$ and is not a positive real number, we give the stronger result that approximating $Z_G(\lambda)$ is actually #P-hard. If $\lambda$ is a negative real number outside of $\Lambda_\Delta$, we show that it is #P-hard to even decide whether $Z_G(\lambda)>0$, resolving in the affirmative a conjecture of Harvey, Srivastava and Vondrak. Our proof techniques are based around tools from complex analysis - specifically the study of iterative multivariate rational maps.
• ### Random Walks on Small World Networks(1707.02467)

Feb. 14, 2018 cs.DM
We study the mixing time of random walks on small-world networks modelled as follows: starting with the 2-dimensional periodic grid, each pair of vertices $\{u,v\}$ with distance $d>1$ is added as a "long-range" edge with probability proportional to $d^{-r}$, where $r\geq 0$ is a parameter of the model. Kleinberg studied a close variant of this network model and proved that the (decentralised) routing time is $O((\log n)^2)$ when $r=2$ and $n^{\Omega(1)}$ when $r\neq 2$. Here, we prove that the random walk also undergoes a phase transition at $r=2$, but in this case the phase transition is of a different form. We establish that the mixing time is $\Theta(\log n)$ for $r<2$, $O((\log n)^4)$ for $r=2$ and $n^{\Omega(1)}$ for $r>2$.
• ### The Complexity of Counting Surjective Homomorphisms and Compactions(1706.08786)

April 9, 2019 cs.DM, cs.CC
A homomorphism from a graph G to a graph H is a function from the vertices of G to the vertices of H that preserves edges. A homomorphism is surjective if it uses all of the vertices of H and it is a compaction if it uses all of the vertices of H and all of the non-loop edges of H. Hell and Nesetril gave a complete characterisation of the complexity of deciding whether there is a homomorphism from an input graph G to a fixed graph H. A complete characterisation is not known for surjective homomorphisms or for compactions, though there are many interesting results. Dyer and Greenhill gave a complete characterisation of the complexity of counting homomorphisms from an input graph G to a fixed graph H. In this paper, we give a complete characterisation of the complexity of counting surjective homomorphisms from an input graph G to a fixed graph H and we also give a complete characterisation of the complexity of counting compactions from an input graph G to a fixed graph H. In an addendum we use our characterisations to point out a dichotomy for the complexity of the respective approximate counting problems (in the connected case).
• ### A Fixed-Parameter Perspective on #BIS(1702.05543)

July 14, 2019 cs.CC
The problem of (approximately) counting the independent sets of a bipartite graph (#BIS) is the canonical approximate counting problem that is complete in the intermediate complexity class #RH\Pi_1. It is believed that #BIS does not have an efficient approximation algorithm but also that it is not NP-hard. We study the robustness of the intermediate complexity of #BIS by considering variants of the problem parameterised by the size of the independent set. We exhaustively map the complexity landscape for three problems, with respect to exact computation and approximation and with respect to conventional and parameterised complexity. The three problems are counting independent sets of a given size, counting independent sets with a given number of vertices in one vertex class and counting maximum independent sets amongst those with a given number of vertices in one vertex class. Among other things, we show that all of these problems are NP-hard to approximate within any polynomial ratio. (This is surprising because the corresponding problems without the size parameter are complete in #RH\Pi_1, and hence are not believed to be NP-hard.) We also show that the first problem is #W[1]-hard to solve exactly but admits an FPTRAS, whereas the other two are W[1]-hard to approximate even within any polynomial ratio. Finally, we show that, when restricted to graphs of bounded degree, all three problems have efficient exact fixed-parameter algorithms.
• ### Inapproximability of the independent set polynomial below the Shearer threshold(1612.05832)

June 21, 2017 cs.DM, cs.CC
We study the problem of approximately evaluating the independent set polynomial of bounded-degree graphs at a point lambda or, equivalently, the problem of approximating the partition function of the hard-core model with activity lambda on graphs G of max degree D. For lambda>0, breakthrough results of Weitz and Sly established a computational transition from easy to hard at lambda_c(D)=(D-1)^(D-1)/(D-2)^D, which coincides with the tree uniqueness phase transition from statistical physics. For lambda<0, the evaluation of the independent set polynomial is connected to the conditions of the Lovasz Local Lemma. Shearer identified the threshold lambda*(D)=(D-1)^(D-1)/D^D as the maximum value p such that every family of events with failure probability at most p and whose dependency graph has max degree D has nonempty intersection. Very recently, Patel and Regts, and Harvey et al. have independently designed FPTASes for approximating the partition function whenever |lambda|<lambda*(D). Our main result establishes for the first time a computational transition at the Shearer threshold. We show that for all D>=3, for all lambda<-lambda*(D), it is NP-hard to approximate the partition function on bipartite graphs of maximum degree D, even within an exponential factor. Thus, our result, combined with the FPTASes for lambda>-lambda*(D), establishes a phase transition for negative activities. In fact, we now have the following picture for the problem of approximating the partition function with activity lambda on graphs G of max degree D. (i) For -lambda*(D)<lambda<lambda_c(D), the problem admits an FPTAS. (ii) For lambda<-lambda*(D) or lambda>lambda_c(D), the problem is NP-hard. Rather than the tree uniqueness threshold of the positive case, the phase transition for negative activities corresponds to the existence of zeros for the partition function of the tree below -lambda*(D).
• ### Functional Clones and Expressibility of Partition Functions(1609.07377)

April 28, 2017 cs.DM
We study functional clones, which are sets of non-negative pseudo-Boolean functions (functions $\{0,1\}^k\to\mathbb{R}_{\geq 0}$) closed under (essentially) multiplication, summation and limits. Functional clones naturally form a lattice under set inclusion and are closely related to counting Constraint Satisfaction Problems (CSPs). We identify a sublattice of interesting functional clones and investigate the relationships and properties of the functional clones in this sublattice.
• ### Approximating partition functions of bounded-degree Boolean counting Constraint Satisfaction Problems(1610.04055)

April 26, 2017 cs.DS, cs.CC
We study the complexity of approximate counting Constraint Satisfaction Problems (#CSPs) in a bounded degree setting. Specifically, given a Boolean constraint language $\Gamma$ and a degree bound $\Delta$, we study the complexity of #CSP$_\Delta(\Gamma)$, which is the problem of counting satisfying assignments to CSP instances with constraints from $\Gamma$ and whose variables can appear at most $\Delta$ times. Our main result shows that: (i) if every function in $\Gamma$ is affine, then #CSP$_\Delta(\Gamma)$ is in FP for all $\Delta$, (ii) otherwise, if every function in $\Gamma$ is in a class called IM$_2$, then for all sufficiently large $\Delta$, #CSP$_\Delta(\Gamma)$ is equivalent under approximation-preserving (AP) reductions to the counting problem #BIS (the problem of counting independent sets in bipartite graphs) (iii) otherwise, for all sufficiently large $\Delta$, it is NP-hard to approximate the number of satisfying assignments of an instance of #CSP$_\Delta(\Gamma)$, even within an exponential factor. Our result extends previous results, which apply only in the so-called "conservative" case.
• ### The complexity of approximating complex-valued Ising and Tutte partition functions(1409.5627)

Jan. 22, 2017 quant-ph, cs.CC
We study the complexity of approximately evaluating the Ising and Tutte partition functions with complex parameters. Our results are partly motivated by the study of the quantum complexity classes BQP and IQP. Recent results show how to encode quantum computations as evaluations of classical partition functions. These results rely on interesting and deep results about quantum computation in order to obtain hardness results about the difficulty of (classically) evaluating the partition functions for certain fixed parameters. The motivation for this paper is to study more comprehensively the complexity of (classically) approximating the Ising and Tutte partition functions with complex parameters. Partition functions are combinatorial in nature and quantifying their approximation complexity does not require a detailed understanding of quantum computation. Using combinatorial arguments, we give the first full classification of the complexity of multiplicatively approximating the norm and additively approximating the argument of the Ising partition function for complex edge interactions (as well as of approximating the partition function according to a natural complex metric). We also study the norm approximation problem in the presence of external fields, for which we give a complete dichotomy when the parameters are roots of unity. Previous results were known just for a few such points, and we strengthen these results from BQP-hardness to #P-hardness. Moreover, we show that computing the sign of the Tutte polynomial is #P-hard at certain points related to the simulation of BQP. Using our classifications, we then revisit the connections to quantum computation, drawing conclusions that are a little different from (and incomparable to) ones in the quantum literature, but along similar lines.
• ### A complexity trichotomy for approximately counting list H-colourings(1602.03985)

Jan. 5, 2017 math.CO, cs.CC
We examine the computational complexity of approximately counting the list H-colourings of a graph. We discover a natural graph-theoretic trichotomy based on the structure of the graph H. If H is an irreflexive bipartite graph or a reflexive complete graph then counting list H-colourings is trivially in polynomial time. Otherwise, if H is an irreflexive bipartite permutation graph or a reflexive proper interval graph then approximately counting list H-colourings is equivalent to #BIS, the problem of approximately counting independent sets in a bipartite graph. This is a well-studied problem which is believed to be of intermediate complexity -- it is believed that it does not have an FPRAS, but that it is not as difficult as approximating the most difficult counting problems in #P. For every other graph H, approximately counting list H-colourings is complete for #P with respect to approximation-preserving reductions (so there is no FPRAS unless NP=RP). Two pleasing features of the trichotomy are (i) it has a natural formulation in terms of hereditary graph classes, and (ii) the proof is largely self-contained and does not require any universal algebra (unlike similar dichotomies in the weighted case). We are able to extend the hardness results to the bounded-degree setting, showing that all hardness results apply to input graphs with maximum degree at most 6.
• ### Counting $4\times 4$ Matrix Partitions of Graphs(1407.7799)

June 29, 2016 cs.CC
Given a symmetric matrix $M\in \{0,1,*\}^{D\times D}$, an $M$-partition of a graph $G$ is a function from $V(G)$ to $D$ such that no edge of $G$ is mapped to a $0$ of $M$ and no non-edge to a $1$. We give a computer-assisted proof that, when $|D|=4$, the problem of counting the $M$-partitions of an input graph is either in FP or is #P-complete. Tractability is proved by reduction to the related problem of counting list $M$-partitions; intractability is shown using a gadget construction and interpolation. We use a computer program to determine which of the two cases holds for all but a small number of matrices, which we resolve manually to establish the dichotomy. We conjecture that the dichotomy also holds for $|D|>4$. More specifically, we conjecture that, for any symmetric matrix $M\in\{0,1,*\}^{D\times D}$, the complexity of counting $M$-partitions is the same as the related problem of counting list $M$-partitions.
• ### The complexity of approximately counting in 2-spin systems on $k$-uniform bounded-degree hypergraphs(1505.06146)

June 20, 2016 cs.DM, cs.CC
One of the most important recent developments in the complexity of approximate counting is the classification of the complexity of approximating the partition functions of antiferromagnetic 2-spin systems on bounded-degree graphs. This classification is based on a beautiful connection to the so-called uniqueness phase transition from statistical physics on the infinite $\Delta$-regular tree. Our objective is to study the impact of this classification on unweighted 2-spin models on $k$-uniform hypergraphs. As has already been indicated by Yin and Zhao, the connection between the uniqueness phase transition and the complexity of approximate counting breaks down in the hypergraph setting. Nevertheless, we show that for every non-trivial symmetric $k$-ary Boolean function $f$ there exists a degree bound $\Delta_0$ so that for all $\Delta \geq \Delta_0$ the following problem is NP-hard: given a $k$-uniform hypergraph with maximum degree at most $\Delta$, approximate the partition function of the hypergraph 2-spin model associated with $f$. It is NP-hard to approximate this partition function even within an exponential factor. By contrast, if $f$ is a trivial symmetric Boolean function (e.g., any function $f$ that is excluded from our result), then the partition function of the corresponding hypergraph 2-spin model can be computed exactly in polynomial time.
• ### Amplifiers for the Moran Process(1512.05632)

May 5, 2016 math.PR, cs.DM, q-bio.PE, cs.SI
The Moran process, as studied by Lieberman, Hauert and Nowak, is a randomised algorithm modelling the spread of genetic mutations in populations. The algorithm runs on an underlying graph where individuals correspond to vertices. Initially, one vertex (chosen u.a.r.) possesses a mutation, with fitness r>1. All other individuals have fitness 1. During each step of the algorithm, an individual is chosen with probability proportional to its fitness, and its state (mutant or non-mutant) is passed on to an out-neighbour which is chosen u.a.r. If the underlying graph is strongly connected then the algorithm will eventually reach fixation, in which all individuals are mutants, or extinction, in which no individuals are mutants. An infinite family of directed graphs is said to be strongly amplifying if, for every r>1, the extinction probability tends to 0 as the number of vertices increases. Lieberman et al. proposed two potentially strongly-amplifying families - superstars and metafunnels. Heuristic arguments have been published, arguing that there are infinite families of superstars that are strongly amplifying. The same has been claimed for metafunnels. In this paper, we give the first rigorous proof that there is an infinite family of directed graphs that is strongly amplifying. We call the graphs in the family "megastars". When the algorithm is run on an n-vertex graph in this family, starting with a uniformly-chosen mutant, the extinction probability is roughly $n^{-1/2}$ (up to logarithmic factors). We prove that all infinite families of superstars and metafunnels have larger extinction probabilities (as a function of n). Finally, we prove that our analysis of megastars is fairly tight - there is no infinite family of megastars such that the Moran algorithm gives a smaller extinction probability (up to logarithmic factors).
• ### Approximately counting locally-optimal structures(1411.6829)

April 18, 2016 cs.CC
A locally-optimal structure is a combinatorial structure such as a maximal independent set that cannot be improved by certain (greedy) local moves, even though it may not be globally optimal. It is trivial to construct an independent set in a graph. It is easy to (greedily) construct a maximal independent set. However, it is NP-hard to construct a globally-optimal (maximum) independent set. In general, constructing a locally-optimal structure is somewhat more difficult than constructing an arbitrary structure, and constructing a globally-optimal structure is more difficult than constructing a locally-optimal structure. The same situation arises with listing. The differences between the problems become obscured when we move from listing to counting because nearly everything is #P-complete. However, we highlight an interesting phenomenon that arises in approximate counting, where the situation is apparently reversed. Specifically, we show that counting maximal independent sets is complete for #P with respect to approximation-preserving reductions, whereas counting all independent sets, or counting maximum independent sets is complete for an apparently smaller class, $\mathrm{\#RH}\Pi_1$ which has a prominent role in the complexity of approximate counting. Motivated by the difficulty of approximately counting maximal independent sets in bipartite graphs, we also study the problem of approximately counting other locally-optimal structures that arise in algorithmic applications, particularly problems involving minimal separators and minimal edge separators. Minimal separators have applications via fixed-parameter-tractable algorithms for constructing triangulations and phylogenetic trees. Although exact (exponential-time) algorithms exist for listing these structures, we show that the counting problems are #P-complete with respect to both exact and approximation-preserving reductions.
• ### The complexity of counting locally maximal satisfying assignments of Boolean CSPs(1509.03543)

April 6, 2016 cs.CC
We investigate the computational complexity of the problem of counting the maximal satisfying assignments of a Constraint Satisfaction Problem (CSP) over the Boolean domain {0,1}. A satisfying assignment is maximal if any new assignment which is obtained from it by changing a 0 to a 1 is unsatisfying. For each constraint language Gamma, #MaximalCSP(Gamma) denotes the problem of counting the maximal satisfying assignments, given an input CSP with constraints in Gamma. We give a complexity dichotomy for the problem of exactly counting the maximal satisfying assignments and a complexity trichotomy for the problem of approximately counting them. Relative to the problem #CSP(Gamma), which is the problem of counting all satisfying assignments, the maximal version can sometimes be easier but never harder. This finding contrasts with the recent discovery that approximately counting maximal independent sets in a bipartite graph is harder (under the usual complexity-theoretic assumptions) than counting all independent sets.
• ### Approximately Counting H-Colourings is #BIS-Hard(1502.01335)

Dec. 23, 2015 cs.DM, cs.CC
We consider the problem of counting H-colourings from an input graph G to a target graph H. We show that if H is any fixed graph without trivial components, then the problem is as hard as the well-known problem #BIS, which is the problem of (approximately) counting independent sets in a bipartite graph. #BIS is a complete problem in an important complexity class for approximate counting, and is believed not to have an FPRAS. If this is so, then our result shows that for every graph H without trivial components, the H-colouring counting problem has no FPRAS. This problem was studied a decade ago by Goldberg, Kelk and Paterson. They were able to show that approximately sampling H-colourings is #BIS-hard, but it was not known how to get the result for approximate counting. Our solution builds on non-constructive ideas using the work of Lovasz.
• ### #BIS-Hardness for 2-Spin Systems on Bipartite Bounded Degree Graphs in the Tree Nonuniqueness Region(1311.4451)

Sept. 21, 2015 cs.CC
Counting independent sets on bipartite graphs (#BIS) is considered a canonical counting problem of intermediate approximation complexity. It is conjectured that #BIS neither has an FPRAS nor is as hard as #SAT to approximate. We study #BIS in the general framework of two-state spin systems on bipartite graphs. We define two notions, nearly-independent phase-correlated spins and unary symmetry breaking. We prove that it is #BIS-hard to approximate the partition function of any 2-spin system on bipartite graphs supporting these two notions. As a consequence, we classify the complexity of approximating the partition function of antiferromagnetic 2-spin systems on bounded-degree bipartite graphs.
• ### Counting Homomorphisms to Square-Free Graphs, Modulo 2(1501.07539)

Aug. 26, 2015 math.CO, cs.CC
We study the problem HomsTo$H$ of counting, modulo 2, the homomorphisms from an input graph to a fixed undirected graph $H$. A characteristic feature of modular counting is that cancellations make wider classes of instances tractable than is the case for exact (non-modular) counting, so subtle dichotomy theorems can arise. We show the following dichotomy: for any $H$ that contains no 4-cycles, HomsTo$H$ is either in polynomial time or is $\oplus P$-complete. This confirms a conjecture of Faben and Jerrum that was previously only known to hold for trees and for a restricted class of treewidth-2 graphs called cactus graphs. We confirm the conjecture for a rich class of graphs including graphs of unbounded treewidth. In particular, we focus on square-free graphs, which are graphs without 4-cycles. These graphs arise frequently in combinatorics, for example in connection with the strong perfect graph theorem and in certain graph algorithms. Previous dichotomy theorems required the graph to be tree-like so that tree-like decompositions could be exploited in the proof. We prove the conjecture for a much richer class of graphs by adopting a much more general approach.
• ### Counting list matrix partitions of graphs(1306.5176)

April 17, 2015 cs.CC
Given a symmetric D*D matrix M over {0,1,*}, a list M-partition of a graph G is a partition of G's vertices into D parts associated with the rows of M. The part of each vertex is chosen from a given list so that no edge of G maps to a 0 in M and no non-edge of G maps to a 1 in M. Many important graph-theoretic structures can be represented as list M-partitions, such as graph colourings, split graphs and homogeneous sets and pairs, which arise in the proofs of the weak and strong perfect graph conjectures. There has been quite a bit of work on determining for which matrices M computations involving list M-partitions are tractable. We focus on counting list M-partitions, given a graph G and a list for each vertex of G. We identify a set of "tractable" matrices and give an algorithm that counts list M-partitions in polynomial time for every (fixed) matrix M in this set. The algorithm uses data structures such as sparse-dense partitions and subcube decompositions to reduce each instance to a sequence of instances in which the lists restrict access to portions of M in which the interaction of 0s and 1s is controlled. We solve the resulting restricted instances by converting them into counting constraint satisfaction problems (#CSPs) which we solve using arc-consistency. For every matrix M for which our algorithm fails, we show that counting list M-partitions is #P-complete. Further, we give an explicit characterisation of the dichotomy theorem: counting list M-partitions is in FP if M has a structure called a derectangularising sequence; otherwise, counting list M-partitions is #P-hard. We show that the meta-problem of determining whether a given matrix has a derectangularising sequence is NP-complete. Finally, we show that lists can be used to encode cardinality restrictions in M-partitions problems and use this to give a polynomial-time algorithm for counting homogeneous pairs in graphs.
• ### The Complexity of Computing the Sign of the Tutte Polynomial(1202.0313)

Oct. 8, 2014 math.CO, cs.CC
We study the complexity of computing the sign of the Tutte polynomial of a graph. As there are only three possible outcomes (positive, negative, and zero), this seems at first sight more like a decision problem than a counting problem. Surprisingly, however, there are large regions of the parameter space for which computing the sign of the Tutte polynomial is actually #P-hard. As a trivial consequence, approximating the polynomial is also #P-hard in this case. Thus, approximately evaluating the Tutte polynomial in these regions is as hard as exactly counting the satisfying assignments to a CNF Boolean formula. For most other points in the parameter space, we show that computing the sign of the polynomial is in FP, whereas approximating the polynomial can be done in polynomial time with an NP oracle. As a special case, we completely resolve the complexity of computing the sign of the chromatic polynomial - this is easily computable at q=2 and when q is less than or equal to 32/27, and is NP-hard to compute for all other values of the parameter q.