iBet uBet web content aggregator. Adding the entire web to your favor.

Link to original content: https://doi.org/10.1145/1993636.1993724

Schaefer's theorem for graphs | Proceedings of the forty-third annual ACM symposium on Theory of computing

research-article

Free access

Schaefer's theorem for graphs

Authors:

Manuel Bodirsky,

Michael PinskerAuthors Info & Claims

STOC '11: Proceedings of the forty-third annual ACM symposium on Theory of computing

Pages 655 - 664

https://doi.org/10.1145/1993636.1993724

Published: 06 June 2011 Publication History

Abstract

Schaefer's theorem is a complexity classification result for so-called Boolean constraint satisfaction problems: it states that every Boolean constraint satisfaction problem is either contained in one out of six classes and can be solved in polynomial time, or is NP-complete. We present an analog of this dichotomy result for the propositional logic of graphs instead of Boolean logic. In this generalization of Schaefer's result, the input consists of a set W of variables and a conjunction Phi of statements ("constraints") about these variables in the language of graphs, where each statement is taken from a fixed finite set Psi of allowed quantifier-free first-order formulas; the question is whether Phi is satisfiable in a graph.

We prove that either Psi is contained in one out of 17 classes of graph formulas and the corresponding problem can be solved in polynomial time, or the problem is NP-complete. This is achieved by a universal-algebraic approach, which in turn allows us to use structural Ramsey theory. To apply the universal-algebraic approach, we formulate the computational problems under consideration as constraint satisfaction problems (CSPs) whose templates are first-order definable in the countably infinite random graph. Our method to classify the computational complexity of those CSPs produces many statements of independent mathematical interest.

Supplementary Material

JPG File (stoc_11a_1.jpg)

Download
20.22 KB

MP4 File (stoc_11a_1.mp4)

Download
81.68 MB

References

[1]

Fred G. Abramson and Leo Harrington. Models without indiscernibles. Journal of Symbolic Logic, 43(3):572--600, 1978.

[2]

Manuel Bodirsky. Constraint satisfaction problems with infinite templates. In Heribert Vollmer, editor, Complexity of Constraints (a collection of survey articles), pages 196--228. Springer, LNCS 5250, 2008.

Digital Library

[3]

Manuel Bodirsky, Hubie Chen, Jan Kára, and Timo von Oertzen. Maximal infinite-valued constraint languages. Theoretical Computer Science (TCS), 410:1684--1693, 2009. A preliminary version appeared at ICALP'07.

Digital Library

[4]

Manuel Bodirsky, Hubie Chen, and Michael Pinsker. The reducts of equality up to primitive positive interdefinability. Journal of Symbolic Logic, 75(4):1249--1292, 2010.

[5]

Manuel Bodirsky and Jan Kára. The complexity of equality constraint languages. Theory of Computing Systems, 3(2):136--158, 2008. A conference version appeared in the proceedings of CSR'06.

[6]

Manuel Bodirsky and Jan Kára. The complexity of temporal constraint satisfaction problems. Journal of the ACM, 57(2), 2009. An extended abstract appeared in the proceedings of STOC'08.

Digital Library

[7]

Manuel Bodirsky and Jan Kára. A fast algorithm and Datalog inexpressibility for temporal reasoning. ACM Transactions on Computational Logic, 11(3), 2010.

Digital Library

[8]

Manuel Bodirsky and Jaroslav Nesetril. Constraint satisfaction with countable homogeneous templates. Journal of Logic and Computation, 16(3):359--373, 2006.

Digital Library

[9]

Manuel Bodirsky and Michael Pinsker. Reducts of Ramsey structures. In Model Theoretic Methods in Finite Combinatorics, Contemporary mathematics. American Mathematical Society. To appear; preprint available from the authors' websites.

[10]

Manuel Bodirsky and Michael Pinsker. Minimal functions on the random graph. Preprint, arXiv:1003.4030, 2010.

[11]

