×

A combinatorial constraint satisfaction problem dichotomy classification conjecture. (English) Zbl 1187.68250

Summary: We further generalise a construction-the fibre construction-that was developed in an earlier paper of the first two authors. The extension in this paper gives a polynomial-time reduction of CSP\((H)\) for any relational system \(H\) to CSP\((P)\) for any relational system \(P\) that meets a certain technical partition condition, that of being \(K_{3}\)-partitionable.
Moreover, we define an equivalent condition on \(P\), that of being block projective, and using this show that our construction proves \(NP\)-completeness for exactly those CSPs that are conjectured to be \(NP\)-complete by the CSP dichotomy classification conjecture made by Bulatov, Jeavons and Krohkin, and by Larose and Zádori. We thus provide two new combinatorial versions of the CSP dichotomy classification conjecture.
As with our previous version of the fibre construction, we are able to address restricted versions of the dichotomy conjecture. In particular, we reduce the Feder-Hell-Huang conjecture to the CSP dichotomy classification conjecture, and we prove the Kostochka-Nešetřil-Smolíková conjecture. Although these results were proved independently by P. Jonsson, A. Kroklin and F. Kuivinen [in: Computer science – theory and applications. Second international symposium on computer science in Russia, CSR 2007, Ekaterinburg, Russia, September 3–7, 2007. Proceedings. Berlin: Springer. Lecture Notes in Computer Science 4649, 182–193 (2007; Zbl 1188.68153)] and G. Kun [Constraints, MMSNP and expander relational structures (to appear)], respectively, we give different, shorter, proofs.

MSC:

68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
90C27 Combinatorial optimization

Citations:

