Semantic Width and the Fixed-Parameter Tractability of Constraint Satisfaction Problems

1 Introduction

CSPs are a fundamental problem of artificial intelligence. As a unifying formal framework, they play a foundational role in many areas of AI research, see e.g., [Kumar, 1992; Narv´aez, 2018]. However, the unifying aspect of CSPs has not yet reached its full potential. While a CSP formulation of a problem allows for reuse of common algorithmic strategies and implementations [Gottlob et al., 2000; Do and Kambhampati, 2001], results in computational complexity still often require individual investigation, with little help from the framework. A complexity characterization for CSP would allow researchers to finally leverage the CSP framework also for strong computational complexity results, hence greatly simplifying the study of all problems that can be formulated as CSPs. The consequences and wide-reaching applications of such a characterization motivate our central research question. Note that throughout this paper, the parameterized complexity of CSPs always refers to the problem parameterized by the size of its constraint scopes.

Research Challenge: Is there a natural characterization of the fixed-parameter tractable classes of CSPs?

To be precise, we study what is referred to as the uniform CSP problem in the literature. In the uniform problem, we are interested in how the structure of constraint scopes affects the complexity of the problem, i.e., we characterize restrictions to the structure of constraint scopes. In the nonuniform problem, one considers restrictions to the constraint relations. Here, in a classic result, [Hell and Nesetril, 1990] gave an elegant characterization of PTIME solvability. More recently, [Bulatov, 2017] and [Zhuk, 2017] were able to independently establish a powerful dichotomy theorem. However, results for the nonuniform case do not translate to the uniform problem.

There is a long line of research devoted to the (parameterized) computational complexity of solving CSPs based on structural parameters of their associated hypergraphs. In a landmark result, [Grohe, 2007] resolved the question for a restricted class of CSPs; namely those with bounded arity. There, PTIME decidability is fully characterized by bounded treewidth modulo homomorphic equivalence. Moreover, for bounded arity, we have fixed-parameter tractability if and only if the problem is solvable in PTIME.

To tackle the problem beyond bounded arity, a number of generalizations of treewidth have been developed that provide sufficient conditions for tractably solving CSPs, the most important of which are hypertree width [Gottlob et al., 2002] and fractional hypertree width [Grohe and Marx, 2014]. Yet, bounding these parameters yields only sufficient conditions for tractability. A necessary condition for unbounded arity remains elusive. In the parameterized space, a highly impressive result by [Marx, 2013] was able to characterize those hypergraphs, i.e., problem structures, that always allow for fixed-parameter tractable evaluation by the submodular width of the hypergraphs. However, while this result is closely related to our goal, the fact that the characterization is on the hypergraph level significantly limits its applicability in our setting: When we consider the CSP formulation of a problem, then the complexity of our problem does not depend on the complexity of other, unrelated, CSPs that happen to have the same underlying hypergraphs. Hence, characterizing on the hypergraph level restricts us to a worst-case that may not be connected to the problem we want to study (this point is discussed in detail in Section 3.1).

Despite their unquestionable importance, Grohe's and Marx's characterizations do not answer our research question. Instead, we introduce a new parameter - semantic submodular width (sem-subw) - to capture the minimal submodular width over the (infinite) equivalence class of semantically equivalent CSPs. We show that it is still possible to decide sem-subw and find the minimal semantically equivalent CSP in time that depends only on the size of the parameter. Following that, we give a reduction from Marx's setting to ours, which allows us to prove the necessary lower bound. Akin to Marx's characterization, our result assumes the Exponential Time Hypothesis [Impagliazzo et al., 2001]; a standard assumption of parameterized complexity.

Main Result 1: Assuming the Exponential Time Hypothesis, a class of CSPs is fixed-parameter tractable if and only if it has bounded semantic submodular width.

Through the well-known equivalence of CSP to the homomorphism problem as well as conjunctive query containment [Kolaitis and Vardi, 2000] and evaluation [Maier, 1983], our main result also applies to those important problem families. By adapting our notion of sem-subw from CSPs to the more general notion of unions of conjunctive queries (UCQs) accordingly, we can also extend our characterization result to UCQs, an important and widely studied class of query languages in database theory [Sagiv and Yannakakis, 1980; Atserias et al., 2006].

Main Result 2: Assuming the Exponential Time Hypothesis, a class of UCQs is fixed-parameter tractable if and only if it has bounded semantic submodular width.

