×

Constraint satisfaction with counting quantifiers. (English) Zbl 1392.68206

Summary: We initiate the study of constraint satisfaction problems (CSPs) in the presence of counting quantifiers \(\exists^{\geq j}\) which assert the existence of at least \(j\) elements such that the ensuing property holds. These are natural variants of CSPs in the mould of quantified CSPs (QCSPs). Namely, \(\exists^{\geq 1}:=\exists\) and \(\exists^{\geq n}:=\forall\) (for the domain of size \(n\)). We observe that a single counting quantifier \(\exists^{\geq j}\) strictly between \(\exists\) and \(\forall\) already affords the maximal possible complexity of QCSPs (which have both \(\exists\) and \(\forall\)), namely, being Pspace-complete for a suitably chosen template. Therefore, to better understand the complexity of this problem, we focus on restricted cases for which we derive the following results. First, for all subsets of counting quantifiers on clique and cycle templates, we give a full trichotomy – all such problems are in P, NP-complete, or Pspace-complete. Second, we consider the problem with exactly two quantifiers: \(\exists^{\geq 1}:=\exists\) and \(\exists^{\geq j}\) (\(j \neq 1\)). Such a CSP is already NP-hard on nonbipartite graph templates. We explore the situation of this generalized CSP on graph templates, giving various conditions for both tractability and hardness. For quantifiers \(\exists^{\geq 1}\) and \(\exists^{\geq 2}\), we give a dichotomy for all graphs, namely, the problem is NP-hard if the graph contains a triangle or has girth at least 5, and is in P otherwise. We strengthen this result in the following two ways. For bipartite graphs, the problem is in P for forests and graphs of girth 4, and is Pspace-hard otherwise. For complete multipartite graphs, the problem is in L, NP-complete, or Pspace-complete. Finally, using counting quantifiers we solve the complexity of a concrete QCSP whose complexity was previously open.

MSC:

