# «A Tractable hypergraph properties for constraint satisfaction and conjunctive queries1 D´niel Marx, Computer and Automation Research Institute, ...»

A

Tractable hypergraph properties for constraint satisfaction and

conjunctive queries1

D´niel Marx, Computer and Automation Research Institute, Hungarian Academy of Sciences (MTA

a

SZTAKI), Budapest, Hungary, dmarx@cs.bme.hu. 2

An important question in the study of constraint satisfaction problems (CSP) is understanding how the

graph or hypergraph describing the incidence structure of the constraints inﬂuences the complexity of the

problem. For binary CSP instances (i.e., where each constraint involves only two variables), the situation is well understood: the complexity of the problem essentially depends on the treewidth of the graph of the constraints [Grohe 2007; Marx 2010b]. However, this is not the correct answer if constraints with unbounded number of variables are allowed, and in particular, for CSP instances arising from query evaluation problems in database theory. Formally, if H is a class of hypergraphs, then let CSP(H) be CSP restricted to instances whose hypergraph is in H. Our goal is to characterize those classes of hypergraphs for which CSP(H) is polynomial-time solvable or ﬁxed-parameter tractable, parameterized by the number of variables. Note that in the applications related to database query evaluation, we usually assume that the number of variables is much smaller than the size of the instance, thus parameterization by the number of variables is a meaningful question.

The most general known property of H that makes CSP(H) polynomial-time solvable is bounded fractional hypertree width. Here we introduce a new hypergraph measure called submodular width, and show that bounded submodular width of H (which is a strictly more general property than bounded fractional hypertree width) implies that CSP(H) is ﬁxed-parameter tractable. In a matching hardness result, we show that if H has unbounded submodular width, then CSP(H) is not ﬁxed-parameter tractable (and hence not polynomial-time solvable), unless the Exponential Time Hypothesis (ETH) fails. The algorithmic result uses tree decompositions in a novel way: instead of using a single decomposition depending on the hypergraph, the instance is split into a set of instances (all on the same set of variables as the original instance), and then the new instances are solved by choosing a diﬀerent tree decomposition for each of them. The reason why this strategy works is that the splitting can be done in such a way that the new instances are “uniform” with respect to the number extensions of partial solutions, and therefore the number of partial solutions can be described by a submodular function. For the hardness result, we prove via a series of combinatorial results that if a hypergraph H has large submodular width, then a 3SAT instance can be eﬃciently simulated by a CSP instance whose hypergraph is H. To provethese combinatorial results, we need to develop a theory of (multicommodity) ﬂows on hypergraphs and vertex separators in the case when the function b(S) deﬁning the cost of separator S is submodular, which can be of independent interest.

Categories and Subject Descriptors: F.2 [Theory of Computing]: Analysis of Algorithms and Problem Complexity; G.2.2 [Mathematics of Computing]: Discrete Mathematics—Graph Theory General Terms: Algorithms Additional Key Words and Phrases: constraint satisfaction, hypergraphs, hypertree width, fractional edge covers

1. INTRODUCTION There is a long line of research devoted to identifying hypergraph properties that make the evaluation of conjunctive queries tractable (see e.g. [Gottlob et al. 2002a; Scarcello et al. 2008; Grohe 2006; 2007]). Our main contribution is giving a complete theoretical answer to this question: in a very precise technical sense, we characterize those hypergraph properties that imply tractability for the evaluation of a query. Eﬃcient evaluation of queries is originally a question of database theory; however, it has been noted that the problem can be treated as a constraint satisfaction problem (CSP) and this connection led to a fruitful

interaction between the two communities [Kolaitis and Vardi 2000a; Gottlob and Szeider 2008; Scarcello et al. 2008]. Most of the literature relevant to the current paper use the language of constraint satisfaction. Therefore, after a brief explanation of the databasetheoretic motivation, we switch to the language of CSPs.

Conjunctive queries. Evaluation of conjunctive queries (or equivalently, Select-ProjectJoin queries) is one of the most basic and most studied tasks in relational databases.

