Search

We show that the flip chain for non-crossing spanning trees of $n+1$ points in convex position mixes in time $O(n^8\log n)$., Comment: 19 pages, 6 figures

The hard-core model has as its configurations the independent sets of some graph instance $G$. The probability distribution on independent sets is controlled by a `fugacity' $\lambda>0$, with higher $\lambda$ leading to denser configurations. We investigate the mixing time of Glauber (single-site) dynamics for the hard-core model on restricted classes of bounded-degree graphs in which a particular graph $H$ is excluded as an induced subgraph. If $H$ is a subdivided claw then, for all $\lambda$, the mixing time is $O(n\log n)$, where $n$ is the order of $G$. This extends a result of Chen and Gu for claw-free graphs. When $H$ is a path, the set of possible instances is finite. For all other $H$, the mixing time is exponential in $n$ for sufficiently large $\lambda$, depending on $H$ and the maximum degree of $G$.

We present a perfect marginal sampler of the unique Gibbs measure of a spin system on $\mathbb Z^2$. The algorithm is an adaptation of a previous `lazy depth-first' approach by the authors, but relaxes the requirement of strong spatial mixing to weak. It exploits a classical result in statistical physics relating weak spatial mixing on $\mathbb Z^2$ to strong spatial mixing on squares. When the spin system exhibits weak spatial mixing, the run-time of our sampler is linear in the size of sample. Applications of note are the ferromagnetic Potts model at supercritical temperatures, and the ferromagnetic Ising model with consistent non-zero external field at any non-zero temperature.

We give a simple polynomial-time approximation algorithm for the total variation distance between two product distributions.

We present a simple algorithm that perfectly samples configurations from the unique Gibbs measure of a spin system on a potentially infinite graph $G$. The sampling algorithm assumes strong spatial mixing together with subexponential growth of $G$. It produces a finite window onto a perfect sample from the Gibbs distribution. The run-time is linear in the size of the window.

Partial Rejection Sampling is an algorithmic approach to obtaining a perfect sample from a specified distribution. The objects to be sampled are assumed to be represented by a number of random variables. In contrast to classical rejection sampling, in which all variables are resampled until a feasible solution is found, partial rejection sampling aims at greater efficiency by resampling only a subset of variables that `go wrong'. Partial rejection sampling is closely related to Moser and Tardos' algorithmic version of the Lov\'asz Local Lemma, but with the additional requirement that a specified output distribution should be met. This article provides a largely self-contained account of the basic form of the algorithm and its analysis., Comment: Some expansion/clarification, especially in Section 4, two extra figures

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., Comment: 15 pages. Minor edits, including a small change to the title. This version is accepted for publication in Discrete and Computational Geometry

We present a polynomial-time Markov chain Monte Carlo algorithm for estimating the partition function of the antiferromagnetic Ising model on any line graph. The analysis of the algorithm exploits the "winding" technology devised by McQuillan [CoRR abs/1301.2880 (2013)] and developed by Huang, Lu and Zhang [Proc. 27th Symp. on Disc. Algorithms (SODA16), 514-527]. We show that exact computation of the partition function is #P-hard, even for line graphs, indicating that an approximation algorithm is the best that can be expected. We also show that Glauber dynamics for the Ising model is rapidly mixing on line graphs, an example being the kagome lattice., Comment: Minor revisions. The version is accepted for publication in Combinatorics, Probability and Computing

Jerrum, Sinclair and Vigoda (2004) showed that the permanent of any square matrix can be estimated in polynomial time. This computation can be viewed as approximating the partition function of edge-weighted matchings in a bipartite graph. Equivalently, this may be viewed as approximating the partition function of vertex-weighted independent sets in the line graph of a bipartite graph. Line graphs of bipartite graphs are perfect graphs, and are known to be precisely the class of (claw, diamond, odd hole)-free graphs. So how far does the result of Jerrum, Sinclair and Vigoda extend? We first show that it extends to (claw, odd hole)-free graphs, and then show that it extends to the even larger class of (fork, odd hole)-free graphs. Our techniques are based on graph decompositions, which have been the focus of much recent work in structural graph theory, and on structural results of Chvatal and Sbihi (1988), Maffray and Reed (1999) and Lozin and Milanic (2008)., Comment: 25 pages, 11 figures

We study the joint components in a random `double graph' that is obtained by superposing red and blue binomial random graphs on $n$~vertices. A joint component is a maximal set of vertices, which contains both a red and a blue spanning tree. We show that there are critical pairs of red and blue edge densities at which a joint-giant component appears. In contrast to the standard binomial graph model, the phase transition is first order: the size of the largest joint component jumps from $O(1)$ vertices to $\Theta(n)$ at the critical point. We connect this phenomenon to the properties of a certain bicoloured branching process., Comment: 18 pages, 2 figures. arXiv admin note: text overlap with arXiv:math/0511093 by other authors