Zbl 1188.68153
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Barto, L.; Kozik, M.; Niven, T., The CSP dichotomy holds for digraphs with no sources and no sinks (A positive answer to a conjecture of Bang-Jensen and Hell), SIAM J. Comput., 38, 5, 1782-1802 (2009) · Zbl 1191.68460
[2] Bodnarčuk, V. G.; Kaluzhnin, L. A.; Kotov, V. N.; Romov, B. A., Galois theory for Post algebras I-II, Kibernetika, 3, 1-10 (1969), and 5 (1969) 1-9 (in Russian). English version: Cybernetics (1969) 243-252 and 531-539
[3] A. Bulatov, A dichotomy theorem for constraints on a three element set, in: FOCS’02, 2002, pp. 649-658. doi:10.1145/1120582.1120584; A. Bulatov, A dichotomy theorem for constraints on a three element set, in: FOCS’02, 2002, pp. 649-658. doi:10.1145/1120582.1120584
[4] Bulatov, A., \(H\)-Coloring dichotomy revisited, Theoret. Comp. Sci., 349, 1, 31-39 (2005) · Zbl 1086.68052
[5] A. Bulatov, P. Jeavons, Algebraic structures in combinatorial problems, Technical report; A. Bulatov, P. Jeavons, Algebraic structures in combinatorial problems, Technical report · Zbl 1273.68337
[6] Bulatov, A.; Jeavons, P.; Krokhin, A., Classifying the complexity of constraints using finite algebras, SIAM J. Comput., 34, 3, 720-742 (2005) · Zbl 1071.08002
[7] Bulatov, A.; Jeavons, P.; Krokhin, A., Constraint satisfaction problems and finite algebras, (Proceedings of the 27th International Coll. on Automata, Languages and Programming-ICALP’00. Proceedings of the 27th International Coll. on Automata, Languages and Programming-ICALP’00, LNCS, vol. 1853 (2000), Springer), 272-282 · Zbl 0973.68181
[8] Creignou, N.; Khanna, S.; Sudan, M., Complexity classifications of boolean constraint satisfaction problems, (SIAM Monographs on Discrete Mathematics Applications (2001), SIAM) · Zbl 0981.68058
[9] Feder, T.; Hell, P.; Huang, J., List homomorphisms of graphs with bounded degree, Discrete Math., 307, 3-5, 386-392 (2007) · Zbl 1111.05035
[10] Feder, T.; Vardi, M., The computational structure of monotone monadic SNP and constraint satisfaction: A study through datalog and group theory, SIAM J. Comput., 28, 1, 57-104 (1999) · Zbl 0914.68075
[11] Garey, M.; Johnson, D., Computers and Intractability (1979), Freeman: Freeman New York
[12] Geiger, D., Closed systems of functions and predicates, Pacific. J. Math., 27, 95-100 (1968) · Zbl 0186.02502
[13] Hell, P., Algorithmic aspects of graph homomorphisms, (Survey in Combinatorics 2003 (2003), Cambridge University Press), 239-276 · Zbl 1035.05089
[14] Hell, P., From graph colouring to constraint satisfaction: There and back again, (Klazar, M.; Kratochvíl, J.; Loebl, M.; Matoušek, J.; Thomas, R.; Valtr, P., Topics in Discrete Mathematics (2006), Springer Verlag), 407-432 · Zbl 1116.05028
[15] Hell, P.; Nešetřil, J., On the complexity of \(H\)-colouring, J. Combin. Theory B, 48, 92-100 (1990)
[16] Hell, P.; Nešetřil, J., Graphs and Homomorphisms (2004), Oxford University Press · Zbl 1062.05139
[17] Hell, P.; Nešetřil, J., Colouring, constraint satisfaction, and complexity, Comp. Sci. Rev., 2, 3, 143-163 (2008) · Zbl 1302.68251
[18] Holyer, I., The NP-completeness of edge-coloring, SIAM J. Comput., 10, 4, 718-720 (1981) · Zbl 0473.68034
[19] Jeavons, P. G., On the algebraic structure of combinatorial problems, Theor. Comput. Sci., 200, 1-2, 185-204 (1998) · Zbl 0915.68074
[20] Jeavons, P. G.; Cohen, D. A.; Gyssens, M., Closure properties of constraints, J. ACM, 44, 527-548 (1997) · Zbl 0890.68064
[21] P. Jonsson, A. Krokhin, F. Kuivinen, Hard constraint satisfaction problems have hard gaps at location 1, in: CSR’07, in: LNCS vol. 4649, 2007, pp. 182-193; P. Jonsson, A. Krokhin, F. Kuivinen, Hard constraint satisfaction problems have hard gaps at location 1, in: CSR’07, in: LNCS vol. 4649, 2007, pp. 182-193 · Zbl 1188.68153
[22] Kostochka, A.; Nešetřil, J.; Smolíková, P., Colorings and homomorphisms of degenerate and bounded degree graphs, Graph theory (Prague, 1998). Graph theory (Prague, 1998), Discrete Math., 233, 1-3, 257-276 (2001) · Zbl 0983.05032
[23] G. Kun, Constraints, MMSNP and expander relational structures (2007) (submitted for publication); G. Kun, Constraints, MMSNP and expander relational structures (2007) (submitted for publication) · Zbl 1313.05274
[24] Larose, B.; Zádori, L., The complexity of the extendibility problem for finite posets, SIAM J. Discrete Math., 17, 1, 114-121 (2003) · Zbl 1034.06004
[25] Maróti, M.; McKenzie, R., Existence theorems for weakly symmetric operations, Algebra Universalis, 59, 3-4, 463-489 (2008) · Zbl 1186.08003
[26] R. McKenzie, Personal communication; R. McKenzie, Personal communication
[27] Montanari, U., Networks of constraints: Fundamental properties and applications to picture processing, Infor. Sci., 7, 95-132 (1974) · Zbl 0284.68074
[28] Müller, V., On colorings of graphs without short cycles, Discrete Math., 26, 165-176 (1979) · Zbl 0407.05037
[29] Nešetřil, J.; Siggers, M., Combinatorial proof that subprojective constraint satisfaction problems are NP-complete, (MFCS 2007. MFCS 2007, Lecture Notes in Computer Science, vol. 4708 (2007)), 159-170 · Zbl 1147.68530
[30] Nešetřil, J.; Zhu, X., On sparse graphs with given colorings and homomorphisms, J. Combin. Theory Ser. B, 90, 1, 161-172 (2004) · Zbl 1033.05044
[31] Pippenger, N., Theories of Computability (1997), Cambridge University Press · Zbl 0879.03013
[32] Pöschel, R.; Kalužnin, L. A., Funktionen-und Relatrionenalgebren (1979), DVW: DVW Berlin
[33] T.J. Schaefer, The complexity of satisfiability problems, in: Proceedings of the 10th ACM symposium on theory of computing (STOC78), 1978, pp. 216-226; T.J. Schaefer, The complexity of satisfiability problems, in: Proceedings of the 10th ACM symposium on theory of computing (STOC78), 1978, pp. 216-226 · Zbl 1282.68143
[34] Siggers, M., On highly Ramsey infinite graphs, J. Graph Theory, 59, 2, 97-114 (2008) · Zbl 1159.05038
[35] Siggers, M., Dichotomy for bounded degree \(H\)-colouring, Discrete Appl. Math., 157, 201-210 (2009) · Zbl 1213.05100
[36] M. Siggers, A strong mal’cev condition for varieties omitting the unary type, Algebra Universalis (2009) (in press); M. Siggers, A strong mal’cev condition for varieties omitting the unary type, Algebra Universalis (2009) (in press) · Zbl 1216.08002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.