Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

 

 

CSP dichotomy for special triads


Authors: Libor Barto, Marcin Kozik, Miklós Maróti and Todd Niven
Journal: Proc. Amer. Math. Soc. 137 (2009), 2921-2934
MSC (2000): Primary 05C85
Published electronically: April 2, 2009
MathSciNet review: 2506450
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: For a fixed digraph $ \mathbb{G}$, the Constraint Satisfaction Problem with the template $ \mathbb{G}$, or $ \mathrm{CSP}(\mathbb{G})$ for short, is the problem of deciding whether a given input digraph $ \mathbb{H}$ admits a homomorphism to $ \mathbb{G}$. The dichotomy conjecture of Feder and Vardi states that $ \mathrm{CSP}(\mathbb{G})$, for any choice of $ \mathbb{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 $ \mathrm{CSP}(\mathbb{G})$.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2000): 05C85

Retrieve articles in all journals with MSC (2000): 05C85


Additional Information

Libor Barto
Affiliation: Department of Algebra, Charles University, Prague, Czech Republic
Email: libor.barto@gmail.com

Marcin Kozik
Affiliation: Department of Theoretical Computer Science, Jagiellonian University, Krakow, Poland – and – Eduard Čech Center, Prague, Czech Republic
Email: kozik@tcs.uj.edu.pl

Miklós Maróti
Affiliation: Bolyai Institute, University of Szeged, Szeged, Hungary
Email: mmaroti@math.u-szeged.hu

Todd Niven
Affiliation: Eduard Čech Center, Prague, Czech Republic
Email: niven@karlin.mff.cuni.cz

DOI: https://doi.org/10.1090/S0002-9939-09-09883-9
Keywords: Graph coloring, constraint satisfaction problem, triad
Received by editor(s): October 14, 2008
Received by editor(s) in revised form: January 5, 2009
Published electronically: April 2, 2009
Additional Notes: The first author was supported by the Grant Agency of the Czech Republic under grant Nos. 201/06/0664 and 201/09/P223, and by the project of the Ministry of Education under grant No. MSM 0021620839.
The second and fourth authors were supported by the Eduard Čech Center grant No. LC505
The third author was partially supported by the Hungarian National Foundation for Scientific Research (OTKA), grant Nos. T 48809 and K 60148.
Communicated by: Jim Haglund
Article copyright: © Copyright 2009 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.