In the Ising model, we consider the problem of estimating the covariance of the spins at two specified vertices. In the ferromagnetic case, it is easy to obtain an additive approximation to this covariance by repeatedly sampling from the relevant Gibbs distribution. However, we desire a multiplicative approximation, and it is not clear how to achieve this by sampling, given that the covariance can be exponentially small. Our main contribution is a fully polynomial time randomised approximation scheme (FPRAS) for the covariance. We also show that that the restriction to the ferromagnetic case is essential --- there is no FPRAS for multiplicatively estimating the covariance of an antiferromagnetic Ising model unless RP = #P. In fact, we show that even determining the sign of the covariance is #P-hard in the antiferromagnetic case., Comment: To Appear in ACM ToCT

We give a fully polynomial-time randomised approximation scheme (FPRAS) for the number of bases in a bicircular matroids. This is a natural class of matroids for which counting bases exactly is #P-hard and yet approximate counting can be done efficiently., Comment: v3: updated introduction and a slightly better run-time bound. v4: minor revisions; this version is accepted for publication in Combinatorics, Probability and Computing (CPC)

We present a perfect simulation of the hard disks model via the partial rejection sampling method. Provided the density of disks is not too high, the method produces exact samples in $O(\log n)$ rounds, and total time $O(n)$, where $n$ is the expected number of disks. The method extends easily to the hard spheres model in $d>2$ dimensions. In order to apply the partial rejection method to this continuous setting, we provide an alternative perspective of its correctness and run-time analysis that is valid for general state spaces., Comment: Minor revisions. This version is accepted for publication in Annales de l'Institut Henri Poincar\'e D

We give a fully polynomial-time randomized approximation scheme (FPRAS) for the all-terminal network reliability problem, which is to determine the probability that, in a undirected graph, assuming each edge fails independently, the remaining graph is still connected. Our main contribution is to confirm a conjecture by Gorodezky and Pak (Random Struct. Algorithms, 2014), that the expected running time of the "cluster-popping" algorithm in bi-directed graphs is bounded by a polynomial in the size of the input., Comment: accepted to SICOMP

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$., Comment: To appear in Transactions of Algorithms (TALG)

We propose a new algorithmic framework, called "partial rejection sampling", to draw samples exactly from a product distribution, conditioned on none of a number of bad events occurring. Our framework builds (perhaps surprising) new connections between the variable framework of the Lov\'asz Local Lemma and some classical sampling algorithms such as the "cycle-popping" algorithm for rooted spanning trees. Among other applications, we discover new algorithms to sample satisfying assignments of k-CNF formulas with bounded variable occurrences., Comment: 29 pages

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., Comment: 42 pages, 6 figures; minor corrections

We show that the mixing time of Glauber (single edge update) dynamics for the random cluster model at $q=2$ is bounded by a polynomial in the size of the underlying graph. As a consequence, the Swendsen-Wang algorithm for the ferromagnetic Ising model at any temperature has the same polynomial mixing time bound.

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., Comment: To appear in ACM Transactions on Computation Theory

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., Comment: V2 adds contextual material relating the results obtained here to earlier work in a different but related setting. The technical content is unchanged. V3 (this version) incorporates minor revisions. The title has been changed to better reflect what is novel in this work. This version has been accepted for publication in Theoretical Computer Science. 19 pages

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.