With the question of fixed-parameter tractability resolved, we shift our attention to PTIME solvable classes of CSPs. Here, a characterization of tractable restrictions for the uniform CSP problem remains an open question. We briefly discuss how our parameterized results relate to the nonparameterized case. Furthermore, we utilize some recent results on the connection of hypergraph width parameters and Vapnik-Chervonenkis dimension to derive new insight on the frontier of tractability of the uniform CSP problem. In particular, we show that the two most important sufficient conditions for tractable CSP solving - bounded fractional hypertree width and bounded hypertree width - actually collapses for classes of CSPs as long as they do not exhibit a certain kind of, seemingly unnatural, exponential growth.

The rest of the paper is structured as follows. Section 2 recalls necessary definitions for constraint satisfaction problems, unions of conjunctive queries, and relevant hypergraph width parameters. We expand on the differences to Marx's characterization in Section 3.1 before we present our two main results in Sections 3.2 and 3.3. Section 4 presents some new insights regarding the PTIME solvability of CSPs. We end with concluding remarks in Section 5.

Some preliminary results related to this paper were previously published in [Gottlob et al., 2019].

2 Preliminaries

2.1 Parameterized Complexity

Parameterized complexity enables a more fine-grained study of computational complexity. Here, we give an abridged definition of the notions necessary for this paper. For full definitions and details we refer to [Flum and Grohe, 2006].

For an alphabet of symbols Σ, a parameterized problem is given as a pair (P, κ) of a problem P ⊆ Σ∗ and its parameterization κ that maps each string in Σ∗ to a parameter.

We say that a parameterized problem (P, κ) is fixedparameter tractable if there exists an algorithm that decides whether a given string x ∈ Σ∗ is in P in time f(κ(x))poly(|x|), where f is a computable function and poly is a polynomial.

Let (P, κ) and (P ′ , κ′ ) be two parameterized problems. A fpt-reduction from (P, κ) to (P ′ , κ′ ) is a mapping R : Σ∗ → Σ∗ with the following properties:

1. x ∈ P ⇐⇒ R(x) ∈ P ′ for every x ∈ Σ∗ ,
2. R is computable in time f(κ(x))poly(|x|) (f is computable), and
3. there is a computable function g such that κ′ (x) ≤ g(κ(x)) for all x ∈ Σ∗ .

We say (P, κ) is fpt-reducible to (P ′ , κ′ ), denoted (P, κ) ≤ (P ′ , κ′ ). The class of fixed-parameter tractable problems is closed under fpt-reductions.

Our main results assume the Exponential Time Hypothesis, which states that 3-SAT with n variables can not be decided in 2o(n) time [Impagliazzo et al., 2001]. This is a standard assumption of parameterized complexity theory.

2.2 Constraint Satisfaction Problems

We formalize CSPs as a relational homomorphism problem. A signature is a finite set of relation symbols with associated arities. A (relational) structure A (over signature σ) consists of a domain A and an interpretation RA for each relation symbol R in the signature. Let A, B be relational structures, we call a function h : A → B a homomorphism from A into B, if for every relation symbol R and all (x1, . . . , xar(R)) ∈ RA also (h(x1), . . . , h(xar(R))) ∈ RB, where ar(R) is the arity of R. We write |A| = |σ| + |A| + ∑R∈σ |RA|ar(R) for the size of structure A.

We call an ordered pair (A,B) of structures a constraint satisfaction problem instance. Intuitively, A expresses the constraint scopes and B the permitted assignments for each constraint scope. For a class A of structures, the corresponding constraint satisfaction problem, denoted CSP(A), is the following decision problem.

CSP(A)

Instance: A CSP instance (A,B) where A ∈ A.

Question: Is there a homomorphism fromA into B?

By slight abuse of notation, we also call A a class of constraint satisfaction problems. Note that what we call CSP(A) is sometimes denoted as CSP(A, -) to emphasize that we are dealing with the uniform CSP problem (cf., [Grohe, 2007]). Furthermore, constants play no role in our considerations since they can be eliminated by straightforward preprocessing.

A hypergraph H is a tuple (V (H),E(H)), where V (H) is the set of vertices and E(H) ⊆ 2V (H) the set of hyperedges. For a set U ⊆ V (H), we define the subhypergraph induced by U as H[U] = (U, E′ ) where E′ = {e ∩ U | e ∈ E(H)} \ {∅}. The hypergraph H(A) of a structure A is the hypergraph where the vertices equal A and e ∈ E(H(A)) if and only if there exists some relation symbol R such that some permutation of e is contained in RA. The hypergraph of a CSP instance (A,B) is the hypergraph of A, i.e., the hypergraph of a CSP instance represents only the structure of its constraint scopes. We are interested in how this structure affects the complexity of the decision problem. We thus consider the CSP decision problem parameterized by its constraint scope structure:

