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 , the Constraint Satisfaction Problem with the template , or for short, is the problem of deciding whether a given input digraph admits a homomorphism to . The dichotomy conjecture of Feder and Vardi states that , for any choice of , 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 vertices) defining an NP-complete .

**[BJH90]**Jørgen Bang-Jensen and Pavol Hell,*The effect of two cycles on the complexity of colourings by directed graphs*, Discrete Appl. Math.**26**(1990), no. 1, 1–23. MR**1028872**, 10.1016/0166-218X(90)90017-7**[BJK05]**Andrei Bulatov, Peter Jeavons, and Andrei Krokhin,*Classifying the complexity of constraints using finite algebras*, SIAM J. Comput.**34**(2005), no. 3, 720–742. MR**2137072**, 10.1137/S0097539700376676**[BKJ00]**Andrei A. Bulatov, Andrei A. Krokhin, and Peter Jeavons,*Constraint satisfaction problems and finite algebras*, Automata, languages and programming (Geneva, 2000) Lecture Notes in Comput. Sci., vol. 1853, Springer, Berlin, 2000, pp. 272–282. MR**1795899**, 10.1007/3-540-45022-X_24**[BKN08a]**Libor Barto, Marcin Kozik, and Todd Niven,*The CSP dichotomy holds for digraphs with no sources and no sinks (a positive answer to a conjecture of Bang-Jensen and Hell)*, SIAM Journal on Computing**38**(2009), no. 5, 1782-1802.**[BKN08b]**-,*Polymorphisms and the complexity of homomorphism problems*, Proceedings of the 40th ACM Symposium on Theory of Computing, STOC'08, 2008.**[DP99]**Victor Dalmau and Justin Pearson,*Closure functions and width problems*, Fifth International Conference on Principles and Practice of Constraint Programming (CP'99), 1999, Lecture Notes in Computer Science, vol. 1713, Springer-Verlag, 2004, pp. 159-173.**[Fed01]**Tomás Feder,*Classification of homomorphisms to oriented cycles and of 𝑘-partite satisfiability*, SIAM J. Discrete Math.**14**(2001), no. 4, 471–480 (electronic). MR**1861785**, 10.1137/S0895480199383353**[FV99]**Tomás Feder and Moshe Y. Vardi,*The computational structure of monotone monadic SNP and constraint satisfaction: a study through Datalog and group theory*, SIAM J. Comput.**28**(1999), no. 1, 57–104 (electronic). MR**1630445**, 10.1137/S0097539794266766**[Gut91]**W. Gutjahr,*Graph colourings*, Ph.D. Thesis, Free University Berlin, 1991.**[GWW92]**Wolfgang Gutjahr, Emo Welzl, and Gerhard Woeginger,*Polynomial graph-colorings*, Discrete Appl. Math.**35**(1992), no. 1, 29–45. MR**1138082**, 10.1016/0166-218X(92)90294-K**[HHMNL88]**R. Häggkvist, P. Hell, D. J. Miller, and V. Neumann Lara,*On multiplicative graphs and the product conjecture*, Combinatorica**8**(1988), no. 1, 63–74. MR**951994**, 10.1007/BF02122553**[HN90]**Pavol Hell and Jaroslav Nešetřil,*On the complexity of 𝐻-coloring*, J. Combin. Theory Ser. B**48**(1990), no. 1, 92–110. MR**1047555**, 10.1016/0095-8956(90)90132-J**[HN04]**Pavol Hell and Jaroslav Nešetřil,*Graphs and homomorphisms*, Oxford Lecture Series in Mathematics and its Applications, vol. 28, Oxford University Press, Oxford, 2004. MR**2089014****[HNZ96a]**P. Hell, J. Nešetřil, and X. Zhu,*Complexity of tree homomorphisms*, Discrete Appl. Math.**70**(1996), no. 1, 23–36. MR**1402736**, 10.1016/0166-218X(96)00099-6**[HNZ96b]**P. Hell, J. Nešetřil, and X. Zhu,*Duality and polynomial testing of tree homomorphisms*, Trans. Amer. Math. Soc.**348**(1996), no. 4, 1281–1297. MR**1333391**, 10.1090/S0002-9947-96-01537-1**[JCG97]**Peter Jeavons, David Cohen, and Marc Gyssens,*Closure properties of constraints*, J. ACM**44**(1997), no. 4, 527–548. MR**1481313**, 10.1145/263867.263489**[KBJ05]**Andrei Krokhin, Andrei Bulatov, and Peter Jeavons,*The complexity of constraint satisfaction: an algebraic approach*, Structural theory of automata, semigroups, and universal algebra, NATO Sci. Ser. II Math. Phys. Chem., vol. 207, Springer, Dordrecht, 2005, pp. 181–213. Notes taken by Alexander Semigrodskikh. MR**2210131**, 10.1007/1-4020-3817-8_8**[LT07]**Benoît Larose and Pascal Tesson,*Universal algebra and hardness results for constraint satisfaction problems*, Automata, languages and programming, Lecture Notes in Comput. Sci., vol. 4596, Springer, Berlin, 2007, pp. 267–278. MR**2424689**, 10.1007/978-3-540-73420-8_25**[MM08]**Miklós Maróti and Ralph McKenzie,*Existence theorems for weakly symmetric operations*, Algebra Universalis**59**(2008), no. 3-4, 463-489.

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.