1 Introduction
The Constraint Satisfaction Problem (CSP) asks to decide the existence of a homomorphism between two given relational structures (or to find the number of such homomorphisms). It has been used to model a vast variety of combinatorial problems and has attracted much attention. Since the general CSP is NPcomplete (#Pcomplete in the counting case) and because one needs to model specific computational problems, various restricted versions of the CSP have been considered. More precisely, let and be two classes of relational structures. In this paper we will assume that structures from only have predicate symbols of bounded arity. The constraint satisfaction problem (CSP) parametrised by and is the following computational problem, denoted by : given and , is there a homomorphism from to ? CSPs in which both input structures are restricted have not received much attention (with a notable exception of matrix partitions [19, 20] and assorted graph problems on restricted classes of graphs). However, the two most natural restrictions have been intensively studied over the last two decades. Let denote the class of all (boundedarity) relational structures, or, equivalently, indicate that there are no restrictions on the corresponding input structure.
Problems of the form , where is a fixed finite relational structure, are known as nonuniform or languagerestricted CSPs [33]. For instance, if is the complete graph on vertices then is the standard 3Colouring problem [27]. The study of nonuniform CSPs has been initiated by Schaefer [38] who considered the case of for 2element structures . The complexity of , for a fixed graph , was studied under the name of colouring by Hell and Nešetřil [32]. General nonuniform CSPs have been studied extensively since the seminal paper of Feder and Vardi [21] who in particular proposed the socalled Dichotomy Conjecture stating that every nonuniform CSP is either solvable in polynomial time or is NPcomplete. The complexity of nonuniform CSPs has been resolved only recently in two independent papers by Bulatov [3] and Zhuk [39], which confirmed the dichotomy conjecture of Feder and Vardi and also its algebraic version [4].
CSPs restricted on the other side, that is, of the form , where is a fixed (infinite) class of finite relational structures, are known as structurallyrestricted CSPs. For instance, if is the class of cliques of all sizes then is the standard Clique problem [27]. In this case the complexity of CSPs is related to various “width” parameters of the associated class of graphs. For a relational structure let denote the Gaifman graph of , that is, the graph whose vertices are the elements of , and vertices are connected with an edge whenever and occur in the same tuple of some relation of . Then denotes the class of Gaifman graphs of structures from , and we refer to the treewidth of as the treewidth of . Dalmau, Kolaitis, and Vardi showed that is in PTIME if has bounded treewidth modulo homomorphic equivalence [10]. Grohe then showed that, assuming FPT W[1], there are no other cases of (bounded arity) solvable in polynomial time (or even fixedparameter time, where the parameter is the size of the lefthand side structure) [29]. The case of structures with unbounded arity was extensively studied by Gottlob et al. who introduced the concept of bounded hypertree width in an attempt to characterise structurally restricted CSPs solvable in polynomial time [28]. The search for a right condition is still going on, and the most general structural property that guarantees that is solvable in polynomial time is fractional hypertree width introduced by Grohe and Marx [30].
An important problem related to the CSP is counting: Given a CSP instance, that is, two relational structures and , find the number of homomorphisms from to . We again consider restricted versions of this problem. More precisely, for two classes and of relational structures, denotes the following computational problem: given and , how many homomorphisms are there from to ? This problem is referred to as a counting CSP. Similar to decision CSPs, problems of the form and are the two most studied ways to restrict the counting CSP, and the research on these problems follows a similar pattern as their decision counterparts.
For a fixed finite relational structure , the complexity of the nonuniform problem was characterised for graphs by Dyer and Greenhill [17] and for 2element structures by Creignou and Hermann [8]. The complexity of the general nonuniform counting CSPs was resolved by Bulatov [5] and Dyer and Richerby [18]. As in the case of the decision version the complexity of nonuniform counting CSPs is determined by their algebraic properties, and every such CSP is either solvable in polynomial time or is #Pcomplete. These dichotomy results were later extended to the case of weighted counting CSP, for which Cai and Chen obtained a complexity classification of counting CSPs with complex weights [6].
The complexity of counting CSPs with restrictions on the left hand side structures also turns out to be related to treewidth. Flum and Grohe showed that is solvable in polynomial time if has bounded treewidth [22]. Dalmau and Jonsson then showed that, assuming FPT #W[1], there are no other cases of (bounded arity) solvable exactly in polynomial time (or, again, even fixedparameter time) [9]. Note that the result of Dalmau and Jonsson states that the class itself has to be of bounded treewidth, while in Grohe’s characterisation of polynomialtime solvable decision CSPs of the form it is the class of cores of structures from that has to have bounded treewidth. To the best of our knowledge there has been no research on counting problems over structures of unbounded arity except for the work of BraultBaron et al., who showed that the (unbounded arity) structurallyrestricted are solvable in polynomial time for the class of acyclic hypergraphs [2].^{1}^{1}1BraultBaron et al. [2] show their tractability results for socalled CSPs with default values, which in particular includes as defined here.
The results we have mentioned so far concern exact counting; however, many applications of counting problems allow for approximation algorithms as well. For nonuniform CSPs the complexity landscape is much more complicated than the dichotomy results for decision CSPs or exact counting. The analogue of “easily solvable” problems in this case are those that admit a Fully Polynomial Randomised Approximation Scheme (FPRAS): a randomised algorithm that, given an instance and an error tolerance returns in time polynomial in the size of the instance and
a result which is with high probability a multiplicative
approximation of the exact solution. The parametrised version of this algorithmic model is known as a Fixed Parameter Tractable Randomised Approximation Scheme (FPTRAS). Beyond counting nonuniform CSPs, however, it was conjectured by Dyer et al. [15] that there is an infinite hierarchy of approximation complexities attainable by such problems. Only a handful of results exist for the approximation complexity of counting nonuniform CSPs. The approximation complexity of for 2element structures was characterised by Dyer at al. [16], where a trichotomy theorem was proved: for every 2element structure the problem either admits an FPRAS, or is interreducible with #SAT or with the problem #BIS of counting independent sets in bipartite graphs. Apart from this only partial results are known. If is a connected graph and does not admit an FPRAS, then Galanis, Goldberg and Jerrum [25] showed that is at least as hard as #BIS. Also, if every unary relation is a part of a complexity classification of can be extracted from the results of Chen et al. [7],^{2}^{2}2Chen et al. [7] studied the weighted version of , and although their result does not provide a complete characterisation of the weighted problem, it allows to determine the complexity of as defined here. see also [26].Our Contribution
It should be clear by now that the picture painted by the short survey above misses one piece: the approximation complexity of structurally restricted CSPs. This is the main contribution of this paper.
Let be a class of boundedarity relational structures. If the treewidth of modulo homomorphic equivalence is unbounded then, by Grohe’s result [29], it is hard to test for the existence of a homomorphism from to , where , for any instance of . Using standard techniques (see, e.g., the proof of [34, Proposition 3.16]), this implies, assuming that FPT #W[1] (under randomised parametrised reductions [14]), that there is not an FPTRAS for , let alone an FPRAS. Consequently, the tractability boundary for approximate counting of lies between bounded treewidth and bounded treewidth modulo homomorphic equivalence.
As our main result, we show that for such that a certain class of graphs (to be defined later) is a subset of , cannot be solved even approximately for of unbounded treewidth, assuming FPT W[1] (under randomised parametrised reductions). Before we introduce the classes of graphs we use, we review how the hardness of or is usually proved.
We follow the hardness proof of Grohe for decision CSPs [29], which was lifted to exact counting CSPs by Dalmau and Jonsson [9]. In fact Grohe’s result had an important precursor [31]. The key idea is a reduction from the parametrised Clique problem to . Let and be an instance of the Clique problem, where is the parameter. Broadly speaking, the reduction works as follows. For a class of unbounded treewidth, the Excluded Grid Theorem of Robertson and Seymour [37] guarantees the existence of the grid (as a minor of some structure ), which is used to encode the existence of a clique in as a certain structure . The encoding usually means that has a clique if and only if there is a homomorphism from to whose image covers a copy of the grid built in . For decision CSPs, the correctness of the reduction — that there are no homomorphisms from to not satisfying this condition — is achieved by dealing with coloured grids [31] or by dealing with structures whose cores have unbounded treewidth (with another complication caused by minor maps) [29]. For the complexity of exact counting CSPs, the correctness of the reduction [9]
is achieved by employing interpolation or the inclusionexclusion principle, a common tool in exact counting.
None of these two methods can be applied to approximate solving . We cannot assume that the class of cores of has unbounded treewidth, because then by [29] even the decision problem cannot be solved in polynomial time, which immediately rules out the existence of an FPRAS. Interpolation techniques such as the inclusionexclusion principle are also well known to be incompatible with approximate counting. The standard tool in approximate counting to achieve the same goal of prohibiting homomorphisms except ones from a certain restricted type, is to use gadgets to amplify the number of homomorphisms of the required type. We give a reduction from #Clique to by using “fangrids”, formally introduced in Section 3.3. Unfortunately, due to the delicate nature of approximation preserving reductions, we cannot use minors and minor maps and have to assume that “fangrids” themselves are present in . (In Section 5, we will briefly discuss how a weaker assumption can be used to obtain the same result.) By the Excluded Grid Theorem [37], if is closed under taking minors, then contains all the fangrids (details are given in Section 3.3 and in particular in Lemma 4). Thus, the classes for which we establish the hardness of includes the classes that are closed under taking minors.^{3}^{3}3We remark that the hardness for closed under taking minors follows from Grohe’s classification [29] of decision CSPs. Indeed, for of unbounded treewidth, the Excluded Grid Theorem [37] gives grids of arbitrary sizes. Since every planar graph is a minor of some grid [11], contains all planar graphs. As there exist graphs of arbitrary large treewidth that are also minimal with respect to homomorphic equivalence, Grohe’s result gives W[1]hardness of and hence cannot have an FPRAS/FPTRAS.
2 Preliminaries
denotes the set of positive integers. For every , we let .
2.1 Relational Structures and Homomorphisms
A relational signature is a finite set of relation symbols , each with a specified arity . A relational structure over a relational signature (or a structure, for short) is a finite universe together with one relation for each symbol . The size of a relational structure is defined as
Let be a binary relational symbol. We will sometimes view graphs as structures.
A homomorphism from a relational structure (with universe ) to a relational structure (with universe ) is a mapping such that for all and all tuples we have .
Two structures and are homomorphically equivalent if there is a homomorphism from to and a homomorphism from to .
Let be a class of relational structures. We say that has bounded arity if there is a constant such that for every structure and , we have that .
2.2 Treewidth and Minors
The notion of treewidth, introduced by Robertson and Seymour [36], is a wellknown measure of the treelikeness of a graph [11]. Let be a graph. A tree decomposition of is a pair where is a tree and is a function that maps each node to a subset of such that

,

for every , the set induces a connected subgraph of , and

for every edge , there is a node with .
The width of the decomposition is . The treewidth of a graph is the minimum width over all its tree decompositions.
Let be a relational structure over relational signature . The Gaifman graph (also known as primal graph) of , denoted by , is the graph whose vertex set is the universe of and whose edges are the pairs for which there is a tuple and a relation symbol such that appear in and .
Let be a class of relational structures. We say that has bounded treewidth if there exists such that for every . We say that has bounded treewidth modulo homomorphic equivalence if there exists such that every is homomorphically equivalent to with .
A graph is a minor of a graph if is isomorphic to a graph that can be obtained from a subgraph of by contracting edges (for more details, see, e.g., [11]).
For , the grid is the graph with the vertex set and an edge between and iff . Treewidth and minors are intimately connected via the celebrated Excluded Grid Theorem of Robertson and Seymour.
Theorem 1 ([37]).
For every there exists a such that the grid is a minor of every graph of treewidth at least .
Let be a class of relational structures. We say that if closed under taking minors if for every and for every minor of , there is a structure such that is isomorphic to .
3 Counting CSP
3.1 Exact Counting CSP
Let be a class of relational structures. We will be interested in the computational complexity of the following problem.
We say that is in FP, the class of function problems solvable in polynomial time, if there is a deterministic algorithm that solves any instance of in time .
We will also consider the parametrised version of .
We say that  is in FPT, the class of problems that are fixedparameter tractable, if there is a deterministic algorithm that solves any instance of  in time , where is an arbitrary computable function.
The class W[1], introduced in [12], can be seen as an analogue of NP in parameterised complexity theory. Proving W[1]hardness of a problem (under a parametrised reduction which may be randomised), is a strong indication that the problem is not solvable in fixedparameter time as it is believed that FPT W[1]. For counting problems, #W[1] is the parametrised analogue of #P. Similarly to the belief that FP #P, it is believed that FPT #W[1]. We refer the reader to [24] for the definitions of W[1] and #W[1], and for more details on parameterised complexity in general.
Dalmau and Jonsson established the following result.
Theorem 2 ([9]).
Assume FPT #W[1] under parametrised reductions. Let be a recursively enumerable class of relational structures of bounded arity. Then, the following are equivalent:

is in FP.

 is in FPT.

has bounded treewidth.
The following problem is an example of a #W[1]hard problem, as established by Flum and Grohe [23].
Note that #Clique can be modelled as  if we set to be the set of cliques of all possible sizes. The decision version of #Clique was shown to be W[1]hard by Downey and Fellows [13].
3.2 Approximate Counting CSP
In view of our complete understanding of the exact complexity of for of bounded arity (cf. Theorem 2), we will be interested in approximation algorithms for . In particular, are there any new classes of bounded arity for which the problem can be solved efficiently (if only approximately)? We will provide a partial answer to this question (cf. Theorem 3): for certain general boundedarity classes (which include classes that are closed under taking minors), the answer is no!
The notion of efficiency for approximate counting is that of a fully polynomial randomised approximation scheme [35] and its parametrised analogue, a fixed parameter tractable randomised approximation scheme, originally introduced by Arvind and Raman [1]. We now define both concepts.
A randomised approximation scheme (RAS) for a function is a randomised algorithm that takes as input
and produces as output an integer random variable
satisfying the condition . A RAS for a counting problem is called fully polynomial (FPRAS) if on input of size it runs in time for some fixed polynomial . A RAS for a parametrised counting problem is called fixed parameter tractable (FPTRAS) if on input of size with parameter it runs in time , where is a fixed polynomial and is an arbitrary computable function.To compare approximation complexity of (parametrised) counting problems two types of reductions are used. Suppose . An approximation preserving reduction (APreduction) [15] from to
is a probabilistic oracle Turing machine
that takes as input a pair , and satisfies the following three conditions: (i) every oracle call made by is of the form , where is an instance of , and is an error bound satisfying ; (ii) the TM meets the specification for being a randomised approximation scheme for whenever the oracle meets the specification for being a randomised approximation scheme for ; and (iii) the running time of is polynomial in and .Similar to [34] we also use the parametrised version of APreductions. Again, let . A parametrised approximation preserving reduction (parametrised APreduction) from to is a probabilistic oracle Turing machine that takes as input a triple , and satisfies the following three conditions: (i) every oracle call made by is of the form , where is an instance of , for some computable function , and is an error bound satisfying ; (ii) the TM meets the specification for being a randomised approximation scheme for whenever the oracle meets the specification for being a randomised approximation scheme for ; and (iii) is fixedparameter tractable with respect to and polynomial in and .
3.3 Main Result
The following concept plays a key role in this paper. Let . The fangrid is a graph with vertex set , where , , where are disjoint and for , and for . Vertices from will be called grid vertices. Vertices , , , , , , , , , , , will be called fan vertices, and will be called corner vertices. The edges of the fan grid are as follows: for , and for each and , see Figure 1.
We call a class of relational structures of bounded arity a fan class if either has bounded treewidth or for any parameters we have that contains the fangrid .
The following is our main result.
Theorem 3 (Main).
Assume FPT W[1] under randomised parametrised reductions. Let be a recursively enumerable class of relational structures of bounded arity. If is a fan class then the following are equivalent:

is polynomial time solvable.

admits an FPRAS.

 admits an FPTRAS.

has bounded treewidth.
Let be a recursively enumerable class of relational structures of bounded arity and closed under taking minors. We claim that is a fan class and thus Theorem 3 applies to such . For this we need Theorem 1. In particular, for any , if is not of bounded treewidth then, by Theorem 1, contains an grid, where , and thus also a grid. The following simple lemma then shows that fangrids are minors of grids (of appropriate size).
Lemma 4.
is a minor of grid, where , .
Proof.
Take the subgraph of the grid as shown in Figure 2 and contract the paths shown with thicker edges. ∎
4 Proof of Theorem 3
Conditions (1) and (4) in Theorem 3 are equivalent by [9]. Implications “(1) (2) (3)” are obvious; implication “(4) (1)” is by the standard treewidthbased dynamic programming for exact counting. Our main contribution is to prove the “(3) (4)” implication.
4.1 Construction
Let be a graph with and . Let . We construct a graph for as follows. Let and let be a correspondence between and the set of 2element sets . For and , we write rather than . The vertex set of is the union of two sets , defined by
where are disjoint and for , for .
As in fangrids, vertices of the form , , , , , , , , , , , will be called fan vertices, and vertices of the form , , , will be called corner vertices.
The edge set of consists of the following pairs:

such that ;

such that ;

for and , where is an arbitrary subset of whose cardinality is such that the degree of is exactly ;
similarly, , , , , , , , , , , for (for in this order) and , , , , , , , , , , , where are arbitrary subsets whose cardinality is such that the degree of is exactly and the degree of the remaining vertices from the list is exactly .
We study homomorphisms from to . A homomorphism is said to be cornertocorner (or cc for short) if
Homomorphism
is called identity (skew identity) if
(respectively, ) for all and . Sometimes we will abuse the terminology and call a (skew) identity homomorphism the restriction of such homomorphism to (the set of grid vertices).We define the weight of a homomorphism from restricted to (the set of grid vertices) to as the number of extensions of to a homomorphism from .
4.2 Weights of Homomorphisms
We start with a simple lemma.
Lemma 5.
The weight of an identity or skew identity homomorphism is .
Proof.
The images of grid vertices (the set ) under identity and skew identity homomorphisms are fixed, while vertices from can be mapped to any neighbour of the corresponding fan vertex independently. Since the degree of a corner vertex with and is , and the degree of any other fan vertex is , the result follows. ∎
The next lemma, which will be proved using Lemma 5, is essentially [9, Lemma 3.1] adapted to our setting, which in turn builds on [29, Lemma 4.4].
Lemma 6.
Let be the number of cliques in . Then the total weight of identity and skew identity homomorphisms is .
Proof.
We will show that the total weight of identity homomorphisms is . The same argument works for skew identity homomorphisms. First we give a description of all identity homomorphisms. Let be the vertex set of a clique in . For with , let be the edge in between and . We define by
for every and .
We will need two claims; the first one follows directly from the definition.
Claim 1. is an identity homomorphism from to .
Claim 2. If is an identity homomorphism from to then for some vertex set of a clique in .
Proof of Claim 2. Let be an identity homomorphism from to .
For every and , we have for some and with . Let . We claim that (A) . We prove (A) for , the rest follows by induction. Since is a homomorphism and is an edge in , there is an edge in . The definition of edges in implies that . Similarly, let and . We claim that (B) . For , this again follows from the assumption that is a homomorphism and the definition of edges in ; a simple induction establishes (B) for arbitrary values .
Together, claims (A) and (B) imply that there are vertices and edges such that for all and we have . Since , we have . Hence forms a clique in . (End of proof of Claim 2.)
Claims 1 and 2 give us a complete description of identity homomorphisms from to : a mapping from to is an identity homomorphisms if and only if for some vertex set of a clique in . Hence, the number of such mappings is the number of cliques in multiplied by . By Lemma 5, each identity homomorphism can be extended in distinct ways to a homomorphism from to . ∎
We will frequently use the following simple observation.
Observation 7.
Let be a homomorphism from a bipartite graph to a graph . If vertices are of distance in then are of distance at most in and the parity of the distances is the same.
Next we establish an upper bound on the total weight of homomorphisms that are neither identity nor skew identity.
Lemma 8.
Let has vertices and edges, let for some , and let . If
then the total weight of homomorphisms that are neither identity nor skew identity is at most
The key ideas in the proof of Lemma 8 are the following: Firstly, we show that cc homomorphisms dominate noncc homomorphisms. Secondly, using crucially the special structure of fan grids and our choice of being a multiple of four, we establish an upper bound on any cc homomorphism that is neither identity nor skew identity. Finally, we give an upper bound on the number of all homomorphisms. These three ingredients together allows us to establish the required bound.
Proof.
We prove this lemma in two steps. First, in Claims 1 and 2, we upper bound the weight of a homomorphism that is not identity or skew identity. Second, in Claim 3, we upper bound the number of such homomorphisms.
Claim 1. The weight of any cc homomorphism is greater than the weight of any non cc homomorphism.
Proof of Claim 1: The weight of a cc homomorphism is lower bounded by , and the weight of any non cc homomorphism is upper bounded by . Take the logarithm base of the two numbers. We need to show that
or, equivalently,
which is equivalent to the condition
of the lemma. (End of proof of Claim 1.)
Claim 2. Let be a cc homomorphism that is neither identity nor skew identity. Then its weight does not exceed .
Proof of Claim 2: We consider several cases. First observe some symmetries in cc homomorphisms. If is the mapping of (the “grid” part of ) mapping to , then the weight of equals that of . Thus we may assume , which gives Case 1 and Case 2 below, respectively. Note that by the assumption that is a multiple of four, both and , where
, are odd.
Case 1. for some .
Since is at distance from , by Observation 7, is at odd distance not exceeding from . As is cc, there is only one possibility for some . Similarly, as is at odd distance from and is a corner vertex, by Observation 7 it suffices to consider only two cases for .
Case 1.1. for some .
Since is at distance from , by Observation 7, is at odd distance not exceeding from . As is cc and we assume that , there is only one possibility for some . This means that is identity, a contradiction.
Case 1.2. for some .
As in Case 1.1, for some . In detail, since is at distance from , by Observation 7, is at odd distance not exceeding from . As is cc and we assume that , there is only one possibility .
Since is the only shortest path from to , homomorphism maps this path to for some (in fact, we can claim that , but we do not need this). In particular, and ; that is, these two vertices are mapped to nonfan vertices. Since both and have at most neighbours, the weight of is at most .
Case 2. for some .
This case is symmetric to Case 1 so we do not give full details. Using Observation 7 and the assumption that is cc, we get for some . Also, we get that or for some . In the former case, as in Case 1.1 we get that necessarily is skew identity, which is a contradiction. In the latter case, similarly to Case 1.2, we get that for some . Since and are not fan vertices, as in Case 1.2, the weight of does not exceed . (End of proof of Claim 2.)
Claim 3. The number of homomorphisms of the grid to is upper bounded by
Proof of Claim 3: Since has no more than vertices and the grid has vertices, the claim follows. (End of proof of Claim 3.)
By Claims 1 and 2, the maximum weight of a homomorphism that is not identity or skew identity is . By Claim 3, there are at most
Comments
There are no comments yet.