research-article

A universal-algebraic proof of the complexity dichotomy for Monotone Monadic SNP

Authors:

Manuel Bodirsky,

Florent Madelaine,

Antoine MottetAuthors Info & Claims

LICS '18: Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science

Pages 105 - 114

https://doi.org/10.1145/3209108.3209156

Published: 09 July 2018 Publication History

Abstract

The logic MMSNP is a restricted fragment of existential second-order logic which allows to express many interesting queries in graph theory and finite model theory. The logic was introduced by Feder and Vardi who showed that every MMSNP sentence is computationally equivalent to a finite-domain constraint satisfaction problem (CSP); the involved probabilistic reductions were derandomized by Kun using explicit constructions of expander structures. We present a new proof of the reduction to finite-domain CSPs that does not rely on the results of Kun. This new proof allows us to obtain a stronger statement and to verify the Bodirsky-Pinsker dichotomy conjecture for CSPs in MMSNP. Our approach uses the fact that every MMSNP sentence describes a finite union of CSPs for countably infinite ω-categorical structures; moreover, by a recent result of Hubička and Nešetřil, these structures can be expanded to homogeneous structures with finite relational signature and the Ramsey property. This allows us to use the universal-algebraic approach to study the computational complexity of MMSNP.

References

[1]

Libor Barto, Michael Kompatscher, Miroslav Olšák, Michael Pinsker, and Trung Van Pham. 2017. The Two Dichotomy Conjectures for Infinite Domain Constraint Satisfaction Problems Are Equivalent. In Proceedings of the 32nd Annual IEEE Symposium on Logic in Computer Science -- LICS'17.

[2]

Libor Barto and Marcin Kozik. 2012. Absorbing subalgebras, cyclic terms and the constraint satisfaction problem. Logical Methods in Computer Science 8/1, 07 (2012), 1--26.

[3]

Libor Barto, Jakub Opršal, and Michael Pinsker. 2017. The wonderland of reflections. Israel Journal of Mathematics (2017). To appear. Preprint arXiv:1510.04521.

[4]

Libor Barto and Michael Pinsker. 2016. The algebraic dichotomy conjecture for infinite domain constraint satisfaction problems. In Proceedings of the 31th Annual IEEE Symposium on Logic in Computer Science -- LICS'16. 615--622.

Digital Library

[5]

Manuel Bodirsky. 2007. Cores of countably categorical structures. Logical Methods in Computer Science 3, 1 (2007), 1--16.

[6]

Manuel Bodirsky. 2012. Complexity Classification in Infinite-Domain Constraint Satisfaction. (2012). Mémoire d'habilitation à diriger des recherches, Université Diderot -- Paris 7. Available at arXiv:1201.0856v8.

[7]

Manuel Bodirsky. 2015. Ramsey Classes: Examples and Constructions. In Surveys in Combinatorics. London Mathematical Society Lecture Note Series 424. Cambridge University Press. Invited survey article for the British Combinatorial Conference.

[8]

Manuel Bodirsky and Víctor Dalmau. 2013. Datalog and Constraint Satisfaction with Infinite Templates. Journal on Computer and System Sciences 79 (2013), 79--100. A preliminary version appeared in the proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS'05).

Digital Library

[9]

Manuel Bodirsky and Antoine Mottet. 2016. Reducts of finitely bounded homogeneous structures, and lifting tractability from finite-domain constraint satisfaction. In Proceedings of the 31th Annual IEEE Symposium on Logic in Computer Science -- LICS'16. 623--632. Preprint available at ArXiv:1601.04520.

Digital Library

[10]

Manuel Bodirsky and Antoine Mottet. 2018. A Dichotomy for First-Order Reducts of Unary Structures. Logical Methods of Computer Science (2018). To appear.

[11]

Manuel Bodirsky and Jaroslav Nešetřil. 2006. Constraint Satisfaction with Countable Homogeneous Templates. Journal of Logic and Computation 16, 3 (2006), 359--373.

Digital Library

[12]

