
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 antiferromagnetic twospin
models.
Previous analyses of correlationdecay algorithms implicitly depended on the
occurrence of strong spatial mixing (SSM). This means that one uses worstcase
analysis of the recursive procedure that creates the subinstances. We develop
a new analysis method that is more refined than the worstcase 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 upperbound 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 previouslyknown approximation scheme
for Delta=6 is the Markovchain 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 NPhard even within the uniqueness regime.

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
nonmutants 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 mostamplifying 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 stronglyconnected nvertex
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.

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 zerotemperature 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 3state antiferromagnetic Potts model has
uniqueness for all $\beta\geq 13/(d+1)$. The case $d=2$ is critical since it
relates to the 3colourings model on the binary tree ($\beta=0$), which has
nonuniqueness. 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 twostep recursion on the tree, which we
conjecture to be sufficient to establish the uniqueness threshold for all
noncritical cases ($q\neq d+1$).

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
linearsized 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 randomcluster representation of the model. In
particular, we show that a percolationtype algorithm succeeds in sampling from
the randomcluster 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.

We analyse the complexity of approximate counting constraint satisfactions
problems $\mathrm{\#CSP}(\mathcal{F})$, where $\mathcal{F}$ is a set of
nonnegative rationalvalued 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 twospin 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 nontrivial example of a set of
functions satisfying the monotonicity condition.

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 almosttight bound on the expected running time of the
algorithm. For all epsilon > 0, we show that the expected running time on an
nvertex 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.

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 NPhard.
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
cardioidshaped 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 NPhard. 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 #Phard. If $\lambda$ is a
negative real number outside of $\Lambda_\Delta$, we show that it is #Phard 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.

We study the mixing time of random walks on smallworld networks modelled as
follows: starting with the 2dimensional periodic grid, each pair of vertices
$\{u,v\}$ with distance $d>1$ is added as a "longrange" 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$.

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 nonloop 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).

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 NPhard. 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 NPhard 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 NPhard.) 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 fixedparameter algorithms.

We study the problem of approximately evaluating the independent set
polynomial of boundeddegree graphs at a point lambda or, equivalently, the
problem of approximating the partition function of the hardcore 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)=(D1)^(D1)/(D2)^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)=(D1)^(D1)/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 NPhard 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 NPhard.
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).

We study functional clones, which are sets of nonnegative pseudoBoolean
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.

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 approximationpreserving (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 NPhard 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 socalled
"conservative" case.

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 BQPhardness to #Phardness. Moreover, we show that computing the sign of
the Tutte polynomial is #Phard 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.

We examine the computational complexity of approximately counting the list
Hcolourings of a graph. We discover a natural graphtheoretic trichotomy based
on the structure of the graph H. If H is an irreflexive bipartite graph or a
reflexive complete graph then counting list Hcolourings is trivially in
polynomial time. Otherwise, if H is an irreflexive bipartite permutation graph
or a reflexive proper interval graph then approximately counting list
Hcolourings is equivalent to #BIS, the problem of approximately counting
independent sets in a bipartite graph. This is a wellstudied 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 Hcolourings is complete for #P with respect to
approximationpreserving 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 selfcontained
and does not require any universal algebra (unlike similar dichotomies in the
weighted case). We are able to extend the hardness results to the
boundeddegree setting, showing that all hardness results apply to input graphs
with maximum degree at most 6.

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 nonedge to a $1$. We give a computerassisted proof
that, when $D=4$, the problem of counting the $M$partitions of an input
graph is either in FP or is #Pcomplete. 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.

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 2spin systems on boundeddegree
graphs. This classification is based on a beautiful connection to the socalled
uniqueness phase transition from statistical physics on the infinite
$\Delta$regular tree. Our objective is to study the impact of this
classification on unweighted 2spin 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 nontrivial 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 NPhard: given a
$k$uniform hypergraph with maximum degree at most $\Delta$, approximate the
partition function of the hypergraph 2spin model associated with $f$. It is
NPhard 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 2spin model can be computed exactly in polynomial
time.

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 nonmutant) is passed on to an outneighbour 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 stronglyamplifying 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 nvertex
graph in this family, starting with a uniformlychosen 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).

A locallyoptimal 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 NPhard to construct a globallyoptimal
(maximum) independent set. In general, constructing a locallyoptimal structure
is somewhat more difficult than constructing an arbitrary structure, and
constructing a globallyoptimal structure is more difficult than constructing a
locallyoptimal 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 #Pcomplete. 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 approximationpreserving 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
locallyoptimal structures that arise in algorithmic applications, particularly
problems involving minimal separators and minimal edge separators. Minimal
separators have applications via fixedparametertractable algorithms for
constructing triangulations and phylogenetic trees. Although exact
(exponentialtime) algorithms exist for listing these structures, we show that
the counting problems are #Pcomplete with respect to both exact and
approximationpreserving reductions.

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 complexitytheoretic assumptions)
than counting all independent sets.

We consider the problem of counting Hcolourings 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 wellknown 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
Hcolouring 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 Hcolourings is #BIShard, but it was not known how to get the result
for approximate counting. Our solution builds on nonconstructive ideas using
the work of Lovasz.

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 twostate spin systems
on bipartite graphs. We define two notions, nearlyindependent phasecorrelated
spins and unary symmetry breaking. We prove that it is #BIShard to approximate
the partition function of any 2spin system on bipartite graphs supporting
these two notions. As a consequence, we classify the complexity of
approximating the partition function of antiferromagnetic 2spin systems on
boundeddegree bipartite graphs.

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 (nonmodular) counting, so subtle
dichotomy theorems can arise. We show the following dichotomy: for any $H$ that
contains no 4cycles, 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 treewidth2 graphs
called cactus graphs. We confirm the conjecture for a rich class of graphs
including graphs of unbounded treewidth. In particular, we focus on squarefree
graphs, which are graphs without 4cycles. 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 treelike so that treelike 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.

Given a symmetric D*D matrix M over {0,1,*}, a list Mpartition 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 nonedge of G maps to a 1 in M. Many important graphtheoretic
structures can be represented as list Mpartitions, 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 Mpartitions
are tractable. We focus on counting list Mpartitions, 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 Mpartitions in polynomial time for every (fixed)
matrix M in this set. The algorithm uses data structures such as sparsedense
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 arcconsistency. For every matrix M for which our
algorithm fails, we show that counting list Mpartitions is #Pcomplete.
Further, we give an explicit characterisation of the dichotomy theorem:
counting list Mpartitions is in FP if M has a structure called a
derectangularising sequence; otherwise, counting list Mpartitions is #Phard.
We show that the metaproblem of determining whether a given matrix has a
derectangularising sequence is NPcomplete. Finally, we show that lists can be
used to encode cardinality restrictions in Mpartitions problems and use this
to give a polynomialtime algorithm for counting homogeneous pairs in graphs.

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 #Phard. As a
trivial consequence, approximating the polynomial is also #Phard 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 NPhard to
compute for all other values of the parameter q.