A relational database consists of a ﬁxed set of relations. A conjunctive query deﬁnes a new relation that can be obtained as ﬁrst taking the join of some relations and then projecting it to a subset of the variables. As an example, consider a relational database that contains three relations: enrolled(Person, Course, Date), teaches(Person, Course, Year), parent(Person1, Person2). The following query Q deﬁnes a unary relation ans(P ) with the meaning that “P is enrolled in a course taught by her parent.” Q : ans(P ) ← enrolled(P, C, D) ∧ teaches(P 2, C, Y ) ∧ parent(P 2, P ).

In the Boolean Conjunctive Query problem, the task is only to decide if the answer relation is empty or not, that is, if the join of the relations is empty or not. This is usually denoted as the relation “ans” not having any variables. Boolean Conjunctive Query contains most of the combinatorial diﬃculty of the general problem without complications such that the size of the output being exponentially large. Therefore, the current paper focuses on this decision problem.

In a natural way, we can deﬁne the hypergraph of a query: its vertices are the variables appearing in the query and for each relation there is a corresponding hyperedge containing the variables appearing in the relation. Intuitively, if the hypergraph has “simple structure,”

**then the query is easy to solve. For example, compare the following two queries:**

Q1 : ans ← R1 (A, B, C) ∧ R2 (C, D) ∧ R3 (D, E, F ) ∧ R4 (E, F, G, H) ∧ R5 (H, I) Q2 : ans ← R1 (A, B) ∧ R2 (A, C) ∧ R3 (A, D) ∧ R4 (B, C) ∧ R5 (B, D) ∧ R6 (C, D) Even though more variables appear in Q1, evaluating it seems to be easier: its hypergraph is “path like,” thus the query can be answered eﬃciently by, say, dynamic programming techniques. On the other hand, the hypergraph of Q2 is a clique on 4 vertices and no signiﬁcant shortcut is apparent compared to trying all possible combinations of values for (A, B, C, D).

What are those hypergraph properties that make Boolean Conjunctive Query tractable?

In the early 80s, it has been noted that acyclicity is one such property [Beeri et al. 1983;

Fagin 1983; Yannakakis 1981; Beeri et al. 1981]. Later, more general such properties were identiﬁed in the literature: for example, bounded query width [Chekuri and Rajaraman 2000], bounded hypertree width [Gottlob et al. 2002a], and bounded fractional hypertree width [Marx 2010a; Grohe and Marx 2012]. Our goal is to ﬁnd the most general hypergraph property that guarantees an eﬃcient solution for query evaluation.

Constraint satisfaction. Constraint satisfaction is a general framework that includes many standard algorithmic problems such as satisﬁability, graph coloring, database queries, etc. [Grohe 2006; Feder and Vardi 1999]. A constraint satisfaction problem (CSP) consists of a set V of variables, a domain D, and a set C of constraints, where each constraint is a relation on a subset of the variables. The task is to assign a value from D to each variable in such a way that every constraint is satisﬁed (see Deﬁnition 2.1 in Section 2 for the formal deﬁnition). For example, 3SAT can be interpreted as a CSP problem where the domain is D = {0, 1} and the constraints in C correspond to the clauses (thus the arity of each constraint is 3). As another example, let us observe that the k-Clique problem (Is there a kclique in a given graph G?) can be easily expressed as a CSP instance the following way. Let D be the set of vertices of G, let V contain k variables, and let C contain k constraints, one constraint on each pair of variables. The binary relation of these constraints require Journal of the ACM, Vol. V, No. N, Article A, Publication date: January YYYY.

**Tractable hypergraph properties for constraint satisfaction and conjunctive queries A:3**

that the two vertices are distinct and adjacent. Therefore, the CSP instance has a solution if and only if G has a k-clique.

It is easy to see that Boolean Conjunctive Query can be formulated as the problem of deciding if a CSP instance has a solution: the variables of the CSP instance correspond to the variables appearing in the query and the constraints correspond to the database relations.

A distinctive feature of CSP instances obtained this way is that the number of variables is small (as queries are typically small), while the domain of the variables are large (as the database relations usually contain a large number of entries). This has to be contrasted with typical CSP problems from AI, such as 3-colorability and satisﬁability, where the domain is small, but the number of variables is large. As our motivation is database-theoretic, in the rest of the paper the reader should keep in mind that we are envisioning scenarios where the number of variables is small and the domain is large.