68Q25 Analysis of algorithms and problem complexity
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] L. Barto, M. Kozik, and T. Niven, {\it The CSP dichotomy holds for digraphs with no sources and no sinks (a positive answer to a conjecture of Bang-Jensen and Hell)}, SIAM J. Comput., 38 (2009), pp. 1782-1802. · Zbl 1191.68460
[2] M. Bodirsky, J. Kára, and B. Martin, {\it The complexity of surjective homomorphism problems – a survey}, Discrete Appl. Math., 160 (2012), pp. 1680-1690. · Zbl 1246.05104
[3] F. Börner, A. A. Bulatov, H. Chen, P. Jeavons, and A. A. Krokhin, {\it The complexity of constraint satisfaction games and QCSP}, Inform. and Comput., 207 (2009), pp. 923-944. · Zbl 1188.68269
[4] F. Börner, A. Krokhin, A. Bulatov, and P. Jeavons, {\it Quantified Constraints and Surjective Polymorphisms}, Technical report PRG-RR-02-11, Oxford University, Oxford, 2002. · Zbl 1116.03314
[5] A. Bulatov, {\it A dichotomy theorem for constraint satisfaction problems on a 3-element set}, J. ACM, 53 (2006), pp. 66-120. · Zbl 1316.68057
[6] A. Bulatov and A. Hedayaty, {\it Counting predicates, subset surjective functions, and counting CSPs}, in 42nd IEEE International Symposium on Multiple-Valued Logic, ISMVL 2012, IEEE, Piscataway, NJ, 2012, pp. 331-336.
[7] A. Bulatov and A. Hedayaty, {\it Galois correspondence for counting quantifiers}, Multiple-Valued Logic and Soft Computing, 24 (2015), pp. 405-424. · Zbl 1394.08009
[8] A. Bulatov, P. Jeavons, and A. Krokhin, {\it Classifying the complexity of constraints using finite algebras}, SIAM J. Comput., 34 (2005), pp. 720-742. · Zbl 1071.08002
[9] P. Buneman, {\it A note on the metric properties of trees}, J. Combin. Theory Ser. B, 1 (1974), pp. 48-50. · Zbl 0286.05102
[10] H. Chen, {\it The complexity of quantified constraint satisfaction: Collapsibility, sink algebras, and the three-element case}, SIAM J. Comput., 37 (2008), pp. 1674-1701. · Zbl 1151.68025
[11] R. Clark and M. Grossman, {\it Number sense and quantifier interpretation}, Topoi, 26 (2007), pp. 51-62.
[12] H.-D. Ebbinghaus and J. Flum, {\it Finite Model Theory}, 2nd ed., Springer, Berlin, 1999. · Zbl 0932.03032
[13] L. Egri, P. Hell, B. Larose, A. Rafiey, {\it Space complexity of list \(H\)-colouring: A dichotomy}, in Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, SIAM, 2014, pp. 349-365. · Zbl 1421.68073
[14] T. Feder and P. Hell, {\it List homomorphisms to reflexive graphs}, J. Combin. Theory Ser. B, 72 (1998), pp. 236-250. · Zbl 0904.05078
[15] T. Feder, P. Hell, and J. Huang, {\it List homomorphisms and circular arc graphs}, Combinatorica, 19 (1999), pp. 487-505. · Zbl 0985.05048
[16] T. Feder and M. Y. Vardi, {\it The computational structure of monotone monadic SNP and constraint satisfaction: A study through Datalog and group theory}, SIAM J. Comput., 28 (1998), pp. 57-104. · Zbl 0914.68075
[17] M. C. Golumbic and R. E. Jamison, {\it The edge intersection graphs of paths in a tree}, J. Combin. Theory Ser. B, 38 (1985), pp. 8-22. · Zbl 0537.05063
[18] P. Hell and J. Nešetřil, {\it On the complexity of H-coloring}, J. Combin. Theory Ser. B, 48 (1990), pp. 92-110. · Zbl 0639.05023
[19] P. G. Kolaitis and M. Y. Vardi, {\it Finite Model Theory and Its Applications}, Texts Theoret. Comput. Sci. Ser., Springer-Verlag, New York, 2005.
[20] K.-J. Lange, {\it Some results on majority quantifiers over words}, in Proceedings of the 19th IEEE Annual Conference on Computational Complexity, CCC, IEEE Computer Society, Los Alamitos, CA, 2004, pp. 123-129.
[21] F. Madelaine, B. Martin, and J. Stacho, {\it Constraint satisfaction with counting quantifiers}, in Proceedings of the 7th International Computer Science Symposium on Computer Science - Theory and Applications, Nizhny Novgorod, Russia, Springer-Verlag, New York, 2012, pp. 253-265. · Zbl 1360.68514
[22] B. Martin and J. Stacho, {\it Constraint satisfaction with counting quantifiers} 2, in Proceedings of the 9th International Computer Science Symposium on Computer Science - Theory and Applications, Moscow, Russia, Springer, Cham, Switzerland, 2014. · Zbl 1407.68230
[23] B. Martin, {\it First order model checking problems parameterized by the model}, in Logic and Theory of Algorithms, Lecture Notes in Comput. Sci, 5028, Springer, Berlin, 2008, pp. 417-427. · Zbl 1142.68439
[24] B. Martin, {\it QCSP} on partially reflexive forests, in Principles and Practice of Constraint Programming, CP 2011, Lecture Notes in Comput. Sci. 6876, Springer, Heidelberg, 2011, pp. 546-560. · Zbl 1401.68124
[25] B. Martin and F. Madelaine, {\it Towards a trichotomy for quantified H-coloring}, in Logical Approaches to Computational Barriers, Lecture Notes in Comput. Sci. 3988, Springer, Berlin, 2006, pp. 342-352. · Zbl 1145.68436
[26] B. Martin and F. Madelaine, {\it QCSP} on partially reflexive cycles – the wavy line of tractability, in Computer Science - Theory and Applications, CSR 2013, Ekaterinburg, Russia, Springer, Berlin, 2013, pp. 322-333. · Zbl 1381.68099
[27] M. Otto, {\it Bounded Variable Logics and Counting – A Study in Finite Models}, Lect. Notes Log. 9, Springer, Berlin, 1997. · Zbl 0869.03018
[28] C. H. Papadimitriou, {\it Computational Complexity}, Addison-Wesley, Reading, MA, 1994. · Zbl 0833.68049
[29] O. Reingold, {\it Undirected connectivity in log-space}, J. ACM, 55 (2008), 17. · Zbl 1315.68156
[30] T. J. Schaefer, {\it The complexity of satisfiability problems}, in Proceedings of the 10th Annual ACM Symposium on Theory of Computing, ACM, New York, 1978, pp. 216-226. · Zbl 1282.68143
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.