p-CSP(A)

Instance: A CSP instance (A,B) where A ∈ A.

Parameter: |A|

Question:

Is there a homomorphism from A into B?

For a class H of hypergraphs, let Struct[H] denote all structures whose hypergraphs are in H. We will abbreviate the problem CSP(Struct[H]) to CSP(H), i.e., CSP restricted to those instances whose hypergraphs are in H. The analogue applies to p-CSP.

For two structures A and A′ , we say A is homomorphically equivalent to A′ , or A ≃ A′ , if there exists a homomorphism from A into A′ and vice versa. The core of a structure A, denoted core(A), is the minimal structure (with regards to the number of tuples) that is homomorphically equivalent to A. It is not hard to verify that every structure has a unique (up to isomorphism) core. For a class of structures A, we write core(A) for the class of cores of structures in A.

In the context of CSPs, we say a structure A is contained in structure A′ if for every B we have that if (A,B) has a solution, then (A′ ,B) also has a solution. It is easy to see that A is contained in A′ if and only if there exists a homomorphism from A′ to A. If two structures A and A′ are contained within each other, we say that they are semantically equivalent (we write A ≡ A′ ). Hence, if A ≡ A′ then for every B we have that (A,B) has a solution if and only if (A′ ,B) has a solution. Furthermore, note that A ≡ A′ if and only if A ≃ A′ , i.e., homomorphic equivalence equals semantic equivalence. In particular, (A,B) is always equivalent to (core(A),B).

2.3 Unions of Conjunctive Queries

Please note that, for consistency and brevity, we will define unions of conjunctive queries via CSPs. This does not match the standard presentations of the problem but is equivalent to them.

An instance of the (boolean) unions of conjunctive queries (UCQ) problem is a set of structures {A1, . . . ,An}, we write ⋃ni=1 Ai, and a structure B which is usually referred to as the database. We say an instance of the UCQ problem (⋃ni=1 Ai,B) has a solution if any of the CSP instances (Ai,B), for 1 ≤ i ≤ n, has a solution. Hence, the accompanying parameterized decision problem for a class of UCQs U is the following p-UCQ(U )

Instance: A UCQ U = ⋃ni=1 Ai where U ∈ U and a

Parameter: ∑ni=1 |Ai|

database B.

Question: Does U,B have a solution?

Analogue to CSPs, the equivalence of UCQs will be important. We say that two UCQs U = ⋃ni=1 Ai and U ′ = ⋃mi=1 A′i are semantically equivalent (we write U ≡ U ′ ) if for every structure B, (U,B) has a solution if and only if (U ′ , B) has a solution.

A UCQ ⋃ni=1 Ai is non-redundant if there are no Ai and Aj (i ̸= j) such that Ai is contained in Aj. Note that every UCQ can be transformed into an equivalent non-redundant UCQ by repeated deletion of structures that are contained by other structure in the UCQ [Sagiv and Yannakakis, 1980]). We write nr(U) for the UCQ obtained by applying this procedure to make an UCQ U non-redundant. Importantly, as the procedure only deletes structures we have nr(U) ⊆ U.

2.4 Decompositions and TheirWidths

In this work we will only consider width notions that are based on tree decompositions. A tuple (T, (Bu)u∈T ) is a tree decomposition of a hypergraph H if T is a tree, every Bu is a subset of V (H) and the following two conditions are satisfied:

1. For every e ∈ E(H) there is a node u ∈ T s.t. e ⊆ Bu, and
2. for every vertex v ∈ V (H), {u ∈ T | v ∈ Bu} is connected in T .

For functions f : 2V (H) → R+, the f-width of a tree decomposition is sup{f(Bu) | u ∈ T} and the f-width of a hypergraph is the minimal f-width over all its tree decompositions. Let F be a class of functions from subsets of V (H) to the non-negative reals, then the F-width of H is sup{f-width(H) | f ∈ F}. All such widths are implicitly extended to structures and CSP instances by taking the width of their respective hypergraphs.

The following properties of functions f : 2V (H) → R+ are important:

• f is monotone if X ⊆ Y implies f(X) ≤ f(Y ).
• f is called edge-dominated if f(e) ≤ 1 for every e ∈ E(H).
• f is called submodular if f(X) + f(Y ) ≥ f(X ∩ Y ) + f(X ∪ Y ) holds for every X, Y ⊆ V (H).

