Algebra and the complexity of digraph CSPs: a survey
From MaRDI portal
Publication:4993603
Recommendations
- The complexity of constraint satisfaction: an algebraic approach
- Complexity of the counting constraint satisfaction problem
- scientific article; zbMATH DE number 1670830
- Constraint satisfaction problems: complexity and algorithms
- Complexity and polymorphisms for digraph constraint problems under some basic constructions
Cites work
- scientific article; zbMATH DE number 610968 (Why is no real title available?)
- scientific article; zbMATH DE number 1487982 (Why is no real title available?)
- scientific article; zbMATH DE number 2117181 (Why is no real title available?)
- scientific article; zbMATH DE number 5030273 (Why is no real title available?)
- A Characterisation of First-Order Constraint Satisfaction Problems
- A discrete homotopy theory for binary reflexive structures
- A finer reduction of constraint problems to digraphs
- A new line of attack on the dichotomy conjecture
- A polynomial-time algorithm for near-unanimity graphs
- A quasi-Mal'cev condition with unexpected application.
- Absolute retracts and varieties generated by chordal graphs
- Algebraic properties and dismantlability of finite posets
- Asking the Metaquestions in Constraint Tractability
- Bi‐arc graphs and the complexity of list homomorphisms
- Bounded width problems and algebras
- CSP for binary conservative relational structures
- Characterizations of several Maltsev conditions.
- Classification of homomorphisms to oriented cycles and of \(k\)-partite satisfiability
- Classifying the Complexity of Constraints Using Finite Algebras
- Complexity and polymorphisms for digraph constraint problems under some basic constructions
- Complexity of conservative constraint satisfaction problems
- Complexity of tree homomorphisms
- Computing and Combinatorics
- Constraints, consistency and closure
- Decidability of absorption in relational structures of bounded width.
- Descriptive complexity of list H-coloring problems in logspace: a refined dichotomy
- Dichotomy for finite tournaments of mixed-type
- Distributive lattice polymorphisms on reflexive graphs
- Dualities for Constraint Satisfaction Problems
- Duality theorems for finite structures (characterising gaps and good characterisations)
- Existence theorems for weakly symmetric operations
- Finite posets and topological spaces in locally finite varieties
- Graphs admitting \(k\)-NU operations. I: The reflexive case
- Graphs admitting \(k\)-NU operations. II: The irreflexive case
- List homomorphisms of graphs with bounded degrees
- List homomorphisms to reflexive graphs
- List-homomorphism problems on graphs and arc consistency
- Maltsev digraphs have a majority polymorphism
- Maltsev families of varieties closed under join or Maltsev product
- Monotone clones, residual smallness and congruence distributivity
- Monotone proper interval digraphs and Min-Max orderings
- NU polymorphisms on reflexive digraphs
- Near unanimity constraints have bounded pathwidth duality
- Near-Unanimity Functions and Varieties of Reflexive Graphs
- On the algebraic structure of combinatorial problems
- On the complexity of H-coloring
- Polymorphisms of small digraphs
- Polynomial graph-colorings
- Projection properties and reflexive binary relations
- Recent Results on the Algebraic Approach to the CSP
- Reflexive digraphs with near unanimity polymorphisms
- Reflexive graphs with near unanimity but no semilattice polymorphisms
- Retractions onto series-parallel posets
- Retractions to Pseudoforests
- Semilattice polymorphisms and chordal graphs
- Space complexity of list H-colouring: a dichotomy
- The Complexity of the Extendibility Problem for Finite Posets
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- The Existence of Homomorphisms to Oriented Cycles
- The complexity of the list homomorphism problem for graphs
- The dichotomy of list homomorphisms for digraphs
- The structure of finite algebras
- Tractability and learnability arising from algebras with few subpowers
- Two new homomorphism dualities and lattice operations
- Universal algebra and hardness results for constraint satisfaction problems
- Varieties with few subalgebras of powers
- H-coloring dichotomy revisited
Cited in
(9)- Surjective \texttt{H}-colouring over reflexive digraphs
- On the computational complexity of non-dictatorial aggregation
- The complexity of constraint satisfaction: an algebraic approach
- Surjective polymorphisms of directed reflexive cycles
- Polymorphisms of small digraphs
- Reflexive graphs with near unanimity but no semilattice polymorphisms
- The complexity of valued CSPs
- On the complexity of \(\mathbb{H}\)-coloring for special oriented trees
- Complexity and polymorphisms for digraph constraint problems under some basic constructions
This page was built for publication: Algebra and the complexity of digraph CSPs: a survey
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4993603)
