Constraint Satisfaction Problems for Reducts of Homogeneous Graphs

DOI10.1137/16M1082974zbMath1430.68121WikidataQ127455221 ScholiaQ127455221MaRDI QIDQ5232325

Barnaby Martin, András Pongrácz, Michael Pinsker, Manuel Bodirsky

Publication date: 2 September 2019

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

computational complexityconstraint satisfaction problemshomogeneous structuresuniversal algebrastructural Ramsey theoryfirst-order reducts

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Applications of universal algebra in computer science (08A70) Structural characterization of families of graphs (05C75) Generalized Ramsey theory (05C55) Model theory of denumerable and separable structures (03C15)

Related Items

When Symmetries Are Not Enough: A Hierarchy of Hard Constraint Satisfaction Problems, Hardness of Network Satisfaction for Relation Algebras with Normal Representations, \((\mathbb{Z},\mathrm{succ},U)\), \((\mathbb{Z},E,U)\), and their CSP's, 𝜔-categorical structures avoiding height 1 identities, Unnamed Item, Unnamed Item, Homomorphism order of connected monounary algebras, Pseudo‐loop conditions, PROJECTIVE CLONE HOMOMORPHISMS, Using model theory to find decidable and tractable description logics with concrete domains, Unnamed Item, The Complexity of Network Satisfaction Problems for Symmetric Relation Algebras with a Flexible Atom

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Reducts of the Henson graphs with a constant
• The complexity of equality constraint languages
• A survey of clones on infinite sets
• Maximal infinite-valued constraint languages
• On the complexity of H-coloring
• The partite construction and Ramsey set systems
• Minimal functions on the random graph
• Fraïssé limits, Ramsey theory, and topological dynamics of automorphism groups
• Complexity Classifications of Boolean Constraint Satisfaction Problems
• Schaefer's Theorem for Graphs
• Reducts of Ramsey structures
• Constraint Satisfaction with Countable Homogeneous Templates
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• The complexity of temporal constraint satisfaction problems
• The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell)
• Countable Ultrahomogeneous Undirected Graphs
• Reducts of the random graph
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Finite Clones Containing All Permutations
• Closure properties of constraints
• Discrete Temporal Constraint Satisfaction Problems
• The algebraic dichotomy conjecture for infinite domain Constraint Satisfaction Problems
• Reducts of finitely bounded homogeneous structures, and lifting tractability from finite-domain constraint satisfaction
• PROJECTIVE CLONE HOMOMORPHISMS
• Topology Is Irrelevant (In a Dichotomy Conjecture for Infinite Domain Constraint Satisfaction Problems)
• Cores of Countably Categorical Structures
• Classifying the Complexity of Constraints Using Finite Algebras
• The Complexity of Phylogeny Constraint Satisfaction Problems
• The complexity of satisfiability problems
• Decidability of Definability
• Topological Birkhoff
• The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)