We say a weight function γ : E(H) → R+ is a fractional edge cover of a set X ⊆ V (H) if for every v ∈ X we have ∑e∈Iv γ(e) ≥ 1 where Iv is the set of all edges incident to v. If we restrict the co-domain to {0, 1}, we obtain the definition of an integral edge cover. We refer to the total weight ∑e∈E(H) γ(e) of an edge cover as the size of the edge cover.

For X ⊆ V (H), let ρH(X) be the size of the smallest integral edge cover of X by edges in E(H) and ρ∗H (X) the size of the smallest fractional edge cover of X by edges in E(H). This framework now allows us to define many of the important widths in the current literature.

(Primal) Treewidth of H [Robertson and Seymour, 1986]: tw(H) := c-width, where c(X) = |X| - 1.

Generalized hypertree width of H [Gottlob et al., 2002]: ghw(H) := ρH-width.

Fractional hypertree width of H [Grohe and Marx, 2014]: fhw(H) := ρ∗H -width.

Submodular width of H [Marx, 2013]:

subw(H) := F-width(H), where F is the set of all monotone, edge-dominated, submodular functions b on 2V (H) with b(∅) = 0.

A notable omission, that is not expressible through this notion of f-width, is hypertree width (hw) [Gottlob et al., 2002], which uses the same width function as ghw but imposes an additional restriction on the tree decomposition. Note that these widths spawn a hierarchy in the sense that the following inequality holds for all hypergraphs H:

For a class of structures A, we say A has bounded width if there exists a constant k such that every structure in A has width ≤ k. The computational complexity of CSP is tightly linked to this hierarchy of parameters. This connection is summarized by the following two propositions.

Proposition 1 ([Grohe and Marx, 2014]). Let C be a class of CSP instances of bounded fhw. Then CSP(C) is tractable.

Proposition 2 ([Marx, 2013]). Let H be a recursively enumerable class of hypergraphs. Assuming the Exponential Time Hypothesis, p-CSP(H) is fixed-parameter tractable if and only if H has bounded submodular width.

3 Main Results

3.1 Characterization of Hypergraph Classes vs. Classes of CSP Instances

Recall the motivation given in the introduction. Many AI problems have natural CSP formulations and we wish to determine the computational complexity of all such problems through a characterization of the complexity of CSP. In this section we argue why a characterization on the hypergraph level (which ignores relation symbols), as in Proposition 2, is not enough for this goal. The main issue with the hypergraph characterization is that even though a CSP instance may have a highly complex hypergraph structure, it can still be easy to solve. Yet, the complexity of p-CSP(H) expresses only the complexity of the worst-case CSP instances of the given structure. We illustrate this issue in the following example.

Consider the following problem: Given a directed graph G, can we embed (by a homomorphism) a bidirected n × n-grid into G? The corresponding CSP instance Cn(G) = (A,B) has a single relation symbol E and B = G. As domain of A we take {xi,j | i ∈ [n], j ∈ [n]} and EA contains exactly the following tuples specifying the n × n-grid: (xi,j, xi+1,j), (xi+1,j, xi,j) for i ∈ [n - 1], j ∈ [n] and (xi,j , xi,j+1), (xi,j+1, xi,j) for i ∈ [n], j ∈ [n - 1].

We now consider the class C of all CSP instances Cn(G) for n ≥ 1 and all graphs G. The hypergraphs of C are, by definition, exactly the class of n × n-grid graphs Gn×n, which is well-known to have unbounded treewidth [Robertson and Seymour, 1986]. In general, it is difficult to determine the submodular width of graphs since the definition depends on a supremum over an infinite class of functions. However, Lemma 1 below provides us with a convenient way to recognize that certain classes have unbounded submodular width.

Lemma 1. Let H be an arbitrary hypergraph and let rank(H) be the maximum edge size in H, then

Sketch. Let f : X ↦→ |X|/rank(H) be a function on the subsets of V (H). It is easy to verify that f is submodular, edgedominated and monotone. For any node u of any tree decomposition of H we clearly have |Bu| = rank(H) · f(Bu) and therefore also tw(H) + 1 = rank(H) · f -width(H). Since f is submodular, edge-dominated and monotone we also have f-width(H) ≤ subw(H) and the statement follows immediately.

From Lemma 1 we can conclude that Gn×n also has unbounded submodular width. From Proposition 2 we can thus only deduce that p-CSP(Gn×n) is not fixed-parameter tractable.

