CSP dichotomy for special triads

Barto, Libor; Kozik, Marcin; Maróti, Miklós; Niven, Todd

doi:10.1090/S0002-9939-09-09883-9

CSP dichotomy for special triads
HTML articles powered by AMS MathViewer

by Libor Barto, Marcin Kozik, Miklós Maróti and Todd Niven

Proc. Amer. Math. Soc. 137 (2009), 2921-2934

DOI: https://doi.org/10.1090/S0002-9939-09-09883-9

Published electronically: April 2, 2009

PDF | Request permission

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

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, DOI 10.1016/0166-218X(90)90017-7
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, DOI 10.1137/S0097539700376676
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, DOI 10.1007/3-540-45022-X_{2}4
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.
—, Polymorphisms and the complexity of homomorphism problems, Proceedings of the 40th ACM Symposium on Theory of Computing, STOC’08, 2008.
Victor Dalmau and Justin Pearson, Closure functions and width $1$ 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.
Tomás Feder, Classification of homomorphisms to oriented cycles and of $k$-partite satisfiability, SIAM J. Discrete Math. 14 (2001), no. 4, 471–480. MR 1861785, DOI 10.1137/S0895480199383353
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, DOI 10.1137/S0097539794266766
W. Gutjahr, Graph colourings, Ph.D. Thesis, Free University Berlin, 1991.
Wolfgang Gutjahr, Emo Welzl, and Gerhard Woeginger, Polynomial graph-colorings, Discrete Appl. Math. 35 (1992), no. 1, 29–45. MR 1138082, DOI 10.1016/0166-218X(92)90294-K
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, DOI 10.1007/BF02122553
Pavol Hell and Jaroslav Ne et il, On the complexity of $H$-coloring, J. Combin. Theory Ser. B 48 (1990), no. 1, 92–110. MR 1047555, DOI 10.1016/0095-8956(90)90132-J
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, DOI 10.1093/acprof:oso/9780198528173.001.0001
P. Hell, J. Nešetřil, and X. Zhu, Complexity of tree homomorphisms, Discrete Appl. Math. 70 (1996), no. 1, 23–36. MR 1402736, DOI 10.1016/0166-218X(96)00099-6
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, DOI 10.1090/S0002-9947-96-01537-1
Peter Jeavons, David Cohen, and Marc Gyssens, Closure properties of constraints, J. ACM 44 (1997), no. 4, 527–548. MR 1481313, DOI 10.1145/263867.263489
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, DOI 10.1007/1-4020-3817-8_{8}
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, DOI 10.1007/978-3-540-73420-8_{2}5
Miklós Maróti and Ralph McKenzie, Existence theorems for weakly symmetric operations, Algebra Universalis 59 (2008), no. 3-4, 463–489.