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 (that is, 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 fixed-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 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, which can be of independent interest.
- Isolde Adler. 2006. Width functions for hypertree decompositions. Ph.D. dissertation, Albert-Ludwigs-Universität Freiburg.Google Scholar
- Isolde Adler, Georg Gottlob, and Martin Grohe. 2007. Hypertree width and related hypergraph invariants. Euro. J. Combin. 28, 8, 2167--2181. Google ScholarDigital Library
- Amit Agarwal, Noga Alon, and Moses Charikar. 2007. Improved approximation for directed cut problems. In Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC’07). ACM, New York, 671--680. Google ScholarDigital Library
- Noga Alon, Ilan Newman, Alexander Shen, Gábor Tardos, and Nikolai Vereshchagin. 2007. Partitioning multi-dimensional sets in a small number of “uniform” parts. Euro. J. Combin. 28, 1, 134--144. Google ScholarDigital Library
- Omid Amini, Frédéric Mazoit, Nicolas Nisse, and Stéphan Thomassé. 2009. Submodular partition functions. Discr. Math. 309, 20, 6000--6008. DOI:http://dx.doi.org/DOI:10.1016/j.disc.2009.04.033.Google ScholarDigital Library
- Alexandr Andoni, Piotr Indyk, and Mihai Patrascu. 2006. On the optimality of the dimensionality reduction method. In Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS’06). IEEE Computer Society, Los Alamitos, CA, 449--458. DOI:http://dx.doi.org/10.1109/FOCS.2006.56. Google ScholarDigital Library
- Albert Atserias, Andrei A. Bulatov, and Víctor Dalmau. 2007. On the power of k-consistency. In Proceedings of ICALP. 279--290. Google ScholarDigital Library
- Catriel Beeri, Ronald Fagin, David Maier, Alberto O. Mendelzon, Jeffrey D. Ullman, and Mihalis Yannakakis. 1981. Properties of acyclic database schemes. In Proceedings of STOC. 355--362. Google ScholarDigital Library
- Catriel Beeri, Ronald Fagin, David Maier, and Mihalis Yannakakis. 1983. On the desirability of acyclic database schemes. J. ACM 30, 3, 479--513. Google ScholarDigital Library
- Andrei A. Bulatov. 2006. A dichotomy theorem for constraint satisfaction problems on a 3-element set. J. ACM 53, 1, 66--120. Google ScholarDigital Library
- Andrei A. Bulatov. 2011. Complexity of conservative constraint satisfaction problems. ACM Trans. Comput. Log. 12, 4, Article 24. Google ScholarDigital Library
- A. A. Bulatov, A. A. Krokhin, and P. Jeavons. 2001. The complexity of maximal constraint languages. In Proceedings of the 33rd ACM Symposium on Theory of Computing. 667--674. Google ScholarDigital Library
- Ashok K. Chandra and Philip M. Merlin. 1977. Optimal implementation of conjunctive queries in relational data bases. In Proceedings of STOC. 77--90. Google ScholarDigital Library
- Chandra Chekuri and Anand Rajaraman. 2000. Conjunctive query containment revisited. Theoret. Comput. Sci. 239, 2, 211--229. Google ScholarDigital Library
- Hubie Chen and Martin Grohe. 2010. Constraint satisfaction with succinctly specified relations. J. Comput. Syst. Sci. 76, 8, 847--860. Google ScholarDigital Library
- F. R. K. Chung, R. L. Graham, P. Frankl, and J. B. Shearer. 1986. Some intersection theorems for ordered sets and graphs. J. Combin. Theory Ser. A 43, 1, 23--37. Google ScholarDigital Library
- Víctor Dalmau, Phokion G. Kolaitis, and Moshe Y. Vardi. 2002. Constraint satisfaction, bounded treewidth, and finite-variable logics. In Proceedings of the 8th International Conference on Principles and Practice of Constraint Programming (CP’02). Springer-Verlag, 310--326. Google ScholarDigital Library
- R. G. Downey and M. R. Fellows. 1999. Parameterized Complexity. Springer, New York. Google ScholarDigital Library
- Ronald Fagin. 1983. Degrees of acyclicity for hypergraphs and relational database schemes. J. ACM 30, 3, 514--550. Google ScholarDigital Library
- Tomás Feder and Moshe Y. Vardi. 1999. The computational structure of monotone monadic SNP and constraint satisfaction: A study through Datalog and group theory. SIAM J. Comput. 28, 1, 57--104. Google ScholarDigital Library
- Jörg Flum and Martin Grohe. 2006. Parameterized Complexity Theory. Springer, Berlin. Google ScholarDigital Library
- E. C. Freuder. 1990. Complexity of k-tree structured constraint satisfaction problems. In Proceedings of AAAI-90. 4--9. Google ScholarDigital Library
- G. Gottlob and S. Szeider. 2008. Fixed-parameter algorithms for artificial intelligence, constraint satisfaction and database problems. Comput. J. 51, 3, 303--325. Google ScholarDigital Library
- G. Gottlob, N. Leone, and F. Scarcello. 2002a. Hypertree decompositions and tractable queries. J. Comput. System Sci. 64, 579--627.Google ScholarDigital Library
- Georg Gottlob, Francesco Scarcello, and Martha Sideri. 2002b. Fixed-parameter complexity in AI and nonmonotonic reasoning. Artif. Intell. 138, 1--2, 55--86. Google ScholarDigital Library
- Gianluigi Greco and Francesco Scarcello. 2010. The power of tree projections: Local consistency, greedy algorithms, and larger islands of tractability. In Proceedings of the 29th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS’10). ACM, New York, 327--338. DOI:http://dx.doi.org/10.1145/1807085.1807127. Google ScholarDigital Library
- Martin Grohe. 2006. The structure of tractable constraint satisfaction problems. In Proceedings of MFCS’06. 58--72. Google ScholarDigital Library
- Martin Grohe. 2007. The complexity of homomorphism and constraint satisfaction problems seen from the other side. J. ACM 54, 1, 1. DOI:http://dx.doi.org/10.1145/1206035.1206036. Google ScholarDigital Library
- Martin Grohe and Dániel Marx. 2009. On tree width, bramble size, and expansion. J. Combinat. Theory Ser. B 99, 1, 218--228. Google ScholarDigital Library
- Martin Grohe and Dániel Marx. 2012+. Constraint solving via fractional edge covers. (2012+). To appear. ACM Trans. Algor.Google Scholar
- Anupam Gupta. 2003. Improved results for directed multicut. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM, New York, 454--455. Google ScholarDigital Library
- Mohammad Taghi Hajiaghayi and Harald Räcke. 2006. An O(√n)-approximation algorithm for directed sparsest cut. Inform. Process. Lett. 97, 4, 156--160. Google ScholarDigital Library
- Petr Hliněný. 2005. A parametrized algorithm for matroid branch-width. SIAM J. Comput. 35, 2, 259--277. Google ScholarDigital Library
- Petr Hliněný and Sang-il Oum. 2008. Finding branch-decompositions and rank-decompositions. SIAM J. Comput. 38, 3, 1012--1032. Google ScholarDigital Library
- Petr Hliněný and Geoff Whittle. 2006. Matroid tree-width. European J. Combin. 27, 7, 1117--1128. Google ScholarDigital Library
- Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. 2001. Which problems have strongly exponential complexity? J. Comput. System Sci. 63, 4, 512--530. Google ScholarDigital Library
- Satoru Iwata. 2008. Submodular function minimization. Math. Program. 112, 1, Ser. B, 45--64. Google ScholarDigital Library
- Satoru Iwata, Lisa Fleischer, and Satoru Fujishige. 2001. A combinatorial strongly polynomial algorithm for minimizing submodular functions. J. ACM 48, 4, 761--777. Google ScholarDigital Library
- P. Jeavons, D. A. Cohen, and M. Gyssens. 1997. Closure properties of constraints. J. ACM 44, 4, 527--548. Google ScholarDigital Library
- Phokion G. Kolaitis and Moshe Y. Vardi. 2000a. Conjunctive-query containment and constraint satisfaction. J. Comput. Syst. Sci. 61, 2, 302--332. DOI:http://dx.doi.org/10.1006/jcss.1713. Google ScholarDigital Library
- Phokion G. Kolaitis and Moshe Y. Vardi. 2000b. A game-theoretic approach to constraint satisfaction. In Proceedings of AAAI/IAAI. 175--181. Google ScholarDigital Library
- Dániel Marx. 2007. On the optimality of planar and geometric approximation schemes. In Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS’07). 338--348. Google ScholarDigital Library
- Dániel Marx. 2010a. Approximating fractional hypertree width. ACM Trans. Algor. 6, 2, 1--17. DOI:http://dx.doi.org/10.1145/1721837.1721845. Google ScholarDigital Library
- Dániel Marx. 2010b. Can You Beat Treewidth? Theory Comput. 6, 1, 85--112. DOI:http://dx.doi.org/10.4086/toc.2010.v006a005.Google Scholar
- Dániel Marx. 2010c. Tractable hypergraph properties for constraint satisfaction and conjunctive queries. In Proceedings of the 42nd ACM Symposium on Theory of Computing. 735--744. Google ScholarDigital Library
- Dániel Marx. 2011. Tractable structures for constraint satisfaction with truth tables. Theory Comput. Syst. 48, 444--464. Google ScholarDigital Library
- Rolf Niedermeier. 2006. Invitation to Fixed-Parameter Algorithms. Oxford Lecture Series in Mathematics and its Applications, Vol. 31, Oxford University Press, Oxford.Google Scholar
- Sang-il Oum. 2005. Approximating rank-width and clique-width quickly. In Proceedings of the 31st International Workshop on Graph-Theoretic Concepts in Computer Science. 49--58. Google ScholarDigital Library
- Sang-il Oum and Paul Seymour. 2006. Approximating clique-width and branch-width. J. Combin. Theory Ser. B 96, 4, 514--528. Google ScholarDigital Library
- Sang-il Oum and Paul Seymour. 2007. Testing branch-width. J. Combin. Theory Ser. B 97, 3, 385--393. Google ScholarDigital Library
- Mihai Pǎtraşcu and Ryan Williams. 2010. On the possibility of faster SAT algorithms. In Proceedings of the 21st ACM/SIAM Symposium on Discrete Algorithms (SODA). 1065--1075. Google ScholarDigital Library
- Francesco Scarcello, Georg Gottlob, and Gianluigi Greco. 2008. Uniform constraint satisfaction problems and database theory. In Complexity of Constraints, 156--195. Google ScholarDigital Library
- Thomas J. Schaefer. 1978. The complexity of satisfiability problems. In Conference Record of the 10th Annual ACM Symposium on Theory of Computing. ACM, New York, 216--226. Google ScholarDigital Library
- Alexander Schrijver. 2000. A combinatorial algorithm minimizing submodular functions in strongly polynomial time. J. Combin. Theory Ser. B 80, 2, 346--355. Google ScholarDigital Library
- Mihalis Yannakakis. 1981. Algorithms for acyclic database schemes. In Proceedings of VLDB. 82--94. Google ScholarDigital Library
Index Terms
- Tractable Hypergraph Properties for Constraint Satisfaction and Conjunctive Queries
Recommendations
Constraint Solving via Fractional Edge Covers
Many important combinatorial problems can be modeled as constraint satisfaction problems. Hence, identifying polynomial-time solvable classes of constraint satisfaction problems has received a lot of attention. In this article, we are interested in ...
Tractable hypergraph properties for constraint satisfaction and conjunctive queries
STOC '10: Proceedings of the forty-second ACM symposium on Theory of computingAn 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., ...
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