As the examples above show, solving constraint satisfaction problems is NP-hard in general if there are no additional restrictions on the input instances. The main goal of the research on CSP is to identify tractable special cases of the general problem. The theoretical literature on CSP investigates two main types of restrictions. The ﬁrst type is to restrict the constraint language, that is, the type of constraints that are allowed. This direction includes the classical work of Schaefer [1978] and its many generalizations [Bulatov 2006;

2003; Bulatov et al. 2001; Feder and Vardi 1999; Jeavons et al. 1997]. The second type is to restrict the structure induced by the constraints on the variables. The hypergraph of a CSP instance is deﬁned to be a hypergraph on the variables of the instance such that for each constraint c ∈ C there is a hyperedge ec containing exactly the variables that appear in c. If the hypergraph of the CSP instance has very simple structure, then the instance is easy to solve. For example, it is well-known that a CSP instance I with hypergraph H can be solved in time I O(tw(H)) [Freuder 1990], where tw(H) denotes the treewidth of H and I is the size of the representation of I in the input.

Our goal is to characterize the “easy” and “hard” hypergraphs from the viewpoint of constraint satisfaction. However, formally speaking, CSP is polynomial-time solvable for every ﬁxed hypergraph H: since H has a constant number k of vertices, every CSP instance with hypergraph H can be solved by trying all I k possible combinations on the k variables. It makes more sense to characterize those classes of hypergraphs where CSP is easy. Formally, for a class H of hypergraphs, let CSP(H) be the restriction of CSP where the hypergraph of the instance is assumed to be in H. For example, as discussed above, we know that if H is a class of hypergraphs with bounded treewidth (i.e., there is a constant w such that tw(H) ≤ w for every H ∈ H), then CSP(H) is polynomial-time solvable.

For the characterization of the complexity of CSP(H), we can investigate two notions of tractability. CSP(H) is polynomial-time solvable if there is an algorithm solving every instance of CSP(H) in time ( I )O(1), where I is the length of the representation of I in the input. The following notion interprets tractability in a less restrictive way: CSP(H) is ﬁxed-parameter tractable (FPT) if there is an algorithm solving every instance I of CSP(H) in time f (H)( I )O(1), where f is an arbitrary computable function of the hypergraph H of the instance. Equivalently, the factor f (H) in the deﬁnition can be replaced by a factor f (k) depending only on the number k of vertices of H: as the number of hypergraphs on k vertices (without parallel edges) is bounded by a function of k, the two deﬁnitions result in the same notion. The motivation behind this deﬁnition is that if the number of variables is assumed to be much smaller than the the domain size, then we can aﬀord even exponential dependence on the number of variables, as long as the dependence on the size of the instance is polynomial. For a more background on ﬁxed-parameter tractability, the reader is referred to the parameterized complexity literature [Downey and Fellows 1999; Flum and Grohe 2006; Niedermeier 2006].

Journal of the ACM, Vol. V, No. N, Article A, Publication date: January YYYY.

A:4 D. Marx The case of bounded arities. If the constraints have bounded arity (i.e., the edge size in H is bounded by a constant r), then the complexity of CSP(H) is well understood. In

**this case, bounded treewidth is the only polynomial-time solvable case:**

** Theorem 1.1 (Grohe [2007]).**

If H is a recursively enumerable class of hypergraphs

**with bounded edge size, then (assuming FPT = W[1]) the following are equivalent:**

(1 ) CSP(H) is polynomial-time solvable.

(2 ) CSP(H) is ﬁxed-parameter tractable.

(3 ) H has bounded treewidth.

The assumption FPT = W[1] is a standard hypothesis of parameterized complexity. Thus in the bounded arity case bounded treewidth is the only property of the hypergraph that can make the problem polynomial-time solvable. By deﬁnition, polynomial-time solvability implies ﬁxed-parameter tractability, but Theorem 1.1 proves the surprising result that whenever CSP(H) is ﬁxed-parameter tractable, it is polynomial-time solvable as well.

The following sharpening of Theorem 1.1 shows that there is no algorithm whose running time is signiﬁcantly better than the I O(tw(H)) bound of the treewidth based algorithm, and this is true if we restrict the problem to any class H of hypergraphs. The result is proved under the Exponential Time Hypothesis (ETH) [Impagliazzo et al. 2001] stating that there is no 2o(n) time algorithm for n-variable 3SAT, which is a somewhat stronger assumption than FPT = W[1].

** Theorem 1.2 (Marx [2010b]).**