ABSTRACT
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 influences 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. 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 fixed-parameter tractable, parameterized by the number of variables. 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 fixed-parameter tractable. In a matching hardness result, we show that if H has unbounded submodular width, then CSP(H) is not fixed-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 different 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 efficiently simulated by a CSP instance whose hypergraph is H. To prove these combinatorial results, we need to develop a theory of (multicommodity) flows on hypergraphs and vertex separators in the case when the function b(S) defining the cost of separator S is submodular.
- I. Adler. Width functions for hypertree decompositions. PhD thesis, Albert-Ludwigs-Universität Freiburg, 2006.Google Scholar
- I. Adler, G. Gottlob, and M. Grohe. Hypertree width and related hypergraph invariants. European J. Combin., 28(8):2167--2181, 2007. Google ScholarDigital Library
- N. Alon, I. Newman, A. Shen, G. Tardos, and N. Vereshchagin. Partitioning multi-dimensional sets in a small number of "uniform" parts. European J. Combin., 28(1):134--144, 2007. Google ScholarDigital Library
- C. Beeri, R. Fagin, D. Maier, A. O. Mendelzon, J. D. Ullman, and M. Yannakakis. Properties of acyclic database schemes. In STOC, pages 355--362, 1981. Google ScholarDigital Library
- C. Beeri, R. Fagin, D. Maier, and M. Yannakakis. On the desirability of acyclic database schemes. J. Assoc. Comput. Mach., 30(3):479--513, 1983. Google ScholarDigital Library
- A. K. Chandra and P. M. Merlin. Optimal implementation of conjunctive queries in relational data bases. In STOC, pages 77--90, 1977. Google ScholarDigital Library
- C. Chekuri and A. Rajaraman. Conjunctive query containment revisited. Theoret. Comput. Sci., 239(2):211--229, 2000. Google ScholarDigital Library
- H. Chen and M. Grohe. Constraint satisfaction problems with succinctly specified relations, 2006. Manuscript. Preliminary version in Dagstuhl Seminar Proceedings 06401: Complexity of Constraints.Google Scholar
- F. R. K. Chung, R. L. Graham, P. Frankl, and J. B. Shearer. Some intersection theorems for ordered sets and graphs. J. Combin. Theory Ser. A, 43(1):23--37, 1986. Google ScholarDigital Library
- R. G. Downey and M. R. Fellows. Parameterized Complexity. Monographs in Computer Science. Springer, New York, 1999. Google ScholarDigital Library
- R. Fagin. Degrees of acyclicity for hypergraphs and relational database schemes. J. Assoc. Comput. Mach., 30(3):514--550, 1983. Google ScholarDigital Library
- T. Feder and M. Y. Vardi. The computational structure of monotone monadic SNP and constraint satisfaction: a study through Datalog and group theory. SIAM J. Comput., 28(1):57--104, 1999. Google ScholarDigital Library
- J. Flum and M. Grohe. Parameterized Complexity Theory. Springer, Berlin, 2006. Google ScholarDigital Library
- E. C. Freuder. Complexity of k-tree structured constraint satisfaction problems. In Proc. of AAAI-90, pages 4--9, Boston, MA, 1990.Google ScholarDigital Library
- G. Gottlob, N. Leone, and F. Scarcello. Hypertree decompositions and tractable queries. Journal of Computer and System Sciences, 64:579--627, 2002.Google ScholarDigital Library
- G. Gottlob, F. Scarcello, and M. Sideri. Fixed-parameter complexity in AI and nonmonotonic reasoning. Artificial Intelligence, 138(1-2):55--86, 2002. Google ScholarDigital Library
- G. Gottlob and S. Szeider. Fixed-parameter algorithms for artificial intelligence, constraint satisfaction and database problems. The Computer Journal, 51(3):303--325, 2008. Google ScholarDigital Library
- M. Grohe. The structure of tractable constraint satisfaction problems. In MFCS'06, pages 58--72, 2006. Google ScholarDigital Library
- M. Grohe. The complexity of homomorphism and constraint satisfaction problems seen from the other side. J. ACM, 54(1):1, 2007. Google ScholarDigital Library
- M. Grohe and D. Marx. Constraint solving via fractional edge covers. In SODA'06, pages 289--298, 2006. Google ScholarDigital Library
- M. Grohe and D. Marx. On tree width, bramble size, and expansion. J. Combin. Theory Ser. B, 99(1):218--228, 2009. Google ScholarDigital Library
- R. Impagliazzo, R. Paturi, and F. Zane. Which problems have strongly exponential complexity? J. Comput. System Sci., 63(4):512--530, 2001. Google ScholarDigital Library
- P. G. Kolaitis and M. Y. Vardi. Conjunctive-query containment and constraint satisfaction. J. Comput. Syst. Sci., 61(2):302--332, 2000. Google ScholarDigital Library
- D. Marx. Can you beat treewidth? To appear in Theory of Computing. Conference version in FOCS 2007. Google ScholarDigital Library
- D. Marx. Approximating fractional hypetree width. In SODA'09, pages 902--911, 2009. Google ScholarDigital Library
- D. Marx. Tractable structures for constraint satisfaction with truth tables. In STACS'09, pages 649--660, 2009.Google Scholar
- R. Niedermeier. Invitation to fixed-parameter algorithms, volume 31 of Oxford Lecture Series in Mathematics and its Applications. Oxford University Press, Oxford, 2006.Google Scholar
- S. Oum. Approximating rank-width and clique-width quickly. In WG'05, pages 49--58, 2005. Google ScholarDigital Library
- S. Oum and P. Seymour. Testing branch-width. J. Combin. Theory Ser. B, 97(3):385--393, 2007. Google ScholarDigital Library
- S.-i. Oum and P. Seymour. Approximating clique-width and branch-width. J. Combin. Theory Ser. B, 96(4):514--528, 2006. Google ScholarDigital Library
- F. Scarcello, G. Gottlob, and G. Greco. Uniform constraint satisfaction problems and database theory. In Complexity of Constraints, pages 156--195, 2008. Google ScholarDigital Library
- M. Yannakakis. Algorithms for acyclic database schemes. In VLDB, pages 82--94, 1981. Google ScholarDigital Library
Index Terms
- Tractable hypergraph properties for constraint satisfaction and conjunctive queries
Recommendations
Tractable Hypergraph Properties for Constraint Satisfaction and Conjunctive Queries
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 influences the complexity of the problem. For binary CSP instances (that is, ...
Fixed-parameter complexity in AI and nonmonotonic reasoning
Many relevant intractable problems become tractable if some problem parameter is fixed. However, various problems exhibit very different computational properties, depending on how the runtime required for solving them is related to the fixed parameter ...
Tractable Structures for Constraint Satisfaction with Truth Tables
The way the graph structure of the constraints influences the complexity of constraint satisfaction problems (CSP) is well understood for bounded-arity constraints. The situation is less clear if there is no bound on the arities. In this case the answer ...
Comments