We study a simple Markov chain, the switch chain, on the set of all perfect matchings in a bipartite graph. This Markov chain was proposed by Diaconis, Graham and Holmes as a possible approach to a sampling problem arising in Statistics. We ask: for which classes of graphs is the Markov chain ergodic and for which is it rapidly mixing? We provide a precise answer to the ergodicity question and close bounds on the mixing question. We show for the first time that the mixing time of the switch chain is polynomial in the case of monotone graphs, a class that includes examples of interest in the statistical setting., Comment: 31 pages

We consider the problem of counting, in a given graph, the number of induced k-vertex subgraphs which have an even number of edges, and also the complementary problem of counting the k-vertex induced subgraphs having an odd number of edges. We demonstrate that both problems are #W[1]-hard when parameterised by k, in fact proving a somewhat stronger result about counting subgraphs with a property that only holds for some subset of k-vertex subgraphs which have an even (respectively odd) number of edges. On the other hand, we show that the problems of counting even and odd k-vertex induced subgraphs both admit an FPTRAS. These approximation schemes are based on a surprising structural result, which exploits ideas from Ramsey theory., Comment: Author final version, to appear in Combinatorica

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.

We consider parameterised subgraph-counting problems of the following form: given a graph G, how many k-tuples of its vertices have a given property? A number of such problems are known to be #W[1]-complete; here we substantially generalise some of these existing results by proving hardness for two large families of such problems. We demonstrate that it is #W[1]-hard to count the number of k-vertex subgraphs having any property where the number of distinct edge-densities of labelled subgraphs that satisfy the property is o(k^2). In the special case that the property in question depends only on the number of edges in the subgraph, we give a strengthening of this result which leads to our second family of hard problems., Comment: A few more minor changes. This version to appear in the ACM Transactions on Computation Theory

Given a graph G, we investigate the question of determining the parity of the number of homomorphisms from G to some other fixed graph H. We conjecture that this problem exhibits a complexity dichotomy, such that all parity graph homomorphism problems are either polynomial-time solvable or parityP-complete, and provide a conjectured characterisation of the easy cases. We show that the conjecture is true for the restricted case in which the graph H is a tree, and provide some tools that may be useful in further investigation into the parity graph homomorphism problem, and the problem of counting homomorphisms for other moduli., Comment: 22 pages

We introduce a class of parameterised counting problems on graphs, p-#Induced Subgraph With Property(\Phi), which generalises a number of problems which have previously been studied. This paper focusses on the case in which \Phi defines a family of graphs whose edge-minimal elements all have bounded treewidth; this includes the special case in which \Phi describes the property of being connected. We show that exactly counting the number of connected induced k-vertex subgraphs in an n-vertex graph is #W[1]-hard, but on the other hand there exists an FPTRAS for the problem; more generally, we show that there exists an FPTRAS for p-#Induced Subgraph With Property(\Phi) whenever \Phi is monotone and all the minimal graphs satisfying \Phi have bounded treewidth. We then apply these results to a counting version of the Graph Motif problem., Comment: Final version, to appear in JCSS

We study two computational problems, parameterised by a fixed tree H. #HomsTo(H) is the problem of counting homomorphisms from an input graph G to H. #WHomsTo(H) is the problem of counting weighted homomorphisms to H, given an input graph G and a weight function for each vertex v of G. Even though H is a tree, these problems turn out to be sufficiently rich to capture all of the known approximation behaviour in #P. We give a complete trichotomy for #WHomsTo(H). If H is a star then #WHomsTo(H) is in FP. If H is not a star but it does not contain a certain induced subgraph J_3 then #WHomsTo(H) is equivalent under approximation-preserving (AP) reductions to #BIS, the problem of counting independent sets in a bipartite graph. This problem is complete for the class #RHPi_1 under AP-reductions. Finally, if H contains an induced J_3 then #WHomsTo(H) is equivalent under AP-reductions to #SAT, the problem of counting satisfying assignments to a CNF Boolean formula. Thus, #WHomsTo(H) is complete for #P under AP-reductions. The results are similar for #HomsTo(H) except that a rich structure emerges if H contains an induced J_3. We show that there are trees H for which #HomsTo(H) is #SAT-equivalent (disproving a plausible conjecture of Kelk). There is an interesting connection between these homomorphism-counting problems and the problem of approximating the partition function of the ferromagnetic Potts model. In particular, we show that for a family of graphs J_q, parameterised by a positive integer q, the problem #HomsTo(H) is AP-interreducible with the problem of approximating the partition function of the q-state Potts model. It was not previously known that the Potts model had a homomorphism-counting interpretation. We use this connection to obtain some additional upper bounds for the approximation complexity of #HomsTo(J_q).

