The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell)
From MaRDI portal
Publication:3642864
DOI10.1137/070708093zbMath1191.68460OpenAlexW1984074081WikidataQ122949801 ScholiaQ122949801MaRDI QIDQ3642864
Marcin Kozik, Todd Niven, Libor Barto
Publication date: 6 November 2009
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/310c1cb4d781602906a97e1c515bdf13c9cf8aec
Graph theory (including graph drawing) in computer science (68R10) Applications of universal algebra in computer science (08A70)
Related Items
Quantified Constraint Satisfaction Problem on Semicomplete Digraphs ⋮ Tractability in constraint satisfaction problems: a survey ⋮ The Complexity of General-Valued CSPs ⋮ Hard constraint satisfaction problems have hard gaps at location 1 ⋮ Oriented incidence colourings of digraphs ⋮ On Planar Boolean CSP ⋮ A Galois Connection for Valued Constraint Languages of Infinite Size ⋮ On the Complexity of the Model Checking Problem ⋮ Complexity and polymorphisms for digraph constraint problems under some basic constructions ⋮ Necessary Conditions for Tractability of Valued CSPs ⋮ Circuit Satisfiability and Constraint Satisfaction Around Skolem Arithmetic ⋮ The Complexity of Counting Quantifiers on Equality Languages ⋮ Axiomatisability and hardness for universal Horn classes of hypergraphs ⋮ A complexity dichotomy for signed \(\mathbf{H}\)-colouring ⋮ Deciding absorption in relational structures ⋮ Analogues of cliques for \((m,n)\)-colored mixed graphs ⋮ Circuit satisfiability and constraint satisfaction around Skolem arithmetic ⋮ The Complexity of Approximately Counting Tree Homomorphisms ⋮ Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy ⋮ A strong Mal'cev condition for locally finite varieties omitting the unary type ⋮ Cyclic terms for \(\text{SD}_{\vee}\) varieties revisited ⋮ On the complexity of \(\mathbb{H}\)-coloring for special oriented trees ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The smallest hard trees ⋮ A new line of attack on the dichotomy conjecture ⋮ \((\mathbb{Z},\mathrm{succ},U)\), \((\mathbb{Z},E,U)\), and their CSP's ⋮ Enumerating homomorphisms ⋮ Low-level dichotomy for quantified constraint satisfaction problems ⋮ Colouring, constraint satisfaction, and complexity ⋮ Quantified Constraints in Twenty Seventeen ⋮ The structure of polynomial operations associated with smooth digraphs. ⋮ On the restricted homomorphism problem ⋮ The complexity of counting quantifiers on equality languages ⋮ Rigid binary relations on a 4-element domain ⋮ Gap theorems for robust satisfiability: Boolean CSPs and beyond ⋮ The complexity of the list homomorphism problem for graphs ⋮ The complexity of tropical graph homomorphisms ⋮ The complexity of colouring by locally semicomplete digraphs ⋮ Constraint satisfaction problems over semilattice block Mal'tsev algebras ⋮ Constraint Satisfaction with Counting Quantifiers ⋮ Graph partitions with prescribed patterns ⋮ Optimal strong Mal'cev conditions for omitting type 1 in locally finite varieties. ⋮ Dichotomy for finite tournaments of mixed-type ⋮ Smooth digraphs modulo primitive positive constructability and cyclic loop conditions ⋮ Loop conditions for strongly connected digraphs ⋮ The local loop lemma ⋮ Topology Is Irrelevant (In a Dichotomy Conjecture for Infinite Domain Constraint Satisfaction Problems) ⋮ Testing the Complexity of a Valued CSP Language ⋮ CSP dichotomy for special triads ⋮ Decidable Relationships between Consistency Notions for Constraint Satisfaction Problems ⋮ Constraint Satisfaction Problems for Reducts of Homogeneous Graphs ⋮ A combinatorial constraint satisfaction problem dichotomy classification conjecture ⋮ Congruence modularity implies cyclic terms for finite algebras ⋮ CSP DICHOTOMY FOR SPECIAL POLYADS ⋮ The Power of Linear Programming for General-Valued CSPs ⋮ Unnamed Item ⋮ Characterizations of several Maltsev conditions. ⋮ The Complexity of General-Valued Constraint Satisfaction Problems Seen from the Other Side
