1. CSP dichotomy for special triads
- Author
-
Libor Barto, Miklós Maróti, Todd Niven, and Marcin Kozik
- Subjects
Discrete mathematics ,Conjecture ,triad ,Applied Mathematics ,General Mathematics ,Digraph ,Directed graph ,Computer Science::Computational Complexity ,Combinatorics ,TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY ,graph coloring ,Homomorphism ,Graph coloring ,Tree (set theory) ,constraint satisfaction problem ,Time complexity ,Constraint satisfaction problem ,MathematicsofComputing_DISCRETEMATHEMATICS ,Mathematics - Abstract
For a fixed digraph G, the Constraint Satisfaction Problem with the template G, or CSP(G) for short, is the problem of deciding whether a given input digraph H admits a homomorphism to G. The dichotomy conjecture of Feder and Vardi states that CSP(G), for any choice of G, is solvable in polynomial time or NP-complete. This paper confirms the conjecture for a class of oriented trees called special triads. As a corollary we get the smallest known example of an oriented tree (with 33 vertices) defining an NP-complete CSP(G).
- Published
- 2023
- Full Text
- View/download PDF