We consider the problem of approximating the partition function of the hard-core model on planar graphs of degree at most 4. We show that when the activity lambda is sufficiently large, there is no fully polynomial randomised approximation scheme for evaluating the partition function unless NP=RP. The result extends to a nearby region of the parameter space in a more general two-state spin system with three parameters. We also give a polynomial-time randomised approximation scheme for the logarithm of the partition function.

We study the complexity of approximately solving the weighted counting constraint satisfaction problem #CSP(F). In the conservative case, where F contains all unary functions, there is a classification known for the case in which the domain of functions in F is Boolean. In this paper, we give a classification for the more general problem where functions in F have an arbitrary finite domain. We define the notions of weak log-modularity and weak log-supermodularity. We show that if F is weakly log-modular, then #CSP(F)is in FP. Otherwise, it is at least as difficult to approximate as #BIS, the problem of counting independent sets in bipartite graphs. #BIS is complete with respect to approximation-preserving reductions for a logically-defined complexity class #RHPi1, and is believed to be intractable. We further sub-divide the #BIS-hard case. If F is weakly log-supermodular, then we show that #CSP(F) is as easy as a (Boolean) log-supermodular weighted #CSP. Otherwise, we show that it is NP-hard to approximate. Finally, we give a full trichotomy for the arity-2 case, where #CSP(F) is in FP, or is #BIS-equivalent, or is equivalent in difficulty to #SAT, the problem of approximately counting the satisfying assignments of a Boolean formula in conjunctive normal form. We also discuss the algorithmic aspects of our classification., Comment: Minor revision

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., Comment: minor updates. This is the final version (to appear in SICOMP)

Ge and Stefankovic have recently introduced a novel two-variable graph polynomial. When specialised to a bipartite graphs G and evaluated at the point (1/2,1) this polynomial gives the number of independent sets in the graph. Inspired by this polynomial, they also introduced a Markov chain which, if rapidly mixing, would provide an efficient sampling procedure for independent sets in G. This sampling procedure in turn would imply the existence of efficient approximation algorithms for a number of significant counting problems whose complexity is so far unresolved. The proposed Markov chain is promising, in the sense that it overcomes the most obvious barrier to mixing. However, we show here, by exhibiting a sequence of counterexamples, that the mixing time of their Markov chain is exponential in the size of the input when the input is chosen from a particular infinite family of bipartite graphs.

An important tool in the study of the complexity of Constraint Satisfaction Problems (CSPs) is the notion of a relational clone, which is the set of all relations expressible using primitive positive formulas over a particular set of base relations. Post's lattice gives a complete classification of all Boolean relational clones, and this has been used to classify the computational difficulty of CSPs. Motivated by a desire to understand the computational complexity of (weighted) counting CSPs, we develop an analogous notion of functional clones and study the landscape of these clones. One of these clones is the collection of log-supermodular (lsm) functions, which turns out to play a significant role in classifying counting CSPs. In the conservative case (where all nonnegative unary functions are available), we show that there are no functional clones lying strictly between the clone of lsm functions and the total clone (containing all functions). Thus, any counting CSP that contains a single nontrivial non-lsm function is computationally as hard to approximate as any problem in #P. Furthermore, we show that any non-trivial functional clone (in a sense that will be made precise) contains the binary function "implies". As a consequence, in the conservative case, all non-trivial counting CSPs are as hard as #BIS, the problem of counting independent sets in a bipartite graph. Given the complexity-theoretic results, it is natural to ask whether the "implies" clone is equivalent to the clone of lsm functions. We use the Mobius transform and the Fourier transform to show that these clones coincide precisely up to arity 3. It is an intriguing open question whether the lsm clone is finitely generated. Finally, we investigate functional clones in which only restricted classes of unary functions are available., Comment: corrected typo in title :-)

