The Complexity of Modular Counting in Constraint Satisfaction Problems.
Abstract
Constraint Satisfaction Problems are a broad class of combinatorial problems,
including several classical decision problems such as graph colouring and SAT,
and a range of problems from other areas, including statistical physics, DNA
sequencing and scheduling problems. There are a variety of dichotomy theorems
for various subclasses of CSP in various complexity classes, one of the most
noteable is Bulatov's proof that a dichotomy holds for #CSP [Bul08], that is,
all #CSP problems are either #P-complete or in FP.
In this thesis, we look at the complexity of modular counting in some re-
stricted classes of CSP, answering questions of the sort \What is the number of
solutions to this CSP modulo k?" for various k. In particular, we discuss CSP
restricted to relations on the domain of size 2, Boolean CSP or Generalised Sat-
is ability, and CSP restricted to a single, symmetric, binary relation, or Graph
Homomorphism. In [CH96], Creignou and Hermann proved a dichotomy the-
orem for counting solutions to Boolean CSP problems, and characterised the
easy cases. We provide a proof of a dichotomy theorem for #kBoolean CSP for
all k, characterising the easy cases.
In [DG00], Dyer and Greenhill proved a dichotomy theorem for counting the
3
4
number of homomorphisms into a xed graph H, or H-colouring, and provided
a characterisation of the types of H for which the problem is tractable. We
give some results on
L
H-colouring. We give a conjectured dichotomy for the
general
L
H-colouring problem, based on a condition related to the automor-
phism group of H. We show that this dichotomy holds for the case in which H
is restricted to be a tree, and give some results about the complexity of deter-
mining, given an arbitrary H, whether the associated H-colouring problem is
tractable assuming the dichotomy holds.
Authors
Faben, JohnCollections
- Theses [3600]