Manuel Bodirsky and Michael Pinsker. Schaefer's theorem for graphs (full version). Preprint available from http://www.dmg.tuwien.ac.at/pinsker/, 2010.

Digital Library

[12]

Manuel Bodirsky, Michael Pinsker, and Todor Tsankov. Decidability of definability. In LICS'11, 2011. To appear. Preprint arXiv:1012.2381.

Digital Library

[13]

Andrei Bulatov, Andrei Krokhin, and Peter G. Jeavons. Classifying the complexity of constraints using finite algebras. SIAM Journal on Computing, 34:720--742, 2005.

Digital Library

[14]

Peter J. Cameron. The random graph. Algorithms and Combinatorics, 14:333--351, 1997.

[15]

Peter J. Cameron. The random graph revisited. In Proceedings of the European Congress of Mathematics, volume 201, pages 267--274. Birkhäuser, 2001.

[16]

David A. Cohen, Peter Jeavons, Peter Jonsson, and Manolis Koubarakis. Building tractable disjunctive constraints. Journal of the ACM, 47(5):826--853, 2000.

Digital Library

[17]

Ivo Duentsch. Relation algebras and their application in temporal and spatial reasoning. Artificial Intelligence Review, 23:315--357, 2005.

Digital Library

[18]

Wilfrid Hodges. Model theory. Cambridge University Press, 1993.

[19]

Peter Jeavons, David Cohen, and Marc Gyssens. Closure properties of constraints. Journal of the ACM, 44(4):527--548, 1997.

Digital Library

[20]

Jaroslav Nesetril. Ramsey theory. Handbook of Combinatorics, pages 1331--1403, 1995.

Digital Library

[21]

Jaroslav Nesetril and Vojtech Rödl. Ramsey classes of set systems. Journal of Combinatorial Theory, Series A, 34(2):183--201, 1983.

[22]

Thomas J. Schaefer. The complexity of satisfiability problems. In Proceedings of the Symposium on Theory of Computing (STOC), pages 216--226, 1978.

Digital Library

[23]

Mark H. Siggers. A strong Mal'cev condition for varieties omitting the unary type. Algebra universalis, 64(1):15--20, 2010.

[24]

Ágnes Szendrei. Clones in universal algebra. Séminaire de Mathématiques Supérieures. Les Presses de L'Université de Montréal, 1986.

[25]

Simon Thomas. Reducts of the random graph. Journal of Symbolic Logic, 56(1):176--181, 1991.

Digital Library

[26]

Simon Thomas. Reducts of random hypergraphs. Annals of Pure and Applied Logic, 80(2):165--193, 1996.

[27]

Matthias Westphal and Stefan Wölfl. Qualitative CSP, finite CSP, and SAT: Comparing methods for Qualitative Constraint-based Reasoning. In Proceedings of the 21th International Joint Conference on Artificial Intelligence (IJCAI), pages 628--633, 2009.

Digital Library

Cited By

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
Pech CPech M(2018)Polymorphism clones of homogeneous structures: gate coverings and automatic homeomorphicityAlgebra universalis10.1007/s00012-018-0504-179:2Online publication date: 20-Apr-2018
https://doi.org/10.1007/s00012-018-0504-1
Barto LKompatscher MOlšák MVan Pham TPinsker MAceto LIngólfsdóttir A(2017)The equivalence of two dichotomy conjectures for infinite domain constraint satisfaction problemsProceedings of the 32nd Annual ACM/IEEE Symposium on Logic in Computer Science10.5555/3329995.3330063(1-12)Online publication date: 20-Jun-2017
https://dl.acm.org/doi/10.5555/3329995.3330063
Show More Cited By

Index Terms

Schaefer's theorem for graphs
1. Theory of computation
  1. Randomness, geometry and discrete structures

Recommendations

Schaefer's Theorem for Graphs

Schaefer's theorem is a complexity classification result for so-called Boolean constraint satisfaction problems: it states that every Boolean constraint satisfaction problem is either contained in one out of six classes and can be solved in polynomial ...
Complexity of Approximating CSP with Balance / Hard Constraints

