A new line of attack on the dichotomy conjecture
From MaRDI portal
Publication:896081
DOI10.1016/j.ejc.2015.07.011zbMath1327.05183WikidataQ122872422 ScholiaQ122872422MaRDI QIDQ896081
Publication date: 11 December 2015
Published in: European Journal of Combinatorics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ejc.2015.07.011
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C40: Connectivity
Related Items
Unnamed Item, Unnamed Item, Algebra and the Complexity of Digraph CSPs: a Survey, The Power of Sherali--Adams Relaxations for General-Valued CSPs, CLAP: A New Algorithm for Promise CSPs, Unnamed Item, Towards a characterization of constant-factor approximable finite-valued CSPs, On algebras with many symmetric operations, Unnamed Item, Nonnegative Weighted #CSP: An Effective Complexity Dichotomy
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Colouring, constraint satisfaction, and complexity
- Unary polynomials in algebras. I
- \(H\)-coloring dichotomy revisited
- Towards a dichotomy theorem for the counting constraint satisfaction problem
- Bounded width problems and algebras
- Existence theorems for weakly symmetric operations
- A combinatorial constraint satisfaction problem dichotomy classification conjecture
- On the complexity of H-coloring
- Constraints, consistency and closure
- On the algebraic structure of combinatorial problems
- Conjunctive-query containment and constraint satisfaction
- Duality theorems for finite structures (characterising gaps and good characterisations)
- Independent sets in graph powers are almost contained in juntas
- Generalised dualities and maximal finite antichains in the homomorphism order of relational structures
- Forbidden lifts (NP and CSP for combinatorialists)
- Constraints, MMSNP and expander relational structures
- Linear programming, width-1 CSPs, and robust satisfaction
- Robust Satisfiability for CSPs
- OMITTING TYPES, BOUNDED WIDTH AND THE ABILITY TO COUNT
- Constraint Satisfaction with Countable Homogeneous Templates
- Quantified Constraint Satisfaction and the Polynomially Generated Powers Property
- A dichotomy theorem for constraint satisfaction problems on a 3-element set
- A Subalgebra Intersection Property for Congruence Distributive Varieties
- The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell)
- The structure of finite algebras
- On the Structure of Polynomial Time Reducibility
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- An Easy Way to Minimal Algebras
- Closure properties of constraints
- Duality and Polynomial Testing of Tree Homomorphisms
- Constraint Satisfaction Problems of Bounded Width
- The complexity of satisfiability problems
- Robust satisfiability of constraint satisfaction problems
- A Simple Algorithm for Mal'tsev Constraints
- The PCP theorem by gap amplification
- Idempotent totally symmetric operations on finite posets