Manuel Bodirsky and Michael Pinsker. 2016. Canonical Functions: a Proof via Topological Dynamics. (2016). Preprint available under http://arxiv.org/abs/1610.09660.

[13]

Manuel Bodirsky, Michael Pinsker, and András Pongrácz. 2014. Projective clone homomorphisms. (2014). Preprint arXiv:1409.4601.

[14]

Andrei A. Bulatov. 2017. A dichotomy theorem for nonuniform CSPs. In Proceedings of FOCS 2017.

[15]

Andrei A. Bulatov and Peter Jeavons. 2001. Algebraic Structures in Combinatorial Problems. Technical report MATH-AL-4-2001, Technische Universität Dresden. (2001).

[16]

Andrei A. Bulatov, Andrei A. Krokhin, and Peter G. Jeavons. 2005. Classifying the complexity of constraints using finite algebras. SIAM J. Comput. 34 (2005), 720--742.

Digital Library

[17]

Ashok K. Chandra and Philip M. Merlin. 1977. Optimal Implementation of Conjunctive Queries in Relational Data Bases. In Proceedings of the Symposium on Theory of Computing (STOC). 77--90.

Digital Library

[18]

Gregory Cherlin, Saharon Shelah, and Niangdong Shi. 1999. Universal graphs with forbidden subgraphs and algebraic closure. Advances in Applied Mathematics 22 (1999), 454--491.

Digital Library

[19]

Tomás Feder and Moshe Y. Vardi. 1993. Monotone monadic SNP and constraint satisfaction. In Proceedings of the Symposium on Theory of Computing (STOC). 612--622.

Digital Library

[20]

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 (1999), 57--104.

Digital Library

[21]

J. Hubička and J. Nešetřil. 2016. All those Ramsey classes (Ramsey classes with closures and forbidden homomorphisms). (2016). arXiv:1606.07979v2.

[22]

Gábor Kun. 2013. Constraints, MMSNP, and Expander Relational Structures. Combinatorica 33, 3 (2013), 335--347.

Digital Library

[23]

Carsten Lutz and Frank Wolter. 2015. On the Relationship between Consistent Query Answering and Constraint Satisfaction Problems. In Proceedings of the 18th International Conference on Database Theory (ICDT15).

[24]

Florent Madelaine. 2003. Constraint satisfaction problems and related logic. PhD-thesis, University of Leicester. (2003).

[25]

Florent Madelaine and Iain A. Stewart. 2007. Constraint Satisfaction, Logic and Forbidden Patterns. SIAM J. Comput. 37, 1 (2007), 132--163.

Digital Library

[26]

Dmitriy Zhuk. 2017. The Proof of CSP Dichotomy Conjecture. In Proceedings of FOCS 2017.

Cited By

Mottet APinsker M(2024)Smooth approximations: An algebraic approach to CSPs over finitely bounded homogeneous structuresJournal of the ACM10.1145/368920771:5(1-47)Online publication date: 17-Aug-2024
https://dl.acm.org/doi/10.1145/3689207
Bodirsky MBodor B(2024)A Complexity Dichotomy in Spatial Reasoning via Ramsey TheoryACM Transactions on Computation Theory10.1145/3649445Online publication date: Mar-2024
https://doi.org/10.1145/3649445
Barsukov AKanté M(2024)Generalisations of Matrix Partitions: Complexity and ObstructionsTheoretical Computer Science10.1016/j.tcs.2024.114652(114652)Online publication date: May-2024
https://doi.org/10.1016/j.tcs.2024.114652
Show More Cited By

Recommendations

A Proof of the CSP Dichotomy Conjecture

Many natural combinatorial problems can be expressed as constraint satisfaction problems. This class of problems is known to be NP-complete in general, but certain restrictions on the form of the constraints can ensure tractability. The standard way to ...
A Proof of the Algebraic Tractability Conjecture for Monotone Monadic SNP

The logic MMSNP is a restricted fragment of existential second-order logic which can express many interesting queries in graph theory and finite model theory. The logic was introduced by Feder and Vardi, who showed that every MMSNP sentence is ...
Parameterized complexity dichotomy for Steiner Multicut