We study two natural extensions of Constraint Satisfaction Problems (CSPs). Balance-Max-CSP requires that in any feasible assignment each element in the domain is used an equal number of times. An instance of Hard-Max-CSP consists of soft constraints ...
(2 + epsilon)-Sat Is NP-Hard
FOCS '14: Proceedings of the 2014 IEEE 55th Annual Symposium on Foundations of Computer Science

We prove the following hardness result for anatural promise variant of the classical CNF-satisfiabilityproblem: Given a CNF-formula where each clause has widthw and the guarantee that there exists an assignment satisfyingat least g = [w/2]--1 literals ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '11: Proceedings of the forty-third annual ACM symposium on Theory of computing

June 2011

840 pages

ISBN:9781450306911

DOI:10.1145/1993636

General Chair:
Lance Fortnow
Northwestern University
,
Program Chair:
Salil Vadhan
Harvard University

Copyright © 2011 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 ACM 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

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 June 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

STOC'11

Sponsor:

SIGACT

STOC'11: Symposium on Theory of Computing

June 6 - 8, 2011

California, San Jose, USA

Acceptance Rates

STOC '11 Paper Acceptance Rate 84 of 304 submissions, 28%;

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
446
Total Downloads

Downloads (Last 12 months)61
Downloads (Last 6 weeks)3

Reflects downloads up to 23 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

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
Pech CPech M(2018)Polymorphism clones of homogeneous structures: gate coverings and automatic homeomorphicityAlgebra universalis10.1007/s00012-018-0504-179:2Online publication date: 20-Apr-2018
https://doi.org/10.1007/s00012-018-0504-1
Barto LKompatscher MOlšák MVan Pham TPinsker MAceto LIngólfsdóttir A(2017)The equivalence of two dichotomy conjectures for infinite domain constraint satisfaction problemsProceedings of the 32nd Annual ACM/IEEE Symposium on Logic in Computer Science10.5555/3329995.3330063(1-12)Online publication date: 20-Jun-2017
https://dl.acm.org/doi/10.5555/3329995.3330063
Barto LKompatscher MOlsak MPham TPinsker M(2017)The equivalence of two dichotomy conjectures for infinite domain constraint satisfaction problems2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)10.1109/LICS.2017.8005128(1-12)Online publication date: Jun-2017
https://doi.org/10.1109/LICS.2017.8005128
Bodirsky MMottet AKoskinen EGrohe MShankar N(2016)Reducts of finitely bounded homogeneous structures, and lifting tractability from finite-domain constraint satisfactionProceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science10.1145/2933575.2934515(623-632)Online publication date: 5-Jul-2016
https://dl.acm.org/doi/10.1145/2933575.2934515
Glaßer CJonsson PMartin B(2016)Circuit Satisfiability and Constraint Satisfaction Around Skolem ArithmeticPursuit of the Universal10.1007/978-3-319-40189-8_33(323-332)Online publication date: 14-Jun-2016
https://doi.org/10.1007/978-3-319-40189-8_33
Bodirsky MPinsker M(2015)Schaefer's Theorem for GraphsJournal of the ACM10.1145/276489962:3(1-52)Online publication date: 30-Jun-2015
https://dl.acm.org/doi/10.1145/2764899
Klin BKopczynski EOchremiak JTorunczyk S(2015)Locally Finite Constraint Satisfaction ProblemsProceedings of the 2015 30th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)10.1109/LICS.2015.51(475-486)Online publication date: 6-Jul-2015
https://dl.acm.org/doi/10.1109/LICS.2015.51
Bodirsky MMartin BMottet A(2015)Constraint Satisfaction Problems over the Integers with SuccessorAutomata, Languages, and Programming10.1007/978-3-662-47672-7_21(256-267)Online publication date: 20-Jun-2015
https://doi.org/10.1007/978-3-662-47672-7_21

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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

Media

Figures

Other

Tables

View Table of Contents