We investigate the computational difficulty of approximating the partition function of the ferromagnetic Ising model on a regular matroid. Jerrum and Sinclair have shown that there is a fully polynomial randomised approximation scheme (FPRAS) for the class of graphic matroids. On the other hand, the authors have previously shown, subject to a complexity-theoretic assumption, that there is no FPRAS for the class of binary matroids, which is a proper superset of the class of graphic matroids. In order to map out the region where approximation is feasible, we focus on the class of regular matroids, an important class of matroids which properly includes the class of graphic matroids, and is properly included in the class of binary matroids. Using Seymour's decomposition theorem, we give an FPRAS for the class of regular matroids., Comment: New Lemma 4 provides a smoother derivation of the two lemmas now numbered 5 and 6. The old Lemma 2 is not now needed, and the appendix is shorter. Various clarifications have been made and typos corrected

We consider the problem of approximating certain combinatorial polynomials. First, we consider the problem of approximating the Tutte polynomial of a binary matroid with parameters q>= 2 and gamma. (Relative to the classical (x,y) parameterisation, q=(x-1)(y-1) and gamma=y-1.) A graph is a special case of a binary matroid, so earlier work by the authors shows inapproximability (subject to certain complexity assumptions) for q>2, apart from the trivial case gamma=0. The situation for q=2 is different. Previous results for graphs imply inapproximability in the region -2<=gamma<0, apart from at two "special points" where the polynomial can be computed exactly in polynomial time. For binary matroids, we extend this result by showing (i) there is no FPRAS in the region gamma<-2 unless NP=RP, and (ii) in the region gamma>0, the approximation problem is hard for the complexity class #RHPi_1 under approximation-preserving (AP) reducibility. The latter result indicates a gap in approximation complexity at q=2: whereas an FPRAS is known in the graphical case, there can be none in the binary matroid case, unless there is an FPRAS for all of #RHPi_1. The result also implies that it is computationally difficult to approximate the weight enumerator of a binary linear code, apart from at the special weights at which the problem is exactly solvable in polynomial time. As a consequence, we show that approximating the cycle index polynomial of a permutation group is hard for #RHPi_1 under AP-reducibility, partially resolving a question that we first posed in 1992.

We give some reductions among problems in (nonnegative) weighted #CSP which restrict the class of functions that needs to be considered in computational complexity studies. Our reductions can be applied to both exact and approximate computation. In particular, we show that a recent dichotomy for unweighted #CSP can be extended to rational-weighted #CSP., Comment: 11 pages

We provide evidence that it is computationally difficult to approximate the partition function of the ferromagnetic q-state Potts model when q>2. Specifically we show that the partition function is hard for the complexity class #RHPi_1 under approximation-preserving reducibility. Thus, it is as hard to approximate the partition function as it is to find approximate solutions to a wide range of counting problems, including that of determining the number of independent sets in a bipartite graph. Our proof exploits the first order phase transition of the "random cluster" model, which is a probability distribution on graphs that is closely related to the q-state Potts model., Comment: Minor corrections

The Tutte polynomial of a graph G is a two-variable polynomial T(G;x,y) that encodes many interesting properties of the graph. We study the complexity of the following problem, for rationals x and y: given as input a planar graph G, determine T(G;x,y). Vertigan completely mapped the complexity of exactly computing the Tutte polynomial of a planar graph. He showed that the problem can be solved in polynomial time if (x,y) is on the hyperbola H_q given by (x-1)(y-1)=q for q=1 or q=2 or if (x,y) is one of the two special points (x,y)=(-1,-1) or (x,y)=(1,1). Otherwise, the problem is #P-hard. In this paper, we consider the problem of approximating T(G;x,y), in the usual sense of "fully polynomial randomised approximation scheme" or FPRAS. Roughly speaking, an FPRAS is required to produce, in polynomial time and with high probability, an answer that has small relative error. Assuming that NP is different from RP, we show that there is no FPRAS for the Tutte polynomial in a large portion of the (x,y) plane. In particular, there is no FPRAS if x>1, y<-1 or if y>1, x<-1 or if x<0, y<0 and q>5. Also, there is no FPRAS if x<1, y<1 and q=3. For q>5, our result is intriguing because it shows that there is no FPRAS at (x,y)=(1-q/(1+epsilon),-epsilon) for any positive epsilon but it leaves open the limit point epsilon=0, which corresponds to approximately counting q-colourings of a planar graph., Comment: In this revision, significant changes have been made to the structure of the paper to clarify the presentation. Extra detail has been provided at certain points in the proofs, and on at least one occasion the exposition has been made more systematic. Some typos have been corrected. The results are unchanged. 28 pages and 5 figures

