Back to Search Start Over

CSP dichotomy for special triads

Authors :
Libor Barto
Miklós Maróti
Todd Niven
Marcin Kozik
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).

Details

Database :
OpenAIRE
Journal :
ResearcherID
Accession number :
edsair.doi.dedup.....54348c06b7d1ec8b99e1d2fc15b92144
Full Text :
https://doi.org/10.26181/22200382.v1