However, for every Cn(G) = (A,B), we have that core(A) is the structure with domain {x1, x2} and Ecore(A) = {(x1, x2), (x2, x1)}. This is easy to verify, e.g., by observing that an undirected n × n-grid is 2-colorable. Clearly, (core(A),B) is solvable in polynomial time and it is equivalent to (A,B). It follows that p-CSP(C) is in fact fixed-parameter tractable (and indeed tractable), despite the complexity of p-CSP(Gn×n). We see that a hypergraph level characterization has inherent shortcomings in establishing lower bounds for specific problem classes.

3.2 Constraint Satisfaction Problems

In this section we prove our characterization theorem for CSPs. The discussion in Section 3.1 shows that unbounded submodular width can still allow for fixed-parameter tractable CSP solving. Hence, we require a new, more general, property to fully capture fixed-parameter tractability. We follow [Barcel´o et al., 2017] who introduced the notion of semantic (generalized) hypertree width and define the following general notion of semantic widths of CSPs.

Definition 1. Let A be the class of all structures and w : A → R+ be an isomorphism invariant. We define semantic w as sem-w(A) := inf{w(A′ ) | A′ ≡ A}.

Using this definition, we are now ready to state our first main result. We show that the characterization from Proposition 2 can indeed be strengthened to the following characterization of the fixed-parameter tractability of CSP instances.

Theorem 1. Let A be a recursively enumerable class of CSPs. Assuming the Exponential Time Hypothesis, p-CSP(A) is fixed-parameter tractable if and only if A has bounded semantic submodular width.

Our proof of the theorem relies on two central lemmas. First, we show how bounded semantic submodular width leads to fixed-parameter tractability. The basic idea is simple, instead of solving a CSP instance with possibly arbitrarily high submodular width, we want to solve an equivalent instance with low width. However, it is not clear how to find such an equivalent instance and whether finding it is decidable. For generalized hypertree width [Barcel´o et al., 2017] have recently shown, that for any structure A, sem-ghw(A) is precisely ghw(core(A)). Indeed, we show in Lemma 2, that the same connection also holds for the more complex cases of fractional hypertree width and submodular width. Note that for treewidth this property is trivial since treewidth is hereditary, i.e., removing edges from a hypergraph can not increase its treewidth. The width functions considered here are not hereditary and involve additional technical considerations beyond those necessary for the ghw case.

Lemma 2. For every structure A:

1. sem-ρ∗ (A) = ρ∗ (core(A))
2. sem-fhw(A) = fhw(core(A))
3. sem-subw(A) = subw(core(A))

Proof (Sketch). First, since call equivalent structures have isomorphic cores it is enough to show w(core(A)) ≤ w(A) to establish that sem-w(A) = w(core(A)) for any invariant w.

Let H be the hypergraph of A and H′ the hypergraph of core(A). Note that there exists an homomorphism h fromA to core(A) where h(a) = a for all elements in the domain of core(A). From this we can then show that for every tree decomposition (T, (Bu)u∈T ) of H, there exists a tree decomposition (T, (B′u )u∈T ) of H′ where B′u = Bu ∩ V (H′ ).

For the fhw case we then use an observation on how fractional edge covers behave under homomorphisms to show that this transformation does not increase the ρ∗ -width. Hence, we can transform the tree decomposition for H with minimal ρ∗ -width into a new tree decomposition for H′ with less or equal ρ∗ -width, i.e., fhw(H′ ) ≤ fhw(H). The observation for edge covers under homomorphisms also leads to the result for sem-ρ∗ .

The subw case requires additional considerations as the width is now defined over a whole class of functions F. We show that for every edge-dominated, submodular function f ′ over H′ there exists an edge-dominated submodular function f over H such that f ′ -width(H′ ) ≤ f-width(H). In particular, for every f ′ this the function f : X ↦→ f ′ (X ∩ V (H′ )) has the required properties.

While sem-ρ∗ and sem-fhw are less general than sem-subw they will be of further interest in the discussion of PTIME solvability of CSPs in Section 4. In the context of our main result, the most important consequence of Lemma 2 is that we are always able to find the equivalent structure with minimal submodular width by simply computing the core. In principle, finding the core of a structure is intractable (formally, deciding if a structure A′ is the core of a structure A, is DPcomplete [Fagin et al., 2005]). However, in our parameterized setting the computation of the core of A only depends on the parameter.