We consider the complexity of counting homomorphisms from an $r$-uniform hypergraph $G$ to a symmetric $r$-ary relation $H$. We give a dichotomy theorem for $r>2$, showing for which $H$ this problem is in FP and for which $H$ it is #P-complete. This generalises a theorem of Dyer and Greenhill (2000) for the case $r=2$, which corresponds to counting graph homomorphisms. Our dichotomy theorem extends to the case in which the relation $H$ is weighted, and the goal is to compute the \emph{partition function}, which is the sum of weights of the homomorphisms. This problem is motivated by statistical physics, where it arises as computing the partition function for particle models in which certain combinations of $r$ sites interact symmetrically. In the weighted case, our dichotomy theorem generalises a result of Bulatov and Grohe (2005) for graphs, where $r=2$. When $r=2$, the polynomial time cases of the dichotomy correspond simply to rank-1 weights. Surprisingly, for all $r>2$ the polynomial time cases of the dichotomy have rather more structure. It turns out that the weights must be superimposed on a combinatorial structure defined by solutions of an equation over an Abelian group. Our result also gives a dichotomy for a closely related constraint satisfaction problem., Comment: 21 pages

We consider Metropolis Glauber dynamics for sampling proper $q$-colourings of the $n$-vertex complete $b$-ary tree when $3\leq q\leq b/2\ln(b)$. We give both upper and lower bounds on the mixing time. For fixed $q$ and $b$, our upper bound is $n^{O(b/\log b)}$ and our lower bound is $n^{\Omega(b/q \log(b))}$, where the constants implicit in the $O()$ and $\Omega()$ notation do not depend upon $n$, $q$ or $b$.

Partition functions, also known as homomorphism functions, form a rich family of graph invariants that contain combinatorial invariants such as the number of k-colourings or the number of independent sets of a graph and also the partition functions of certain "spin glass" models of statistical physics such as the Ising model. Building on earlier work by Dyer, Greenhill and Bulatov, Grohe, we completely classify the computational complexity of partition functions. Our main result is a dichotomy theorem stating that every partition function is either computable in polynomial time or #P-complete. Partition functions are described by symmetric matrices with real entries, and we prove that it is decidable in polynomial time in terms of the matrix whether a given partition function is in polynomial time or #P-complete. While in general it is very complicated to give an explicit algebraic or combinatorial description of the tractable cases, for partition functions described by a Hadamard matrices -- these turn out to be central in our proofs -- we obtain a simple algebraic tractability criterion, which says that the tractable cases are those "representable" by a quadratic polynomial over the field GF(2).

We give a trichotomy theorem for the complexity of approximately counting the number of satisfying assignments of a Boolean CSP instance. Such problems are parameterised by a constraint language specifying the relations that may be used in constraints. If every relation in the constraint language is affine then the number of satisfying assignments can be exactly counted in polynomial time. Otherwise, if every relation in the constraint language is in the co-clone IM_2 from Post's lattice, then the problem of counting satisfying assignments is complete with respect to approximation-preserving reductions in the complexity class #RH\Pi_1. This means that the problem of approximately counting satisfying assignments of such a CSP instance is equivalent in complexity to several other known counting problems, including the problem of approximately counting the number of independent sets in a bipartite graph. For every other fixed constraint language, the problem is complete for #P with respect to approximation-preserving reductions, meaning that there is no fully polynomial randomised approximation scheme for counting satisfying assignments unless NP=RP.

