|
CSP dichotomy for special triads
Author(s):
Libor
Barto;
Marcin
Kozik;
Miklós
Maróti;
Todd
Niven
Journal:
Proc. Amer. Math. Soc.
137
(2009),
2921-2934.
MSC (2000):
Primary 05C85
Posted:
April 2, 2009
Retrieve article in:
PDF
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 .
References:
-
- [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 (91c:05072)
- [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 (electronic). MR 2137072 (2005k:68181)
- [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 (2001h:68137)
- [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 (2002j:05063) - [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 (2000e:68063)
- [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 (92m:05081)
- [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 (90e:05037)
- [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 (91m:68082) - [HN04]
- -, Graphs and homomorphisms, Oxford Lecture Series in Mathematics and its Applications, vol. 28, Oxford University Press, Oxford, 2004. MR 2089014 (2005k:05002)
- [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 (97e:68049)
- [HNZ96b]
- -, Duality and polynomial testing of tree homomorphisms, Trans. Amer. Math. Soc. 348 (1996), no. 4, 1281-1297. MR 1333391 (96h:05072)
- [JCG97]
- Peter Jeavons, David Cohen, and Marc Gyssens, Closure properties of constraints, J. ACM 44 (1997), no. 4, 527-548. MR 1481313 (99a:68089)
- [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; notes taken by Alexander Semigrodskikh, pp. 181-213. MR 2210131 (2006m:68053)
- [LT07]
- Benoit Larose and Pascal Tesson, Universal algebra and hardness results for constraint satisfaction problems, ICALP (2007), Lecture Notes in Comput. Sci., 4596, Springer, Berlin, 2007. MR 2424689
- [MM08]
- Miklós Maróti and Ralph McKenzie, Existence theorems for weakly symmetric operations, Algebra Universalis 59 (2008), no. 3-4, 463-489.
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 Cech 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 Cech Center, Prague, Czech Republic
Email:
niven@karlin.mff.cuni.cz
DOI:
10.1090/S0002-9939-09-09883-9
PII:
S 0002-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
Posted:
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 Cech 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
Copyright of article:
Copyright
2009,
American Mathematical Society
The copyright for this article reverts to public domain after 28 years from publication.
|