To establish a lower bound for classes with unbounded semantic submodular width we will make use of previous results from [Chen and M¨uller, 2015]. A step in our reduction will require an additional definition that helps us fix the domains of individual elements in the reduction. For a structure A, let A∗ be the expansion of A by a new fresh unary relation symbol Ua with U A a = {a} for every element of the domain a ∈ A. For a class of structures A we write A∗ for {A∗ | A ∈ A}. Our intention is to establish our lower bound by reduction from the hypergraph setting of Proposition 2. We will make use of the following two reductions.

Proposition 3 ([Chen and M¨uller, 2015]). Let A be a recursively enumerable class of structures. Then

Lemma 3. Let A be a recursively enumerable class of structures and let HA be the class of hypergraphs of A.

Proof. Let (C,D) be an instance of CSP(HA) and let H be the hypergraph of C and D be the domain of D. Recall that edges can represent multiple constraint scopes, i.e., multiple tuples in C. For each edge e ∈ E(H), we consider the sets Ft1 , . . . , Ftk of satisfying assignments e → D for each of the tuples t1, . . . , tk of C that become edge e in the hypergraph. We then produce the set Fe = ⋂ki=1 Fti of satisfying assignments over all the tuples for e. Observe that computing Fe for all e ∈ E(H) is possible in polynomial time.

By definition there exists a structure A∗ in A∗ where A has hypergraph H. We can compute such a A∗ by enumeration of A until we find an A with a matching hypergraph and then computing A∗ fromA.

We will reduce (C, D) to (A∗ , B) where B is constructed as follows. As the domain of B we take A × D. For each a ∈ A we have a U A a with U A a = {a}. Let U B a = {(a, d) | d ∈ D}. For each other relation symbol R of A and each tuple (a1, . . . , ak) ∈ RA, we add tuples ((a1, f(a1)), . . . , (ak, f(ak))) to RB where f ∈ Fe and e is the hyperedge {a1, . . . , ak}.

We now show that (C,D) has a solution iff (A∗ ,B) has a solution. First, suppose h is a homomorphism from C to D and note that A∗ and C have the same domain since A and C have the same underlying hypergraph. It is then not difficult to see that g : a ↦→ (a, h(a)) is a homomorphism from A∗ to B: For the unary relations U A a , the image trivially exists in U B a . For the other relations, it is enough to observe hat for every edge e of H, the assignment h restricted to variables in e must be in Fe.

For the other side, observe that a homomorphism g from A∗ to B must be of the form a ↦→ (a, h(a)). We argue that h is a homomorphism from C to D. As A and C have the same domain, h also applies to the domain of C. By definition of Fe we have that for every tuple ¯x in RC, h maps to a tuple in RD as long as ¯x is covered by some edge of A. Since the hypergraphs are the same, this holds for all the tuples in C and therefore h is a homomorphism.

Proof of Theorem 1. Let Hcore(A) be the class of hypergraphs of the structures in core(A). We claim that the two problems p-CSP(A) and p-CSP(Hcore(A) ) are fpt-reducible to each other. If the claim holds, p-CSP(A) is fixedparameter tractable iff p-CSP(Hcore(A) ) is fixed-parameter tractable. By Proposition 2 this is the case iff Hcore(A) has bounded submodular width. By Lemma 2, this is equivalent to A having bounded semantic submodular width.

What is left, is to show the claim. First, we observe:

The left reduction holds because (A,B) is equivalent to (core(A),B) and computing the core is feasible in f(|A|) time. The right reduction is trivial since all instances of p-CSP(core(A)) are also instances of p-CSP(Hcore(A) ). For the other direction we get the intended reduction by straightforward combination of Lemma 3 and Proposition 3:

3.3 Unions of Conjunctive Queries

We now extend the characterization in Theorem 1 from CSPs to UCQs. To do so we first need to introduce a way to extend the relevant definitions to UCQs. For our width notions the natural extension to UCQs is through the maximum of its parts, i.e., for width function w and UCQ U = ⋃ni=1 Ai let w(U) := max{w(Ai) | i ∈ [n]}. Semantic width functions are defined the same as for CSPs, i.e., sem-w := inf{w(U ′ ) | U ′ ≡ U}. However, equivalence of UCQs is more complex than equivalence in CSPs. In particular, the characterization by homomorphic equivalence is no longer applicable. Therefore, some additional effort is required to determine the analogue of Lemma 2. Using the following classic result by Sagiv and Yannakakis we can derive the fitting Lemma 4.

Proposition 4 ([Sagiv and Yannakakis, 1980]). Let U = ⋃ni=1 Ai and U ′ = ⋃mj=1 A′j be non-redundant UCQs. Then U ≡ U ′ if and only if for every Ai there is a unique A′j such that Ai ≡ A′j .