We consider the Steiner Multicut problem, which asks, given an undirected graph G, a collection T = { T 1 , ź , T t } , T i ź V ( G ) , of terminal sets of size at most p, and an integer k, whether there is a set S of at most k edges or nodes such that ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

LICS '18: Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science

July 2018

960 pages

ISBN:9781450355834

DOI:10.1145/3209108

Copyright © 2018 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGLOG: ACM Special Interest Group on Logic and Computation
EACSL: European Association for Computer Science Logic
IEEE-CS\DATC: IEEE Computer Society

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 09 July 2018

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article
Research
Refereed limited

Funding Sources

European Research Council

Conference

LICS '18

Sponsor:

SIGLOG
EACSL
IEEE-CS\DATC

LICS '18: 33rd Annual ACM/IEEE Symposium on Logic in Computer Science

July 9 - 12, 2018

Oxford, United Kingdom

Acceptance Rates

Overall Acceptance Rate 215 of 622 submissions, 35%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
116
Total Downloads

Downloads (Last 12 months)8
Downloads (Last 6 weeks)2

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Mottet APinsker M(2024)Smooth approximations: An algebraic approach to CSPs over finitely bounded homogeneous structuresJournal of the ACM10.1145/368920771:5(1-47)Online publication date: 17-Aug-2024
https://dl.acm.org/doi/10.1145/3689207
Bodirsky MBodor B(2024)A Complexity Dichotomy in Spatial Reasoning via Ramsey TheoryACM Transactions on Computation Theory10.1145/3649445Online publication date: Mar-2024
https://doi.org/10.1145/3649445
Barsukov AKanté M(2024)Generalisations of Matrix Partitions: Complexity and ObstructionsTheoretical Computer Science10.1016/j.tcs.2024.114652(114652)Online publication date: May-2024
https://doi.org/10.1016/j.tcs.2024.114652
Mottet APinsker M(2022)Smooth approximations and CSPs over finitely bounded homogeneous structuresProceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science10.1145/3531130.3533353(1-13)Online publication date: 2-Aug-2022
https://dl.acm.org/doi/10.1145/3531130.3533353
Baader FRydval J(2022)Using Model Theory to Find Decidable and Tractable Description Logics with Concrete DomainsJournal of Automated Reasoning10.1007/s10817-022-09626-266:3(357-407)Online publication date: 1-Aug-2022
https://dl.acm.org/doi/10.1007/s10817-022-09626-2
Bodirsky MBodor BGorla D(2021)Canonical polymorphisms of ramsey structures and the unique interpolation propertyProceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science10.1109/LICS52264.2021.9470683(1-13)Online publication date: 29-Jun-2021
https://dl.acm.org/doi/10.1109/LICS52264.2021.9470683
Barto LDeMeo WMottet AGorla D(2021)Constraint satisfaction problems over finite structuresProceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science10.1109/LICS52264.2021.9470670(1-13)Online publication date: 29-Jun-2021
https://dl.acm.org/doi/10.1109/LICS52264.2021.9470670
Baader FRydval J(2021)An Algebraic View on p-Admissible Concrete Domains for Lightweight Description LogicsLogics in Artificial Intelligence10.1007/978-3-030-75775-5_14(194-209)Online publication date: 17-May-2021
https://dl.acm.org/doi/10.1007/978-3-030-75775-5_14
Bodirsky MMottet AOlšák MOpršal JPinsker MWillard R(2020)𝜔-categorical structures avoiding height 1 identitiesTransactions of the American Mathematical Society10.1090/tran/8179374:1(327-350)Online publication date: 14-Oct-2020
https://doi.org/10.1090/tran/8179
Bodirsky MMottet AOlšák MOpršal JPinsker MWillard RBouyer P(2019)Topology is relevant (in a dichotomy conjecture for infinite-domain constraint satisfaction problems)Proceedings of the 34th Annual ACM/IEEE Symposium on Logic in Computer Science10.5555/3470152.3470212(1-12)Online publication date: 24-Jun-2019
https://dl.acm.org/doi/10.5555/3470152.3470212
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents