«A Tractable hypergraph properties for constraint satisfaction and conjunctive queries1 D´niel Marx, Computer and Automation Research Institute, ...»
A diﬀerent version of CSP was investigated in [Marx 2011], where each variable has a diﬀerent domain, and each constraint relation is represented by a full truth table (see the exact deﬁnition in [Marx 2011]). Let us denote by CSPtt (H) this variant of the problem. It is easy to see that CSPtt (H) can be reduced to CSP(H) in polynomial time, but a reduction in the other direction can possibly increase the representation of a constraint by an exponential factor. Nevertheless, the hardness results of this section apply to the “easier” problem CSPtt (H) as well. What we have to verify is that the proof of Lemma 7.5 works even if I2 is an instance of CSPtt, i.e., the constraint relations have to be represented by truth tables. Inspection of the proof shows that it indeed works: the product in Inequality (4) is exactly the size of the truth table describing the constraint corresponding to edge e, thus the |D1 |q upper bound remains valid even if constraints are represented by truth tables. Therefore, the hardness results of [Marx 2011] are subsumed by the following
Corollary 7.8. If H is a recursively enumerable class of hypergraphs with unbounded submodular width, then CSPtt (H) is not ﬁxed-parameter tractable, unless the Exponential Time Hypothesis fails.
8. CONCLUSIONS The main result of the paper is introducing submodular width and proving that bounded submodular width is the property that determines the ﬁxed-parameter tractability of CSP(H). The hardness result is proved assuming the Exponential Time Hypothesis. This conjecture was formulated relatively recently [Impagliazzo et al. 2001], but it turned out to be very useful in proving lower bounds in a variety of settings [Marx 2010b; Andoni et al.
2006; Marx 2007; Pˇtra¸cu and Williams 2010].
as For the hardness proof, we had to understand what large submodular width means and we had to explore the connection between submodular width and other combinatorial properties. We have obtained several equivalent characterizations of bounded submodular width, in particular, we have showed that bounded submodular width is equivalent to bounded
Corollary 8.1. The following are equivalent for every class H of hypergraphs:
(1 ) There is a constant c1 such that µ-width(H) ≤ c1 for every H ∈ H and fractional independent set µ.
(2 ) There is a constant c2 such that b-width(H) ≤ c2 for every H ∈ H and edgedominated monotone submodular function b on V (H) with b(∅) = 0.
(3 ) There is a constant c3 such that b∗ -width(H) ≤ c3 for every H ∈ H and edgedominated monotone submodular function b on V (H) with b(∅) = 0.
Journal of the ACM, Vol. V, No. N, Article A, Publication date: January YYYY.
Tractable hypergraph properties for constraint satisfaction and conjunctive queries A:45 (4 ) There is a constant c4 such that conλ (H) ≤ c4 for every H ∈ H, where λ 0 is a universal constant.
(5 ) There is a constant c5 such that emb(H) ≤ c5 for every H ∈ H.
Implications (2)⇒(1) and (3)⇒(2) are trivial; (4)⇒(3) follows from Lemma 5.10; (5)⇒(4) follows from Corollary 6.2; (1)⇒(5) follows from Lemma 6.9.
Let us brieﬂy review the main ideas that were necessary for proving the main result of
— Recognizing that submodular width is the right property characterizing the complexity of the problem.
— A CSP instance can be partitioned into a bounded number of uniform instances (Section 4.2).
— The number of solutions in a uniform CSP instance can be described by a submodular function (Section 4.3).
— There is a connection between fractional separation and ﬁnding a separator minimizing an edge-dominated submodular cost function (Section 5.2).
— The transformation that turns b into b∗, and the properties of b∗ that are more suitable than b for recursively constructing a tree decomposition (Section 5.1).
— Our results on fractional separation and the standard framework of ﬁnding tree decompositions show that large submodular width implies that there is a highly connected set (Section 5.3).
— A highly connected set can be turned into a highly connected set that is partitioned into cliques in an appropriate way (Section 6.1).
— A highly connected set with appropriate cliques implies that there is a uniform concurrent ﬂow of large value between the cliques (Section 6.2).
— Similarly to [Marx 2010b], we use the observation that a concurrent ﬂow is analogous to a line graph of a clique, hence it has good embedding properties (Section 6.2).
— Similarly to [Marx 2010b], an embedding in a hypergraph gives a way of simulating 3SAT with CSP(H) (Section 7).
It is possible that the main result can be proved in a simpler way by bypassing some of the ideas above. In particular, a surprising consequence of our results is that bounded submodular width and bounded adaptive width are the same, i.e., if a class H has unbounded submodular width, then for every k there is a Hk ∈ H and a fractional independent set µk such that µk -width(Hk ) ≥ k, or in other words, large submodular width can be certiﬁed by the modular function µk. To prove this, we need all the results of Sections 5 and 6. Having a better understanding and an independent proof of this fact could simplify the proofs considerably. Another possible target for simpliﬁcation is Section 6.1, where a lot of eﬀort is spent on proving that if there is a large highly connected set, then there is a large highly connected set that is partitioned into cliques in an appropriate way. It might be possible to strengthen the results of Section 5 (perhaps by better understanding the role of cliques in separators) so that they give such a highly connected set directly.
An obvious question for further research is whether it is possible to prove a similar dichotomy result with respect to polynomial-time solvability. At this point, it is hard to see what the answer could be if we investigate the same question using the more restricted notion of polynomial time solvability. We know that bounded fractional hypertree width implies polynomial-time solvability [Marx 2010a] and Theorem 7.1 shows that unbounded submodular width implies that the problem is not polynomial-time solvable (as it is not even ﬁxed-parameter tractable). So only those classes of hypergraphs are in the “gray zone” that have bounded submodular width but unbounded fractional hypertree width.
What could be the truth in this gray zone? A ﬁrst possibility is that CSP(H) is polynomial-time solvable for every such class, i.e., Theorem 4.1 can be improved from Journal of the ACM, Vol. V, No. N, Article A, Publication date: January YYYY.
A:46 D. Marx ﬁxed-parameter tractability to polynomial-time solvability. However, Theorem 4.1 uses the power of ﬁxed-parameter tractability in an essential way (splitting into a double-exponential number of uniform instances), so it is not clear how such improvement is possible. A second possibility is that unbounded fractional hypertree width implies that CSP(H) is not polynomial-time solvable. Substantially new techniques would be required for such a hardness proof. The hardness proofs of this paper and of [Grohe 2007; Marx 2010b] are based on showing that a large problem space can be eﬃciently embedded into an instance with a particular hypergraph. However, the ﬁxed-parameter tractability results show that no such embedding is possible in case of classes with bounded submodular width. Therefore, a possible hardness proof should embed a problem space that is comparable (in some sense) with the size of the hypergraph and should create instances where the domain size is bounded by a function of the size of the hypergraph. A third possibility is that the boundary of polynomial-time solvability is somewhere between bounded fractional hypertree width and bounded submodular width. Currently, there is no natural candidate for a property that could correspond to this boundary and, again, the hardness part of the characterization should be substantially diﬀerent than what was done before. Finally, there is a fourth possibility: the boundary of the polynomial-time cases cannot be elegantly characterized by a simple combinatorial property. In general, if we consider the restriction of a problem to all possible classes of (hyper)graphs, then there is no a priori reason why an elegant characterization should exist that describes the easy and hard classes. For example, it is highly unlikely that there is an elegant characterization of those classes of graphs where solving the Maximum Independent Set problem is polynomial-time solvable. As discussed earlier, the ﬁxed-parameter tractability of CSP(H) is a more robust question than its polynomialtime solvability, hence it is very well possible that only the former question has an elegant answer.
REFERENCES Isolde Adler. 2006. Width functions for hypertree decompositions. Ph.D. Dissertation. Albert-LudwigsUniversit¨t Freiburg.
a Isolde Adler, Georg Gottlob, and Martin Grohe. 2007. Hypertree width and related hypergraph invariants.
European J. Combin. 28, 8 (2007), 2167–2181.
Amit Agarwal, Noga Alon, and Moses Charikar. 2007. Improved approximation for directed cut problems.
In STOC’07—Proceedings of the 39th Annual ACM Symposium on Theory of Computing. ACM, New York, 671–680.
Noga Alon, Ilan Newman, Alexander Shen, G´bor Tardos, and Nikolai Vereshchagin. 2007. Partitioning a multi-dimensional sets in a small number of “uniform” parts. European J. Combin. 28, 1 (2007), 134– 144.
Omid Amini, Fr´d´ric ee Mazoit, Nicolas Nisse, and St´phan e Thomass´.
e 2009. Submodular partition functions. Discrete Mathematics 309, 20 (2009), 6000 – 6008.
DOI:http://dx.doi.org/DOI:10.1016/j.disc.2009.04.033 Alexandr Andoni, Piotr Indyk, and Mihai Patrascu. 2006. On the Optimality of the Dimensionality Reduction Method. In FOCS ’06: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS’06). IEEE Computer Society, Washington, DC, USA, 449–458.
DOI:http://dx.doi.org/10.1109/FOCS.2006.56 Albert Atserias, Andrei A. Bulatov, and V´ ıctor Dalmau. 2007. On the Power of k-Consistency. In ICALP.
Catriel Beeri, Ronald Fagin, David Maier, Alberto O. Mendelzon, Jeﬀrey D. Ullman, and Mihalis Yannakakis. 1981. Properties of Acyclic Database Schemes. In STOC. 355–362.
Catriel Beeri, Ronald Fagin, David Maier, and Mihalis Yannakakis. 1983. On the desirability of acyclic database schemes. J. Assoc. Comput. Mach. 30, 3 (1983), 479–513.
Andrei A. Bulatov. 2003. Tractable conservative Constraint Satisfaction Problems. In 18th Annual IEEE Symposium on Logic in Computer Science (LICS’03). IEEE Computer Society, Los Alamitos, CA, USA, 321.
Andrei A. Bulatov. 2006. A dichotomy theorem for constraint satisfaction problems on a 3-element set. J.
ACM 53, 1 (2006), 66–120.
Journal of the ACM, Vol. V, No. N, Article A, Publication date: January YYYY.
Tractable hypergraph properties for constraint satisfaction and conjunctive queries A:47 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.
Ashok K. Chandra and Philip M. Merlin. 1977. Optimal Implementation of Conjunctive Queries in Relational Data Bases. In STOC. 77–90.
Chandra Chekuri and Anand Rajaraman. 2000. Conjunctive query containment revisited. Theoret. Comput.
Sci. 239, 2 (2000), 211–229.
Hubie Chen and Martin Grohe. 2010. Constraint satisfaction with succinctly speciﬁed relations. J. Comput.
Syst. Sci. 76, 8 (2010), 847–860.
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 (1986), 23–37.
V´ıctor Dalmau, Phokion G. Kolaitis, and Moshe Y. Vardi. 2002. Constraint Satisfaction, Bounded Treewidth, and Finite-Variable Logics. In CP ’02: Proceedings of the 8th International Conference on Principles and Practice of Constraint Programming. Springer-Verlag, London, UK, 310–326.
R. G. Downey and M. R. Fellows. 1999. Parameterized Complexity. Springer, New York. xvi+533 pages.
Ronald Fagin. 1983. Degrees of acyclicity for hypergraphs and relational database schemes. J. Assoc. Comput. Mach. 30, 3 (1983), 514–550.
Tom´s Feder and Moshe Y. Vardi. 1999. The computational structure of monotone monadic SNP and a constraint satisfaction: a study through Datalog and group theory. SIAM J. Comput. 28, 1 (1999), 57–104.
J¨rg Flum and Martin Grohe. 2006. Parameterized Complexity Theory. Springer, Berlin.
o E. C. Freuder. 1990. Complexity of K-Tree Structured Constraint Satisfaction Problems. In Proc. of AAAIBoston, MA, 4–9.
G. Gottlob, N. Leone, and F. Scarcello. 2002a. Hypertree Decompositions and Tractable Queries. J. Comput.
System Sci. 64 (2002), 579–627.
Georg Gottlob, Francesco Scarcello, and Martha Sideri. 2002b. Fixed-parameter complexity in AI and nonmonotonic reasoning. Artiﬁcial Intelligence 138, 1-2 (2002), 55–86.
G. Gottlob and S. Szeider. 2008. Fixed-Parameter Algorithms For Artiﬁcial Intelligence, Constraint Satisfaction and Database Problems. Comput. J. 51, 3 (2008), 303–325.
Gianluigi Greco and Francesco Scarcello. 2010. The power of tree projections: local consistency, greedy algorithms, and larger islands of tractability. In Proceedings of the twenty-ninth ACM SIGMOD-SIGACTSIGART symposium on Principles of database systems (PODS ’10). ACM, New York, NY, USA, 327–338. DOI:http://dx.doi.org/10.1145/1807085.1807127 Martin Grohe. 2006. The Structure of Tractable Constraint Satisfaction Problems.. In MFCS 2006. 58–72.
Martin Grohe. 2007. The complexity of homomorphism and constraint satisfaction problems seen from the other side. J. ACM 54, 1 (2007), 1. DOI:http://dx.doi.org/10.1145/1206035.1206036 Martin Grohe and D´niel Marx. 2009. On tree width, bramble size, and expansion. Journal of Combinatorial a Theory Ser. B 99, 1 (2009), 218–228.
Martin Grohe and D´niel Marx. 2012+. Constraint solving via fractional edge covers. (2012+). To appear a in ACM Transactions on Algorithm.
Anupam Gupta. 2003. Improved results for directed multicut. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (Baltimore, MD, 2003). ACM, New York, 454–455.
√ Mohammad Taghi Hajiaghayi and Harald R¨cke. 2006. An O( n)-approximation algorithm for directed a sparsest cut. Inform. Process. Lett. 97, 4 (2006), 156–160.
Petr Hlinˇn´. 2005. A parametrized algorithm for matroid branch-width. SIAM J. Comput. 35, 2 (2005), ey 259–277.
Petr Hlinˇn´ and Sang-il Oum. 2008. Finding branch-decompositions and rank-decompositions. SIAM J.
ey Comput. 38, 3 (2008), 1012–1032.
Petr Hlinˇn´ and Geoﬀ Whittle. 2006. Matroid tree-width. European J. Combin. 27, 7 (2006), 1117–1128.
ey Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. 2001. Which problems have strongly exponential complexity? J. Comput. System Sci. 63, 4 (2001), 512–530.
Satoru Iwata. 2008. Submodular function minimization. Math. Program. 112, 1, Ser. B (2008), 45–64.
Satoru Iwata, Lisa Fleischer, and Satoru Fujishige. 2001. A combinatorial strongly polynomial algorithm for minimizing submodular functions. J. ACM 48, 4 (2001), 761–777 (electronic).
P. Jeavons, D. A. Cohen, and M. Gyssens. 1997. Closure properties of constraints. J. ACM 44, 4 (1997), 527–548.
Phokion G. Kolaitis and Moshe Y. Vardi. 2000a. Conjunctive-query containment and constraint satisfaction.
J. Comput. Syst. Sci. 61, 2 (2000), 302–332. DOI:http://dx.doi.org/10.1006/jcss.2000.1713 Journal of the ACM, Vol. V, No. N, Article A, Publication date: January YYYY.
A:48 D. Marx Phokion G. Kolaitis and Moshe Y. Vardi. 2000b. A Game-Theoretic Approach to Constraint Satisfaction.
In AAAI/IAAI. 175–181.
D´niel Marx. 2007. On the optimality of planar and geometric approximation schemes. In 48th Annual a IEEE Symposium on Foundations of Computer Science (FOCS’07). 338–348.
D´niel Marx. 2010a. Approximating fractional hypertree width. ACM Trans. Algorithms 6, 2 (2010), 1–17.
a DOI:http://dx.doi.org/10.1145/1721837.1721845 D´niel Marx. 2010b. Can You Beat Treewidth? Theory of Computing 6, 1 (2010), 85–112.
a DOI:http://dx.doi.org/10.4086/toc.2010.v006a005 D´niel Marx. 2010c. Tractable hypergraph properties for constraint satisfaction and conjunctive queries. In a Proceedings of the 42nd ACM Symposium on Theory of Computing. 735–744.
D´niel Marx. 2011. Tractable Structures for Constraint Satisfaction with Truth Tables. Theory of Computing a Systems 48 (2011), 444–464.
Rolf Niedermeier. 2006. Invitation to ﬁxed-parameter algorithms. Oxford Lecture Series in Mathematics and its Applications, Vol. 31. Oxford University Press, Oxford. xii+300 pages.
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.
Sang-il Oum and Paul Seymour. 2007. Testing branch-width. J. Combin. Theory Ser. B 97, 3 (2007), 385–393.
Sang-il Oum and Paul Seymour. 2006. Approximating clique-width and branch-width. J. Combin. Theory Ser. B 96, 4 (2006), 514–528.
Mihai Pˇtra¸cu and Ryan Williams. 2010. On the Possibility of Faster SAT Algorithms. In Proc. 21st as ACM/SIAM Symposium on Discrete Algorithms (SODA). 1065–1075.
Francesco Scarcello, Georg Gottlob, and Gianluigi Greco. 2008. Uniform Constraint Satisfaction Problems and Database Theory. In Complexity of Constraints. 156–195.
Thomas J. Schaefer. 1978. The complexity of satisﬁability problems. In Conference Record of the Tenth Annual ACM Symposium on Theory of Computing (San Diego, Calif., 1978). ACM, New York, 216– 226.
Alexander Schrijver. 2000. A combinatorial algorithm minimizing submodular functions in strongly polynomial time. J. Combin. Theory Ser. B 80, 2 (2000), 346–355.
Mihalis Yannakakis. 1981. Algorithms for Acyclic Database Schemes. In VLDB. 82–94.