Schaefer's Theorem for Graphs

DOI10.1145/2764899zbMath1333.05194arXiv1011.2894OpenAlexW2243954424WikidataQ56168969 ScholiaQ56168969MaRDI QIDQ2796406

Michael Pinsker, Manuel Bodirsky

Publication date: 24 March 2016

Published in: Journal of the ACM, Proceedings of the forty-third annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1011.2894

zbMATH Keywords

Ramsey theorymodel theoryconstraint satisfactionconstraint satisfaction problemscomputational logichomogeneous structuresuniversal algebracomplexity dichotomypolymorphismscountable random graphramsey theory

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Logic in computer science (03B70) Applications of universal algebra in computer science (08A70) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Generalized Ramsey theory (05C55)

Related Items

Constraint Satisfaction Problems over the Integers with Successor, Circuit Satisfiability and Constraint Satisfaction Around Skolem Arithmetic, When Symmetries Are Not Enough: A Hierarchy of Hard Constraint Satisfaction Problems, Polymorphism clones of homogeneous structures: gate coverings and automatic homeomorphicity, Circuit satisfiability and constraint satisfaction around Skolem arithmetic, Permutation monoids and MB-homogeneity for graphs and relational structures, The complete set of minimal simple graphs that support unsatisfiable 2-CNFs, \((\mathbb{Z},\mathrm{succ},U)\), \((\mathbb{Z},E,U)\), and their CSP's, Reconstructing the topology of clones, Unnamed Item, The wonderland of reflections, Reducts of the random partial order, Quantified Constraints in Twenty Seventeen, 𝜔-categorical structures avoiding height 1 identities, Permutations on the random permutation, Reducts of the Henson graphs with a constant, Minimal functions on the random graph, Unnamed Item, Unnamed Item, Schaefer's Theorem for Graphs, Permutation groups with small orbit growth, Equations in oligomorphic clones and the constraint satisfaction problem for ω-categorical structures, Topology Is Irrelevant (In a Dichotomy Conjecture for Infinite Domain Constraint Satisfaction Problems), Constraint Satisfaction Problems for Reducts of Homogeneous Graphs, Time Complexity of Constraint Satisfaction via Universal Algebra, A Dichotomy for First-Order Reducts of Unary Structures, PROJECTIVE CLONE HOMOMORPHISMS, Unnamed Item, The Complexity of Network Satisfaction Problems for Symmetric Relation Algebras with a Flexible Atom, Distance constraint satisfaction problems

Cites Work

• Unnamed Item
• Unnamed Item
• The complexity of equality constraint languages
• A survey of clones on infinite sets
• Maximal infinite-valued constraint languages
• Relation algebras and their application in temporal and spatial reasoning
• Reducts of random hypergraphs
• Minimal functions on the random graph
• Schaefer's Theorem for Graphs
• Horn versus full first-order: Complexity dichotomies in algebraic constraint satisfaction
• A fast algorithm and datalog inexpressibility for temporal reasoning
• Building tractable disjunctive constraints
• The reducts of equality up to primitive positive interdefinability
• Reducts of Ramsey structures
• Constraint Satisfaction with Countable Homogeneous Templates
• A lower bound for r(5, 5)
• Reducts of the random graph
• `` Strong NP-Completeness Results
• Models Without Indiscernibles
• Closure properties of constraints
• Classifying the Complexity of Constraints Using Finite Algebras
• The complexity of satisfiability problems
• Decidability of Definability
• Topological Birkhoff
• The random graph