Algebra and the complexity of digraph CSPs: a survey
From MaRDI portal
Publication:4993603
DOI10.4230/DFU.VOL7.15301.267zbMATH Open1482.68166OpenAlexW2591988591MaRDI QIDQ4993603FDOQ4993603
Authors: Benoît Larose 
Publication date: 15 June 2021
Full work available at URL: https://dblp.uni-trier.de/db/conf/dagstuhl/dfu7.html#Larose17
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
Directed graphs (digraphs), tournaments (05C20) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Applications of universal algebra in computer science (08A70) Computational aspects of satisfiability (68R07)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Existence theorems for weakly symmetric operations
- On the complexity of H-coloring
- Varieties with few subalgebras of powers
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- Classifying the Complexity of Constraints Using Finite Algebras
- Recent Results on the Algebraic Approach to the CSP
- Constraints, consistency and closure
- On the algebraic structure of combinatorial problems
- Characterizations of several Maltsev conditions.
- CSP for binary conservative relational structures
- Complexity of conservative constraint satisfaction problems
- The structure of finite algebras
- Title not available (Why is that?)
- Tractability and learnability arising from algebras with few subpowers
- A Characterisation of First-Order Constraint Satisfaction Problems
- Dualities for Constraint Satisfaction Problems
- The Complexity of the Extendibility Problem for Finite Posets
- Maltsev digraphs have a majority polymorphism
- \(H\)-coloring dichotomy revisited
- Reflexive digraphs with near unanimity polymorphisms
- Maltsev families of varieties closed under join or Maltsev product
- Bounded width problems and algebras
- Universal algebra and hardness results for constraint satisfaction problems
- The complexity of the list homomorphism problem for graphs
- List homomorphisms to reflexive graphs
- Near-Unanimity Functions and Varieties of Reflexive Graphs
- Bi‐arc graphs and the complexity of list homomorphisms
- Duality theorems for finite structures (characterising gaps and good characterisations)
- Polynomial graph-colorings
- Computing and Combinatorics
- A polynomial-time algorithm for near-unanimity graphs
- Graphs admitting \(k\)-NU operations. II: The irreflexive case
- List-homomorphism problems on graphs and arc consistency
- The dichotomy of list homomorphisms for digraphs
- Title not available (Why is that?)
- Algebraic properties and dismantlability of finite posets
- Reflexive graphs with near unanimity but no semilattice polymorphisms
- Retractions to Pseudoforests
- A finer reduction of constraint problems to digraphs
- Monotone clones, residual smallness and congruence distributivity
- Distributive lattice polymorphisms on reflexive graphs
- NU polymorphisms on reflexive digraphs
- Complexity of tree homomorphisms
- Retractions onto series-parallel posets
- Finite posets and topological spaces in locally finite varieties
- Classification of homomorphisms to oriented cycles and of \(k\)-partite satisfiability
- List homomorphisms of graphs with bounded degrees
- Polymorphisms of small digraphs
- Descriptive complexity of list H-coloring problems in logspace: a refined dichotomy
- Complexity and polymorphisms for digraph constraint problems under some basic constructions
- Near unanimity constraints have bounded pathwidth duality
- The Existence of Homomorphisms to Oriented Cycles
- A new line of attack on the dichotomy conjecture
- A discrete homotopy theory for binary reflexive structures
- Absolute retracts and varieties generated by chordal graphs
- A quasi-Mal'cev condition with unexpected application.
- Dichotomy for finite tournaments of mixed-type
- Projection properties and reflexive binary relations
- Asking the Metaquestions in Constraint Tractability
- Two new homomorphism dualities and lattice operations
- Semilattice polymorphisms and chordal graphs
- Graphs admitting \(k\)-NU operations. I: The reflexive case
- Space complexity of list H-colouring: a dichotomy
- Decidability of absorption in relational structures of bounded width.
- Monotone proper interval digraphs and Min-Max orderings
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
- The complexity of valued CSPs
- Reflexive graphs with near unanimity but no semilattice polymorphisms
- 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)