Lemma 4. Let U be an UCQ, then

Proof. It is clear that the right side of the equality is the subw of an UCQ that is equivalent to U. All that is to show is that this is in fact the minimal subw of an equivalent UCQ. For the sake of brevity we will write core-subw(nr(U)) for max{subw(core(Ai)) | Ai ∈ nr(U)} in the rest of the argument.

Proof is by contradiction. Suppose there exist a UCQ V ≡ U with subw(V ) < core-subw(nr(U)). Since V ≡ U, clearly also nr(V ) ≡ nr(U). Furthermore, since nr(V ) ⊆ V (recall the construction of nr(V )) we also have subw(nr(V )) < core-subw(nr(U). Now, from Proposition 4 we have that for every Bi ∈ nr(V ), there is an equivalent Aj ∈ nr(U). By Lemma 2 it follows that subw(Bi) ≥ sem-subw(Bi) = sem-subw(Aj) = subw(core(Aj)) for all such combinations of Bi and Aj. From the definition of subw for UCQs this then gives an immediate contradiction of subw(nr(V )) < core-subw(nr(U)).

From Lemma 4 it is now easy to see, that for a class of UCQs U with bounded sem-subw, the p-UCQ(U) problem is fixed-parameter tractable. For every U in U we can simply compute nr(U) = ⋃ni=1 Ai and then solve the CSPs

(core(Ai),B) individually. In combination with Theorem 1 we see that this procedure is fixed-parameter tractable.

To establish the lower bound, we make use of previous work on the complexity of existential positive logic [Chen, 2014]. The result there is stated in a different setting but a translation is not difficult through the well-known equivalence of solving CSPs and model checking of primitive positive first-order formulas.

Proposition 5 (Theorem 3.2 in [Chen, 2014]). Let U be recursively enumerable class of non-redundant UCQs and let A be the class of all individual structures that make up the UCQs in U. Then p-CSP(A) ≤ p-UCQ(U).

Theorem 2. Let U be a recursively enumerable class of UCQs. Assuming the Exponential Time Hypothesis, p-UCQ(U) is fixed-parameter tractable if and only if U has bounded semantic submodular width.

Proof. For the case where U has bounded semantic submodular width we have already given a fixed-parameter tractable procedure for solving p-UCQ(U) above. We will establish the lower bound by introducing the class nr(U) = {nr(U) | U ∈ U} as an intermediate.

Suppose U has unbounded sem-subw and let A be the class of all individual structures that make up the UCQs in nr(U). From Lemma 4 it follows that nr(U) and A both also have unbounded sem-subw. By Proposition 5 we have p-CSP(A) ≤ p-UCQ(nr(U)) and therefore, by Theorem 1, p-UCQ(nr(U)) can not be fixed-parameter tractable.

To finish the proof we show that p-UCQ(nr(U)) ≤ p-UCQ(U). The reduction is straightforward, an instance (U,B) of p-UCQ(nr(U)) is reduced to the instance (U ′ ,B) of p-UCQ(U) where nr(U ′ ) ≡ U. Such an U ′ can be found by enumeration of U in time that only depends on the parameter. Since nr(U ′ ) ≡ U, the reduction is trivially correct.

4 On the Plain Tractability of CSPs

A characterization for the plain (non-parameterized) tractability of CSPs remains an open question. Here we wish to highlight two consequences of our work and recent developments regarding the connection of fractional hypertree width and the Vapnik-Chervonenkis (VC) dimension of a hypergraph presented in [Gottlob et al., 2020].

Tractability in natural problem classes. Bounded hypertree width (hw), generalized hypertree width (ghw) and fractional hypertree width (fhw) all represent sufficient conditions for tractable CSP solving, with fhw being the most general such property we know of. It is known that hw is bounded if and only if ghw is bounded [Adler et al., 2007]. Furthermore, there exist classes that exhibit bounded fhw but unbounded hw [Grohe and Marx, 2014]. However, all known hypergraph classes with bounded fhw and unbounded hw involve some form of exponential growth that is unlikely to be present in natural problems. It has remained an open question if this exponential growth is essential for the separation of the two width measures.

Below, we give an answer to this question. The technical details of VC dimension are not important here. Rather we introduce the notion of exotic hypergraph classes, a consequence of unbounded VC dimension, to focus on the exponential character of such classes. We are able to state that this property is indeed intrinsic to the separation of bounded fhw and hw. Alternatively, in the contrapositive, we see that for non-exotic classes, a class has bounded fhw if and only if it has bounded hw. In other words, bounded fhw does not allow for additional tractable cases over bounded hw.

Definition 2. Let H be a class of hypergraphs. We say that H is exotic if for every integer n ≥ 1, there exists a H ∈ H with a set of n vertices U ⊆ V (H) such that H[U] has at least 2n - 1 distinct edges.

Theorem 3. For any class H of hypergraphs, if H has unbounded hypertree width and bounded fractional hypertree width then H is exotic.

Proof (Sketch). As stated above, exoticness is a consequence of unbounded VC dimension, thus we also have that if H is not exotic, then H has bounded VC dimension.

The key observation is then that the integrality gap for fractional edge covers can be bounded by a function of the VC dimension. Hence, under bounded VC dimension the integrality gap is constant. By applying this observation to every bag of a tree decomposition with fhw ≤ k we can see that the tree decomposition will also have ghw bounded by some function of k and the VC dimension. Due to space restrictions we refer to the proof Theorem 7.8 in [Gottlob et al., 2020] for details.

In summary, if H has bounded VC dimension, then H has bounded fhw iff H has bounded ghw. Recall from above, that also ghw(H) is bounded iff hw(H) is bounded. Hence, the contrapositive of the implication in the theorem holds.

We can extend the exotic property from hypergraphs to classes of CSPs in the usual way. Recall, that in the context of CSPs, incident edges in the hypergraph correspond to constraints that involve the variable. Hence, if vertices U have 2|U| -1 distinct incident edges in the hypergraph, there exists at least one constraint for every possible combination of the corresponding variables in the CSP. We argue that this situation is highly unnatural and believe that this motivates further study of the complexity of non-exotic classes of CSP.

Semantic width and tractability. In the parameterized setting, it is easy to utilize low semantic width to establish upperbounds as computing the core requires time only in the parameter. For tractability the situation is more problematic. As noted in Section 3.2, finding the core is intractable. Hence, if we have a class with bounded semantic fractional hypertree width, we know that the problem itself is not difficult, but an efficient solution depends on the hard problem of finding the core. We are caught in an unsatisfactory situation where the origin of the hardness is no longer the actual problem but the concrete formulation.

Part of the issue is that utilizing bounded fhw for polynomial evaluation requires a concrete decomposition with low fhw, which then guides the efficient solution of the CSP. Without knowing the core we cannot compute the appropriate decomposition. For bounded generalized hypertree width, Chen and Dalmau were able to show, that for classes of bounded ghw, there exists an algorithm for solving CSPs in polynomial time without requiring the explicit computation of a decomposition [Chen and Dalmau, 2005]. Their method indeed remains polynomial if only the semantic generalized hypertree width is bounded. Thus, we are able to lift their result to bounded semantic fractional hypertree width for nonexotic classes.

Corollary 1. Let C be a non-exotic class of CSPs with bounded semantic fractional hypertree width. Then CSP(C) is tractable.

Any more general sufficient property for tractability would likely have to preserve this feature of making use of the width of the core without actually requiring the computation of the core. Hence, in light of Theorem 3 and Corollary 1 we conclude the section with the following conjecture.

Conjecture 1. Let C be a class of non-exotic CSPs. Then CSP(C) is tractable if and only if C has bounded semantic hypertree width.

5 Conclusion &Outlook

We have given characterizations of the fixed-parameter tractable classes of CSPs and UCQs. This allows us to determine the parameterized complexity of problems that have CSP or UCQ formulations by determining if the class of these formulations has bounded sem-subw. This motivates further work on theoretical tools that help to show whether a class has bounded sem-subw. We believe that further study of adaptive width [Marx, 2011], which is bounded iff subw is bounded, can be a productive avenue of research here.

The characterization of polynomial time solvable CSPs remains open. We have motivated a new class of non-exotic problems that merits further research. In particular, we wish to resolve Conjecture 1, which we believe to be an important step towards the general problem.

Recent work has proposed the use of hybrid width parameters for the study of the computational complexity of CSP, e.g., [Ganian et al., 2019]. Such hybrid width parameters, which consider both the query structure and database content, are a natural avenue for further research.

Moreover, we are intrigued by the connections to VC dimension, which is an important parameter in learnability theory [Blumer et al., 1989]. We plan to further investigate the nature of the relationship between decomposition methods and learnability theory.

Acknowledgments

This work was supported by the Austrian Science Fund (FWF):P30930. Georg Gottlob is a Royal Society Research Professor and acknowledges support by the Royal Society for the present work in the context of the project "RAISON DATA" (Project reference: RP\R1\201074)