Back to Search
Start Over
CSP dichotomy for special triads
- Source :
- ResearcherID
- Publication Year :
- 2023
- Publisher :
- La Trobe, 2023.
-
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).
- 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
Subjects
Details
- Database :
- OpenAIRE
- Journal :
- ResearcherID
- Accession number :
- edsair.doi.dedup.....54348c06b7d1ec8b99e1d2fc15b92144
- Full Text :
- https://doi.org/10.26181/22200382.v1