Algebra and the Complexity of Digraph CSPs: a Survey
From MaRDI portal
Publication:4993603
DOI10.4230/DFU.Vol7.15301.267zbMath1482.68166OpenAlexW2591988591MaRDI QIDQ4993603
Publication date: 15 June 2021
Full work available at URL: https://dblp.uni-trier.de/db/conf/dagstuhl/dfu7.html#Larose17
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Applications of universal algebra in computer science (08A70) Directed graphs (digraphs), tournaments (05C20) Computational aspects of satisfiability (68R07)
Related Items
Unnamed Item, On the complexity of \(\mathbb{H}\)-coloring for special oriented trees, Surjective polymorphisms of directed reflexive cycles, The Complexity of Valued CSPs, On the Computational Complexity of Non-Dictatorial Aggregation, Reflexive graphs with near unanimity but no semilattice polymorphisms
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- List-homomorphism problems on graphs and arc consistency
- Reflexive digraphs with near unanimity polymorphisms
- Maltsev families of varieties closed under join or Maltsev product
- Maltsev digraphs have a majority polymorphism
- The complexity of the list homomorphism problem for graphs
- \(H\)-coloring dichotomy revisited
- List homomorphisms of graphs with bounded degrees
- A new line of attack on the dichotomy conjecture
- Absolute retracts and varieties generated by chordal graphs
- Bounded width problems and algebras
- Existence theorems for weakly symmetric operations
- Universal algebra and hardness results for constraint satisfaction problems
- On the complexity of H-coloring
- List homomorphisms to reflexive graphs
- Polynomial graph-colorings
- Constraints, consistency and closure
- On the algebraic structure of combinatorial problems
- Algebraic properties and dismantlability of finite posets
- A discrete homotopy theory for binary reflexive structures
- Duality theorems for finite structures (characterising gaps and good characterisations)
- Complexity of tree homomorphisms
- Reflexive graphs with near unanimity but no semilattice polymorphisms
- Characterizations of several Maltsev conditions.
- A quasi-Mal'cev condition with unexpected application.
- Semilattice polymorphisms and chordal graphs
- Retractions onto series-parallel posets
- Decidability of absorption in relational structures of bounded width.
- Dichotomy for finite tournaments of mixed-type
- Finite posets and topological spaces in locally finite varieties
- CSP for binary conservative relational structures
- Classification of Homomorphisms to Oriented Cycles and of k-Partite Satisfiability
- Complexity of conservative constraint satisfaction problems
- Near Unanimity Constraints Have Bounded Pathwidth Duality
- A polynomial-time algorithm for near-unanimity graphs
- Retractions to Pseudoforests
- Two new homomorphism dualities and lattice operations
- Graphs Admitting $k$-NU Operations. Part 2: The Irreflexive Case
- Near-Unanimity Functions and Varieties of Reflexive Graphs
- A finer reduction of constraint problems to digraphs
- Monotone clones, residual smallness and congruence distributivity
- Varieties with few subalgebras of powers
- The structure of finite algebras
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- The Complexity of the Extendibility Problem for Finite Posets
- Distributive Lattice Polymorphism on Reflexive Graphs
- NU Polymorphisms on Reflexive Digraphs
- Descriptive Complexity of List H-Coloring Problems in Logspace: A Refined Dichotomy
- Computing and Combinatorics
- Bi‐arc graphs and the complexity of list homomorphisms
- The Existence of Homomorphisms to Oriented Cycles
- Monotone Proper Interval Digraphs and Min-Max Orderings
- Asking the Metaquestions in Constraint Tractability
- Complexity and polymorphisms for digraph constraint problems under some basic constructions
- Classifying the Complexity of Constraints Using Finite Algebras
- Space complexity of list H-colouring: a dichotomy
- Tractability and Learnability Arising from Algebras with Few Subpowers
- Graphs Admitting $k$-NU Operations. Part 1: The Reflexive Case
- A Characterisation of First-Order Constraint Satisfaction Problems
- Recent Results on the Algebraic Approach to the CSP
- Dualities for Constraint Satisfaction Problems
- Projection properties and reflexive binary relations
