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
DOI:
https://doi.org/10.1090/S0002-9939-09-09883-9
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, https://doi.org/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, https://doi.org/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, https://doi.org/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. MR 1861785, https://doi.org/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. MR 1630445, https://doi.org/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, https://doi.org/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, https://doi.org/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, https://doi.org/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, https://doi.org/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, https://doi.org/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, https://doi.org/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, https://doi.org/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, https://doi.org/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.