This paper gives a dichotomy theorem for the complexity of computing the partition function of an instance of a weighted Boolean constraint satisfaction problem. The problem is parameterised by a finite set F of non-negative functions that may be used to assign weights to the configurations (feasible solutions) of a problem instance. Classical constraint satisfaction problems correspond to the special case of 0,1-valued functions. We show that the partition function, i.e. the sum of the weights of all configurations, can be computed in polynomial time if either (1) every function in F is of ``product type'', or (2) every function in F is ``pure affine''. For every other fixed set F, computing the partition function is FP^{#P}-complete., Comment: Minor revision

We give a systematic development of the application of matrix norms to rapid mixing in spin systems. We show that rapid mixing of both random update Glauber dynamics and systematic scan Glauber dynamics occurs if any matrix norm of the associated dependency matrix is less than 1. We give improved analysis for the case in which the diagonal of the dependency matrix is $\mathbf{0}$ (as in heat bath dynamics). We apply the matrix norm methods to random update and systematic scan Glauber dynamics for coloring various classes of graphs. We give a general method for estimating a norm of a symmetric nonregular matrix. This leads to improved mixing times for any class of graphs which is hereditary and sufficiently sparse including several classes of degree-bounded graphs such as nonregular graphs, trees, planar graphs and graphs with given tree-width and genus., Comment: Published in at http://dx.doi.org/10.1214/08-AAP532 the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)

The Tutte polynomial of a graph G is a two-variable polynomial T(G;x,y) that encodes many interesting properties of the graph. We study the complexity of the following problem, for rationals x and y: take as input a graph G, and output a value which is a good approximation to T(G;x,y). Jaeger, Vertigan and Welsh have completely mapped the complexity of exactly computing the Tutte polynomial. They have shown that this is #P-hard, except along the hyperbola (x-1)(y-1)=1 and at four special points. We are interested in determining for which points (x,y) there is a "fully polynomial randomised approximation scheme" (FPRAS) for T(G;x,y). Under the assumption RP is not equal to NP, we prove that there is no FPRAS at (x,y) if (x,y) is in one of the half-planes x<-1 or y<-1 (excluding the easy-to-compute cases mentioned above). Two exceptions to this result are the half-line x<-1, y=1 (which is still open) and the portion of the hyperbola (x-1)(y-1)=2 corresponding to y<-1 which we show to be equivalent in difficulty to approximately counting perfect matchings. We give further intractability results for (x,y) in the vicinity of the origin. A corollary of our results is that, under the assumption RP is not equal to NP, there is no FPRAS at the point (x,y)=(0,1--lambda) when \lambda>2 is a positive integer. Thus there is no FPRAS for counting nowhere-zero \lambda flows for \lambda>2. This is an interesting consequence of our work since the corresponding decision problem is in P for example for \lambda=6., Comment: Minor changes to correct typos and provide clarification. Also includes an extra figure

We address the problem of sampling colorings of a graph $G$ by Markov chain simulation. For most of the article we restrict attention to proper $q$-colorings of a path on $n$ vertices (in statistical physics terms, the one-dimensional $q$-state Potts model at zero temperature), though in later sections we widen our scope to general ``$H$-colorings'' of arbitrary graphs $G$. Existing theoretical analyses of the mixing time of such simulations relate mainly to a dynamics in which a random vertex is selected for updating at each step. However, experimental work is often carried out using systematic strategies that cycle through coordinates in a deterministic manner, a dynamics sometimes known as systematic scan. The mixing time of systematic scan seems more difficult to analyze than that of random updates, and little is currently known. In this article we go some way toward correcting this imbalance. By adapting a variety of techniques, we derive upper and lower bounds (often tight) on the mixing time of systematic scan. An unusual feature of systematic scan as far as the analysis is concerned is that it fails to be time reversible., Comment: Published at http://dx.doi.org/10.1214/105051605000000683 in the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)

We consider finite-state Markov chains that can be naturally decomposed into smaller ``projection'' and ``restriction'' chains. Possibly this decomposition will be inductive, in that the restriction chains will be smaller copies of the initial chain. We provide expressions for Poincare (resp. log-Sobolev) constants of the initial Markov chain in terms of Poincare (resp. log-Sobolev) constants of the projection and restriction chains, together with further a parameter. In the case of the Poincare constant, our bound is always at least as good as existing ones and, depending on the value of the extra parameter, may be much better. There appears to be no previously published decomposition result for the log-Sobolev constant. Our proofs are elementary and self-contained., Comment: Published at http://dx.doi.org/10.1214/105051604000000639 in the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)