«A Tractable hypergraph properties for constraint satisfaction and conjunctive queries1 D´niel Marx, Computer and Automation Research Institute, ...»
If there is a compuable function f and a recursively enumerable class H of hypergraphs with bounded edge size and unbounded treewidth such that the problem CSP(H) can be solved in time f (H) I o(tw(H)/ log tw(H)) for instances I with hypergraph H ∈ H, then ETH fails.
This means that the treewidth-based algorithm is almost optimal on every class of hypergraphs: in the exponent only an O(log tw(H)) factor improvement is possible. It is conjectured in [Marx 2010b] that Theorem 1.2 can be made tight, i.e., the lower bound holds even if the logarithmic factor is removed from the exponent.
Conjecture 1.3 (Marx [2010b]). If H is a class of hypergraphs with bounded edge size, then there is no algorithm that solves CSP(H) in time f (H) I o(tw(H)) for instances I with hypergraph H ∈ H, where f is an arbitrary function.
Unbounded arities. The situation is less understood in the unbounded arity case, i.e., when there is no bound on the maximum edge size in H. First, the complexity in the unbounded-arity case depends on how the constraints are represented. In the bounded-arity case, if each constraint contains at most r variables (r being a ﬁxed constant), then every reasonable representation of a constraint has size |D|O(r). Therefore, the size of the diﬀerent representations can diﬀer only by a polynomial factor. On the other hand, if there is no bound on the arity, then there can be exponential diﬀerence between the size of succinct representations (e.g., formulas [Chen and Grohe 2010]) and verbose representations (e.g., truth tables [Marx 2011]). The running time of an algorithm is expressed as a function of the input size, hence the complexity of the problem can depend on how the input is represented: longer representation means that it is potentially easier to obtain a polynomialtime algorithm.
The most well-studied representation of constraints is listing all the tuples that satisfy the constraint. This representation is perfectly compatible with our database-theoretic motivation: the constraints are relations of the database, and a relation is physically stored as a table containing all the tuples in the relation. For this representation, there are classes H with unbounded treewidth such that CSP restricted to this class is polynomial-time solvable. A trivial example is the class H of all hypergraphs having only a single hyperedge of Journal of the ACM, Vol. V, No. N, Article A, Publication date: January YYYY.
Tractable hypergraph properties for constraint satisfaction and conjunctive queries A:5
arbitrary size. The treewidth of such hypergraphs can be arbitrarily large (as the treewidth of a hypergraph consisting of a single edge e is exactly |e| − 1), but CSP(H) is trivial to solve: we can pick any tuple from the constraint corresponding to the single edge. There are other, nontrivial, classes of hypergraphs with unbounded treewidth such that CSP(H) is solvable in polynomial time: for example, classes with bounded (generalized) hypertree width [Gottlob et al. 2002b], bounded fractional edge cover number [Grohe and Marx 2012], and bounded fractional hypertree width [Grohe and Marx 2012; Marx 2010a]. Thus, unlike in the bounded-arity case, treewidth is not the right measure for characterizing the complexity of the problem.
Our results. We introduce a new hypergraph width measure that we call submodular width. Small submodular width means that for every monotone submodular function b on the vertices of the hypergraph H, there is a tree decomposition where b(B) is small for every bag B of the decomposition. (This deﬁnition makes sense only if we normalize the considered functions: for this reason, we require that b(e) ≤ 1 for every edge e of H.) The main result of the paper is showing that bounded submodular width is the property that
precisely characterizes the complexity of CSP(H):
Theorem 1.4 (Main).
Let H be a recursively enumerable class of hypergraphs. Assuming the Exponential Time Hypothesis, CSP(H) parameterized by H is ﬁxed-parameter tractable if and only if H has bounded submodular width.
Theorem 1.4 has an algorithmic side (algorithm for bounded submodular width) and a complexity side (hardness result for unbounded submodular width).
Unlike previous width measures in the literature, where small value of the measure suggests a way of solving CSP(H) it is not at all clear how bounded submodular width is of any help. In particular, it is not obvious what submodular functions have to do with CSP instances. The main idea of our algorithm is that a CSP instance can be “split” into a small number of “uniform” CSP instances; for this purpose, we use a partitioning procedure inspired by a result of Alon et al. . More precisely, splitting means that we partition the set of tuples appearing in the constraint relations in a certain way and each new instance inherits only one class of the partition (thus each new instance has the same set of variables as the original). Uniformity means that for any subset B ⊆ A of variables, every solution for the problem restricted to B has roughly the same number of extensions to A. The property of uniformity allows us to bound the logarithm of the number of solutions on the diﬀerent subsets by a submodular function. Therefore, bounded submodular width guarantees that each uniform instance has a tree decomposition where only a polynomially bounded number of solutions has to be considered in each bag.
Conceptually, our algorithm goes beyond previous decomposition techniques in two ways.
First, the tree decomposition that we use depends not only on the hypergraph, but on the actual constraint relations in the instance (we remark that this idea ﬁrst appeared in [Marx 2011] in a diﬀerent context that does not directly apply to our problem). Second, we are not only decomposing the set of variables, but we also split the constraint relations. This way, we can apply diﬀerent decompositions to diﬀerent parts of the solution space.
The proof of the complexity side of Theorem 1.4 follows the same high-level strategy as the proof of Theorem 1.2 in [Marx 2010b]. In a nutshell, the argument of [Marx 2010b] is the following: if treewidth is large, then there is subset of vertices which is highly connected in the sense that the set does not have a small balanced separator; such a highly connected set implies that there is uniform concurrent ﬂow (i.e., a compatible set of ﬂows connecting every pair of vertices in the set); the paths in the ﬂows can be used to embed the graph of a 3SAT formula; and ﬁnally this embedding can be used to reduce 3SAT to CSP. These arguments build heavily on well-known characterizations of treewidth and results from combinatorial optimization (such as the O(log k) integrality gap of sparsest cut). The proof of Theorem 1.4 follows this outline, but now no such well-known tools are available: we are
dealing with hypergraphs and submodular functions in a way that was not explored before in the literature. Thus we have to build from scratch all the necessary tools. One of the main
diﬃculties of obtaining Theorem 1.4 is that we have to work in three diﬀerent domains:
— CSP instances. As our goal is to investigate the existence of algorithms solving CSP, the most obvious domain is CSP instances. In light of previous results, we are especially interested in algorithms based on tree decompositions. For such algorithms, what matters is the existence of subsets of vertices such that restricting the instance to any of these subsets gives an instance with “small” number of solutions. In order to solve the instance, we would like to ﬁnd a tree decomposition where every bag is such a small set.
— Submodular functions. Submodular width is deﬁned in terms of submodular functions, thus submodular functions deﬁned on hypergraphs is our second natural domain. We need to understand what large submodular width means, that is, what property of the submodular function and the hypergraph makes it impossible to obtain a tree decomposition where every bag has small value.
— Flows and embeddings in hypergraphs. In the hardness proof, our goal is to embed the graph of a 3SAT formula into a hypergraph. Thus we need to deﬁne an appropriate notion of embedding and study what guarantees the existence of embeddings with suitable properties. As in [Marx 2010b], we use the paths appearing in ﬂows to construct embeddings. For our purposes, the right notion of ﬂow is a collection of weighted paths where the total weight of the paths intersecting each hyperedge is at most 1. This notion of ﬂows has not been studied in the literature before, thus we need to obtain basic results on such ﬂows, such as exploring the duality between ﬂows and separators.
A key question is how to ﬁnd connections between these domains. As mentioned above and detailed in Section 4, we have a procedure that reduces a CSP instance into a set of uniform CSP instances, and the number of solutions on the diﬀerent subsets of variables in a uniform CSP instance can be described by a submodular function. This method allows us to move from the domain of CSP instances to the domain of submodular functions.
Journal of the ACM, Vol. V, No. N, Article A, Publication date: January YYYY.
Tractable hypergraph properties for constraint satisfaction and conjunctive queries A:7
Section 5 is devoted to showing that if submodular width of a hypergraph is large, then there is a certain “highly connected” set in the hypergraph. Highly connected set is deﬁned as a property of the hypergraph (it requires the existence of certain ﬂows) and has no longer anything to do with submodular functions. Thus this connection allows us to move from the domain of submodular functions to the study of hypergraphs. In Section 6, we show that a highly connected set in a hypergraph means that graphs can be eﬃciently embedded into the hypergraph. In particular, the graph of a 3SAT formula can be embedded into the hypergraph, which gives us (as shown in Section 7) a reduction from 3SAT to CSP(H). This connection allows us to move from the domain of embeddings back to the domain of CSP instances. We remark that Sections 4–7 are written in a self-contained way: only the ﬁrst theorem of each section is used outside the section.
A consequence of our characterization of submodular width implies the surprising fact
that bounded submodular width equals bounded adaptive width (deﬁned in [Marx 2011]):
A class of hypergraphs has bounded submodular width if and only if it has bounded adaptive width.
It is proved in [Marx 2011] that there are classes of hypergraphs having bounded adaptive width (and hence bounded submodular width), but unbounded fractional hypertree width.
Previously, bounded fractional hypertree width was the most general property that was known to guarantee ﬁxed-parameter tractability [Grohe and Marx 2012]. Thus Theorem 1.4 not only gives a complete characterization of the parameterized complexity of CSP(H), but its algorithmic side proves ﬁxed-parameter tractability in a strictly more general case than what was known before.
Why ﬁxed-parameter tractability? We argue that investigating the ﬁxed-parameter tractability of CSP(H) is at least as interesting as investigating polynomial-time solvability.
In problems coming from our database-theoretic motivation, the size of the hypergraph (that is, the size of the query) is assumed to be much smaller than the input size (which is usually dominated by the size of the database), hence a constant factor in the running time depending only on the number of variables (or on the hypergraph) is acceptable3. Even the STOC 1977 landmark paper of Chandra and Merlin , which started the complexity research on conjunctive queries, suggests spending exponential time (in the size of the query) on ﬁnding the best possible evaluation order. Furthermore, the notion of ﬁxed-parameter tractability formalizes the usual viewpoint of the literature on conjunctive queries: in the complexity analysis, we should analyze separately the contribution of the query size and the contribution of the database size.
By aiming for ﬁxed-parameter tractability, we can focus more on the core algorithmic question: is there some method for decomposing the space of all solutions in a way that allows eﬃcient evaluation of the query? Some of the progress in this area was made by introducing new decomposition techniques, without showing how to actually ﬁnd such decompositions. For example, this was the case for the papers introducing query width [Chekuri and Rajaraman 2000] and fractional hypertree width [Grohe and Marx 2012]: it was shown that if a certain type of decomposition is given, then the problem can be solved in polynomial time. In our terminology, these results already show the ﬁxed-parameter tractability of CSP(H) for the classes H where such decompositions exist (since the time required to ﬁnd an appropriate decomposition can be bounded by a function of the hypergraph H only), but do not give polynomial-time algorithms. It took some more time and eﬀort to come up with polynomial-time (approximation) algorithms for ﬁnding such decompositions [Gottlob et al. 2002a; Marx 2010a]. While investigating algorithms for ﬁnding decompositions 3 Thisassumption is valid only for evaluation problems (where the problem instance includes a large database) and not for problems that involves only queries, such as the Conjunctive Query Containment problem.
give rise to interesting and important problems, they are purely combinatorial problems on graphs and hypergraphs, and no longer has anything to do with query evaluation, constraints, or databases. Thus ﬁxed-parameter tractability gives us a formal way of ignoring these issues and focusing exclusively on the evaluation problem.