×

Colouring, constraint satisfaction, and complexity. (English) Zbl 1302.68251

Summary: Constraint satisfaction problems have enjoyed much attention since the early seventies, and in the last decade have become also a focus of attention amongst theoreticians. Graph colourings are a special class of constraint satisfaction problems; they offer a microcosm of many of the considerations that occur in constraint satisfaction. From the point of view of theory, they are well known to exhibit a dichotomy of complexity – the \(k\)-colouring problem is polynomial-time solvable when \(k \leq 2\), and NP-complete when \(k \geq 3\). Similar dichotomy has been proved for the class of graph homomorphism problems, which are intermediate problems between graph colouring and constraint satisfaction. However, for general constraint satisfaction problems, dichotomy has only been conjectured. Although the conjecture remains unproven to this day, it has been driving much of the theoretical research on constraint satisfaction problems, which combines methods of logic, universal algebra, analysis, and combinatorics. Currently, this is a very active area of research, and it is our goal here to present some of the recent developments, updating some of the information in existing books and surveys, while focusing on both the mathematical and the computational aspects of the theory. Given the level of activity, we are only able to survey a fraction of the new work, with emphasis on our own areas of interest.

MSC:

68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
05C15 Coloring of graphs and hypergraphs
68Q25 Analysis of algorithms and problem complexity
68-02 Research exposition (monographs, survey articles) pertaining to computer science
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] (Rossi, F.; van Beek, P.; Walsh, T., Handbook of Constraint Programming (2006), Elsevier), xix+995p · Zbl 1175.90011
[2] Alon, N.; Shapira, A., Homomorphisms in graph property testing, (Klazar, M.; Kratochvíl, J.; Matoušek, J.; Thomas, R.; Valtr, P., Topics in Discrete Mathematics (2006), Springer), 281-314 · Zbl 1108.68084
[3] Alon, N.; Dinur, I.; Friedgut, E.; Sudakov, B., Graph products, Fourier analysis and spectral techniques, Geom. Funct. Anal., 14, 913-940 (2004) · Zbl 1056.05104
[4] Arora, S.; Lund, C.; Motwani, R.; Sudan, M.; Szegedy, M., Proof verification and the hardness of approximation problems, J. ACM, 45, 501-555 (1998) · Zbl 1065.68570
[5] Atserias, A., On digraph coloring problems and treewidth duality, European J. Combin., 29, 796-820 (2008), Also in: 20th IEEE Symposium on Logic in Computer Science (LICS), 2005, pp. 106-115 · Zbl 1160.05024
[6] Aspvall, B.; Plass, F.; Tarjan, R. E., A linear time algorithm for testing the truth of certain quantified Boolean formulas, Inform. Process. Lett., 8, 121-123 (1979) · Zbl 0398.68042
[7] R.N. Ball, J. Nešetřil, A. Pultr, Dualities in full homomorphisms, in: Semigroups, Acts, and Categories, with Applications to Graphs, Estonian Math. Society, Tartu, 2008, pp. 14-27; R.N. Ball, J. Nešetřil, A. Pultr, Dualities in full homomorphisms, in: Semigroups, Acts, and Categories, with Applications to Graphs, Estonian Math. Society, Tartu, 2008, pp. 14-27
[8] Bandelt, H.-J.; Dählmann, A.; Schütte, H., Absolute retracts of bipartite graphs, Discrete Appl. Math., 16, 191-215 (1987) · Zbl 0614.05046
[9] Bandelt, H.-J.; Farber, M.; Hell, P., Absolute reflexive retracts and absolute bipartite retracts, Discrete Appl. Math., 44, 9-20 (1993) · Zbl 0795.05133
[10] Bandelt, H.-J.; Pesch, E., Efficient characterizations of \(n\)-chromatic absolute retracts, J. Combin. Theory B, 53, 5-31 (1991) · Zbl 0751.05036
[11] Bang-Jensen, J.; Hell, P., The effect of two cyles on the complexity of colourings by directed graphs, Discrete Appl. Math., 26, 1-23 (1990) · Zbl 0697.05029
[12] Bang-Jensen, J.; Hell, P.; MacGillivray, G., The complexity of colouring by semicomplete digraphs, SIAM J. Discrete Math., 1, 281-298 (1988) · Zbl 0678.05018
[13] Bang-Jensen, J.; Hell, P.; MacGillivray, G., On the complexity of colouring by superdigraphs of bipartite graphs, Discrete Math., 109, 27-44 (1992) · Zbl 0783.05047
[14] Bang-Jensen, J.; Hell, P.; MacGillivray, G., Hereditarily hard \(H\)-colouring problems, Discrete Math., 138, 75-92 (1995) · Zbl 0816.68090
[15] L. Barto, M. Kozik, T. Niven, The CSP dichotomy holds for digraphs with no sources and sinks (a positive answer to a conjecture of Bang-Jensen and Hell), SIAM J. Computing. Also, Proc. of the 40th ACM Symposium on Theory of Computing, STOC’08, 2008 pp. 789-796 (in press); L. Barto, M. Kozik, T. Niven, The CSP dichotomy holds for digraphs with no sources and sinks (a positive answer to a conjecture of Bang-Jensen and Hell), SIAM J. Computing. Also, Proc. of the 40th ACM Symposium on Theory of Computing, STOC’08, 2008 pp. 789-796 (in press) · Zbl 1191.68460
[16] Birc, M.; Hujter, M.; Tuza, Zs., Precoloring extension I; interval graphs, Discrete Math., 100, 267-279 (1992) · Zbl 0766.05026
[17] J. Berman, P. Idziak, P. Markovic, R. McKenzie, M. Valeriote, R. Willard, Varieties with few subalgebras of powers, Trans. Amer. Math. Soc. (2008) (in press); J. Berman, P. Idziak, P. Markovic, R. McKenzie, M. Valeriote, R. Willard, Varieties with few subalgebras of powers, Trans. Amer. Math. Soc. (2008) (in press) · Zbl 1190.08004
[18] 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), (in Russian) and 5 (1969), 1-9; english version Cybernetics (1969) 243-252 and 531-539
[19] Borgs, C.; Chayes, J.; Lovász, L.; Sós, V. T.; Vesztergombi, K., Counting graph homomorphisms, (Klazar, M.; Kratochvíl, J.; Matoušek, J.; Thomas, R.; Valtr, P., Topics in Discrete Mathematics (2006), Springer), 315-372 · Zbl 1129.05050
[20] Borsuk, K., Sur les rétractes, Fund. Math., 17, 152-170 (1931) · JFM 57.0729.04
[21] Brewster, R.; Feder, T.; Hell, P.; Huang, J.; MacGillivray, G., Near-unanimity functions and varieties of graphs, SIAM J. Discrete Math., 22, 938-960 (2008) · Zbl 1200.05217
[22] A.A. Bulatov, Tractable conservative constraint satisfaction problems, in: Proceedings of the 18th IEEE Annual Symposium on Logic in Computer Science, LICS 2003, pp. 321-330; A.A. Bulatov, Tractable conservative constraint satisfaction problems, in: Proceedings of the 18th IEEE Annual Symposium on Logic in Computer Science, LICS 2003, pp. 321-330
[23] A.A. Bulatov, Maltsev constraints are tractable, Technical Report PRG-RR-02-05 Oxford University, 2002; A.A. Bulatov, Maltsev constraints are tractable, Technical Report PRG-RR-02-05 Oxford University, 2002
[24] A.A. Bulatov, A dichotomy constraint on a three-element set, in: Proceedings of the 43rd IEEE Symposium on Theory of Computing, 2002, pp. 649-658; A.A. Bulatov, A dichotomy constraint on a three-element set, in: Proceedings of the 43rd IEEE Symposium on Theory of Computing, 2002, pp. 649-658
[25] Bulatov, A. A., \(H\)-colouring dichotomy revisited, Theoret. Comput. Sci., 349, 31-39 (2005) · Zbl 1086.68052
[26] Bulatov, A. A.; Dalmau, V., Maltsev constraints are tractable, SIAM J. Comput., 36, 16-27 (2006)
[27] A.A. Bulatov, P. Jeavons, Algebraic structures in combinatorial problems, Technical Report MATH-AL-4-2001m Technische universität Dresden, Germany, 2001; A.A. Bulatov, P. Jeavons, Algebraic structures in combinatorial problems, Technical Report MATH-AL-4-2001m Technische universität Dresden, Germany, 2001
[28] Bulatov, A. A.; Jeavons, P.; Krokhin, A. A., Classifying complexity of constraints using finite algebras, SIAM J. Comput., 34, 720-742 (2005) · Zbl 1071.08002
[29] A. Bulatov, A. Krokhin, B. Larose, Dualities for constraint satisfaction problems, in: Proceedings of the Dagstuhl Seminar on the Complexity of Constraints, Springer Lecture Notes in Computer Science, 2008 (in press); A. Bulatov, A. Krokhin, B. Larose, Dualities for constraint satisfaction problems, in: Proceedings of the Dagstuhl Seminar on the Complexity of Constraints, Springer Lecture Notes in Computer Science, 2008 (in press) · Zbl 1171.68494
[30] K. Cameron, E.E. Eschen, C.T. Hoang, R. Sritharan, The list partition problem for graphs, in: Proc. 15th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2004, pp. 391-399. Also, SIAM J. Discrete Math. 21 (2007) 900-929; K. Cameron, E.E. Eschen, C.T. Hoang, R. Sritharan, The list partition problem for graphs, in: Proc. 15th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2004, pp. 391-399. Also, SIAM J. Discrete Math. 21 (2007) 900-929 · Zbl 1318.05072
[31] Cheng, E.; Kleinberg, R. P.; Kruk, S. G.; Lindsey, W. A.; Steffy, D. E., A strictly combinatorial approach to a university exam scheduling problem, Congr. Numer., 167, 121-132 (2004) · Zbl 1177.90148
[32] Chudnovsky, M.; Robertson, N.; Seymour, P.; Thomas, R., The strong perfect graph theorem, Ann. Math., 164, 51-229 (2006) · Zbl 1112.05042
[33] Chvátal, V., Star-cutsets and perfect graphs, J. Combin. Theory B, 39, 189-199 (1985) · Zbl 0674.05058
[34] Cohen, D.; Cooper, M.; Jeavons, P., Characterizing tractable constraints, Artificial Intelligence, 65, 347-361 (1994) · Zbl 0803.68053
[35] Cohen, D.; Cooper, M.; Jeavons, P.; Krokhin, A., A maximal tractable class of soft constraints, J. Artificial Intelligence Res., 22, 1-22 (2004) · Zbl 1080.68658
[36] Creignou, N.; Khanna, S.; Sudan, M., (Complexity Classifications of Boolean Constraint Satisfaction Problems. Complexity Classifications of Boolean Constraint Satisfaction Problems, SIAM Monographs on Discrete Math. and Applications, vol. 7 (2001)) · Zbl 0981.68058
[37] V. Dalmau, A new tractable class of constraint satisfaction problems, in: Proceedings 6th International Symposium on Artificial Intelligence and Mathematics, 2000; V. Dalmau, A new tractable class of constraint satisfaction problems, in: Proceedings 6th International Symposium on Artificial Intelligence and Mathematics, 2000 · Zbl 1075.68082
[38] V. Dalmau, Generalized majority-minority operations are tractable, in: Proceedings of the 20th Annual IEEE Symposium on Logic in Computer Science, LICS 05, pp. 438-447; V. Dalmau, Generalized majority-minority operations are tractable, in: Proceedings of the 20th Annual IEEE Symposium on Logic in Computer Science, LICS 05, pp. 438-447 · Zbl 1127.68039
[39] Dalmau, V.; Ford, D., Generalized satisfiability with \(k\) occurrences per variable: A study through delta-matroid parity, (Mathematical Foundations of Computer Science (MFCS 2003). Mathematical Foundations of Computer Science (MFCS 2003), Lecture Notes in Computer Science, vol. 2747 (2003), Springer), 358-367 · Zbl 1124.68372
[40] Dalmau, V.; Krokhin, A.; Larose, B., First-order definable retraction problems for posets and reflexive graphs, J. Logic Comput., 17, 31-51 (2007), also in LICS 2004, pp. 232-241 · Zbl 1129.03017
[41] Dalmau, V.; Krokhin, A.; Larose, B., Retractions onto series-parallel posets, Discrete Math., 308, 2104-2114 (2008) · Zbl 1141.06001
[42] Datar, M.; Feder, T.; Gionis, A.; Motwani, R.; Panigrahy, R., A combinatorial algorithm for MAX CSP, Inform. Process. Lett., 85, 307-315 (2003) · Zbl 1173.68880
[43] Dechter, R., Constraint networks, (Encyclopedia of Artificial Intelligence (1992)), 276-285
[44] Dinur, I., The PCP theorem by gap amplification, J. ACM, 54, 12 (2007) · Zbl 1292.68074
[45] I. Dinur, E. Friedgut, O. Regev, Independent sets in graph powers are almost contained in juntas, GAFA (in press); I. Dinur, E. Friedgut, O. Regev, Independent sets in graph powers are almost contained in juntas, GAFA (in press) · Zbl 1147.05058
[46] Dowling, W. F.; Gallier, J. H., Linear-time algorithms for testing the satisfiability of propositional Horn formulae, J. Logic Program., 1, 267-284 (1984) · Zbl 0593.68062
[47] L. Egri, B. Larose, P. Tesson, The complexity of list homomorphism problems for graphs (in preparation); L. Egri, B. Larose, P. Tesson, The complexity of list homomorphism problems for graphs (in preparation) · Zbl 1230.68106
[48] R. Fagin, Generalized first-order spectra and polynomial-time recognizable sets, in: R. Karp (Ed.), Complexity of Computation, SIAM-AMS Proceedings 7, 1974, pp. 43-73; R. Fagin, Generalized first-order spectra and polynomial-time recognizable sets, in: R. Karp (Ed.), Complexity of Computation, SIAM-AMS Proceedings 7, 1974, pp. 43-73 · Zbl 0303.68035
[49] Feder, T., Homomorphisms to oriented cycles and \(k\)-partite satisfiability, SIAM J. Discrete Math., 14, 471-480 (2001) · Zbl 0982.05097
[50] T. Feder, Constraint satisfaction: A personal perspective, manuscript 2004; T. Feder, Constraint satisfaction: A personal perspective, manuscript 2004
[51] Feder, T., A dichotomy theorem on fixed points of several nonexpansive mappings, SIAM J. Discrete Math., 20, 291-301 (2006) · Zbl 1115.68110
[52] T. Feder, D. Ford, Classification of bipartite Boolean constraint satisfaction through delta-matroid intersection, manuscript; T. Feder, D. Ford, Classification of bipartite Boolean constraint satisfaction through delta-matroid intersection, manuscript · Zbl 1115.68090
[53] Feder, T.; Hell, P., List homomorphisms to reflexive graphs, J. Comb. Theory Ser. B, 72, 236-250 (1998) · Zbl 0904.05078
[54] Feder, T.; Hell, P., Full constraint satisfaction problems, SIAM J. Comput., 36, 230-246 (2006) · Zbl 1111.68115
[55] Feder, T.; Hell, P., Matrix partitions of perfect graphs, Discrete Math., 306, 2450-2460 (2006) · Zbl 1143.05035
[56] Feder, T.; Hell, P., On realizations of point determining graphs, and obstructions to full homomorphisms, Discrete Math., 308, 1639-1652 (2008) · Zbl 1135.05042
[57] T. Feder, P. Hell, The complexity of retraction and subretraction problems for reflexive digraphs, manuscript 2007; T. Feder, P. Hell, The complexity of retraction and subretraction problems for reflexive digraphs, manuscript 2007
[58] Feder, T.; Hell, P.; Huang, J., List homomorphisms and circular arc graphs, Combinatorica, 19, 487-505 (1999) · Zbl 0985.05048
[59] Feder, T.; Hell, P.; Huang, J., Bi-arc graphs and the complexity of list homomorphisms, J. Graph Theory, 42, 61-80 (2003) · Zbl 1057.05033
[60] Feder, T.; Hell, P.; Huang, J., List homomorphisms of graphs with bounded degrees, Discrete Math., 307, 386-392 (2007) · Zbl 1111.05035
[61] T. Feder, P. Hell, J. Huang, A. Rafiey, Adjusted interval digraphs, manuscript 2008; T. Feder, P. Hell, J. Huang, A. Rafiey, Adjusted interval digraphs, manuscript 2008
[62] Feder, T.; Hell, P.; Klein, S.; Motwani, R., Complexity of list partitions, SIAM J. Discrete Mathematics, 16, 449-478 (2003) · Zbl 1029.05143
[63] Feder, T.; Hell, P.; Klein, S.; Nogueira, L.; Protti, F., List matrix partitions of chordal graphs, Theoret. Comput. Sci., 349, 52-66 (2005) · Zbl 1084.05026
[64] Feder, T.; Hell, P.; Kral, D.; Sgall, J., Two algorithms for list matrix partitions, (Symposium on Discrete Algorithms (2005)), 870-876 · Zbl 1297.68091
[65] Feder, T.; Hell, P.; Mohar, B., Acyclic homomorphisms and circular colorings of digraphs, SIAM J. Discrete Math., 17, 161-169 (2003) · Zbl 1034.05022
[66] T. Feder, P. Hell, A. Rafiey, List homomorphisms to irreflexive digraphs, manuscript 2008; T. Feder, P. Hell, A. Rafiey, List homomorphisms to irreflexive digraphs, manuscript 2008
[67] Feder, T.; Hell, P.; Tucker-Nally, K., Digraph matrix partitions and trigraph homomorphisms, Discrete Appl. Math., 154, 2458-2469 (2006) · Zbl 1106.05060
[68] Feder, T.; Hell, P.; Hochstättler, W., Generalized colourings (matrix partitions) of cographs, (Graph Theory in Paris, Trends in Mathematics (2006), Birkhauser Verlag), 149-167 · Zbl 1114.05060
[69] T. Feder, P. Hell, W. Xie, Obstructions to generalized colourings, ICDM 2006, Bangalore, India, Lecture Notes of the Ramanujan Math. Society 2007; T. Feder, P. Hell, W. Xie, Obstructions to generalized colourings, ICDM 2006, Bangalore, India, Lecture Notes of the Ramanujan Math. Society 2007
[70] Feder, T.; Madelaine, F.; Stewart, I. A., Dichotomies for classes of homomorphism problems involving unary functions, Theoret. Comput. Sci., 314, 1-43 (2004) · Zbl 1070.68133
[71] Feder, T.; Vardi, M. Y., The computational structure of monotone monadic SNP and constraint satisfaction: A study through Datalog and group theory, SIAM J. Comput. 28, 236-250 (1998), ALSO in STOC 25 (1993) 612-622 · Zbl 0914.68075
[72] Fiala, J.; Kratochvil, J., Locally constrained graph homomorphisms, Comp. Sci. Rev., 2, 97-112 (2008) · Zbl 1302.05122
[73] de Figueiredo, C. M.H.; Klein, S.; Kohayakawa, Y.; Reed, B., Finding skew partitions efficiently, J. Algorithms, 37, 505-521 (2000) · Zbl 0964.68107
[74] Foldes, S.; Hammer, P., Split graphs, Congr. Numer., 19, 311-315 (1977)
[75] Foniok, J.; Nešetřil, J.; Tardif, C., Generalized dualities and maximal finite antichains in the homomorphism order of relational structures, European J. Combin., 29, 881-899 (2008) · Zbl 1147.05037
[76] Freedman, M. H.; Lovász, L.; Schrijver, A., Reflection positivity, rank connectivity and homomorphisms of graphs, J. Amer. Math. Soc., 20, 37-51 (2007) · Zbl 1107.05089
[77] Gallai, T., On directed paths and circuits, (Theory of Graphs (Proc. Colloq., Tihany, 1966) (1968), Academic Press: Academic Press New York), 115-118 · Zbl 0159.54403
[78] Galluccio, A.; Hell, P.; Nešetřil, J., The complexity of H-colouring of bounded degree graphs, Discrete Math., 222, 101-109 (2000) · Zbl 0956.05036
[79] Garey, M.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-completeness (1979), Freeman and Company · Zbl 0411.68039
[80] Geiger, D., Closed systems of functions and predicates, Pacific J. Math., 27, 95-100 (1968) · Zbl 0186.02502
[81] Golumbic, M. C., Algorithmic Graph Theory and Perfect Graphs (1980), Academic Press: Academic Press New York · Zbl 0541.05054
[82] Greenwell, D.; Lovász, L., Applications of product coloring, Acta Math. Acad. Sci. Hungar., 25, 335-340 (1974) · Zbl 0294.05108
[83] Gupta, A.; Hell, P.; Karimi, M.; Rafiey, A., Minimum cost homomorphisms to reflexive digraphs, (LATIN (2008)) · Zbl 1136.68462
[84] A. Gupta, G. Gutin, M. Karimi, E.J. Kim, A. Rafiey, Minimum cost homomorphisms to locally semicomplete and quasi-transitive digraphs, manuscript 2008; A. Gupta, G. Gutin, M. Karimi, E.J. Kim, A. Rafiey, Minimum cost homomorphisms to locally semicomplete and quasi-transitive digraphs, manuscript 2008 · Zbl 1196.05055
[85] A. Gupta, M. Karimi, E.J. Kim, A. Rafiey, Minimum cost homomorphism dichotomy for locally in-semicomplete digraphs, in: COCOA 2008; A. Gupta, M. Karimi, E.J. Kim, A. Rafiey, Minimum cost homomorphism dichotomy for locally in-semicomplete digraphs, in: COCOA 2008 · Zbl 1168.05312
[86] Gutin, G.; Hell, P.; Rafiey, A.; Yeo, A., Minimum cost homomorphisms to proper interval graphs and bigraphs, Europ. J. Combin., 29, 900-911 (2008) · Zbl 1149.90164
[87] Gutin, G.; Rafiey, A.; Yeo, A., Minimum cost and list homomorphisms to semicomplete digraphs, Discrete Appl. Math., 154, 890-897 (2006) · Zbl 1138.05032
[88] Gutin, G.; Rafiey, A.; Yeo, A.; Tso, M., Level of repair analysis and minimum cost homomorphisms of graphs, Discrete Appl. Math. (2007)
[89] Gutin, G.; Kim, E. J., Introduction to the minimum cost homomorphism problem for directed and undirected graphs, (Lecture Notes of the Ramanujan Math. Society (2007)) · Zbl 1189.90179
[90] Gutjahr, W.; Welzl, E.; Woeginger, G., Polynomial graph-colorings, Discrete Appl. Math., 35, 29-45 (1992) · Zbl 0761.05040
[91] Graham, R. L.; Rothschild, B.; Spencer, J., Ramsey Theory (1980), Wiley · Zbl 0455.05002
[92] Hasse, M., Zur algebraischen Begründung der Graphentheorie I, Math Nachr., 28, 275-290 (1964-1965) · Zbl 0214.51003
[93] P. Hell, Rétractions des graphes, Ph.D. Thesis, Université de Montréal, 1972; P. Hell, Rétractions des graphes, Ph.D. Thesis, Université de Montréal, 1972
[94] Hell, P., Absolute planar retracts and the four color conjecture, J. Combin. Theory B, 17, 5-10 (1974) · Zbl 0267.05102
[95] Hell, P., Absolute retracts in graphs, (Bari, R. A.; Harary, F., Graphs and Combinatorics. Graphs and Combinatorics, Springer-Verlag Lecture Notes in Mathematics, vol. 406 (1974)), 291-301
[96] Hell, P., From graph colouring to constraint satisfaction: There and back again, (Topics in Discrete Mathematics. Topics in Discrete Mathematics, Springer Verlag Algorithms and Combinatorics Series, vol. 26 (2006)), 407-432 · Zbl 1116.05028
[97] Hell, P., Algorithmic aspects of graph homomorphisms, (Wensley, C. D., Surveys in Combinatorics 2003. Surveys in Combinatorics 2003, London Math. Society Lecture Note Series, vol. 307 (2003), Cambridge University Press), 239-276 · Zbl 1035.05089
[98] Hell, P.; Klein, S.; Tito Nogueira, L.; Protti, F., Partitioning chordal graphs into independent sets and cliques, Discrete Appl. Math., 141, 185-194 (2004) · Zbl 1043.05097
[99] Hell, P.; Nešetřil, J., The core of a graph, Discrete Math., 109, 117-126 (1992) · Zbl 0803.68080
[100] Hell, P.; Nešetřil, J.; Zhu, X., Duality of graph homomorphisms, (Combinatorics, Paul Erdos is Eighty. Combinatorics, Paul Erdos is Eighty, Bolyai Society Mathematical Studies, vol. 2 (1996)), 271-282 · Zbl 0846.05093
[101] Hell, P.; Nešetřil, J., On the complexity of \(H\)-coloring, J. Comb. Theory, Ser. B, 48, 92-110 (1990) · Zbl 0639.05023
[102] Hell, P.; Nešetřil, J., Counting list homomorphisms and graphs with bounded degrees, (Nešetřil, J.; Winkler, P., Graphs, Morphisms and Statistical Physics. Graphs, Morphisms and Statistical Physics, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 63 (2004)), 105-112 · Zbl 1059.05049
[103] Hell, P.; Nešetřil, J., Graphs and Homomorphisms (2004), Oxford University Press · Zbl 1062.05139
[104] Hell, P.; Nešetřil, J.; Zhu, X., Complexity of tree homomorphisms, Discrete Appl. Math., 70, 23-36 (1996) · Zbl 0868.05018
[105] Hell, P.; Nešetřil, J.; Zhu, X., Duality and polynomial testing of tree homomorphisms, Trans. Amer. Math. Soc., 348, 1281-1297 (1996) · Zbl 0877.05055
[106] Hell, P.; Rival, I., Absolute retracts and varieties of reflexive graphs, Canad. J. Math., 39, 544-567 (1987) · Zbl 0627.05039
[107] Hoory, S.; Linial, N.; Wigderson, A., Expander graphs and their applications, Bull. Amer. Math. Soc., 43, 439-561 (2006) · Zbl 1147.68608
[108] Horn, A., On sentences which are true of direct unions of algebras, J. Symbolic Logic, 16, 14-21 (1951) · Zbl 0043.24801
[109] J. Hubička, J. Nešetřil, Universal structures as shadows of ultrahomogeneous structures (submitted for publication); J. Hubička, J. Nešetřil, Universal structures as shadows of ultrahomogeneous structures (submitted for publication)
[110] Hujter, M.; Tuza, Zs., Precoloring extension II; graph classes related to bipartite graphs, Acta Math. Universitatis Comenianae, 62, 1-11 (1993) · Zbl 0821.05026
[111] Hujter, M.; Tuza, Zs., Precoloring extension III; classes of perfect graphs, Combin. Probab. Comput., 5, 35-56 (1996) · Zbl 0846.05034
[112] P. Idziak, P. Markovic, R. McKenzie, M. Valeriote, R. Willard, Tractability and learnability arising from algebras with few subpowers (extended abstract), in: Proceedings of the 22nd Annual IEEE Symposium on Logic in Computer Science, LICS 2007, pp. 213-224; P. Idziak, P. Markovic, R. McKenzie, M. Valeriote, R. Willard, Tractability and learnability arising from algebras with few subpowers (extended abstract), in: Proceedings of the 22nd Annual IEEE Symposium on Logic in Computer Science, LICS 2007, pp. 213-224 · Zbl 1216.68129
[113] Jawhari, E. M.; Misane, D.; Pouzet, M., Retracts: Graphs and ordered sets from the metric point of view, Contemp. Math. (Amer. Math. Soc.), 57, 175-226 (1986)
[114] Jeavons, P., On the algebraic structure of combinatorial problems, Theoret. Comput. Sci., 200, 185-204 (1998) · Zbl 0915.68074
[115] Jeavons, P.; Cohen, D.; Gyssens, M., Closure properties of constraints, J. ACM, 44, 527-548 (1997) · Zbl 0890.68064
[116] P. Jeavons, D. Cohen, M. Gyssens, A unifying framework for tractable constraints, in: Proc. 1st International Conference on Constraint Programming, CP’95, Cassis 1995; P. Jeavons, D. Cohen, M. Gyssens, A unifying framework for tractable constraints, in: Proc. 1st International Conference on Constraint Programming, CP’95, Cassis 1995
[117] Johnson, D. S., The NP-completeness columns: An ongoing guide, J. Algorithms, 3, 89-99 (1982) · Zbl 0494.68048
[118] Kalai, G., A Fourier-theoretic perspective for the Condorcet parados and Arrow’s theorem, Adv. Appl. Math., 29, 412-426 (2002) · Zbl 1038.91027
[119] Kim, J. H., The Ramsey number \(R(3, t)\) has order of magnitude \(t^2 / \log t\), Random Struct. Algorithms, 7, 173-207 (1995) · Zbl 0832.05084
[120] P. Kolaitis, M. Vardi, Conjunctive-query containment and constraint satisfaction, in: Proc. of the 17th ACM SIGACT SIGMOD SIGART Symp. on Principles of Database Systems 1998, PODS’98, pp. 205-213; P. Kolaitis, M. Vardi, Conjunctive-query containment and constraint satisfaction, in: Proc. of the 17th ACM SIGACT SIGMOD SIGART Symp. on Principles of Database Systems 1998, PODS’98, pp. 205-213 · Zbl 0963.68059
[121] Kostochka, A.; Nešetřil, J.; Smolíková, P., Colorings and homomorphisms of degenerate and bounded degree graphs, Discrete Math., 233, 257-276 (2001) · Zbl 0983.05032
[122] Krokhin, A.; Larose, B., Maximizing supermodular functions on product lattices, with application to maximum constraint satisfaction, SIAM J. Discrete Math., 22, 312-328 (2008) · Zbl 1167.90017
[123] Kumar, V., Algorithms for constraint-satisfaction problems, AI Mag., 13, 32-44 (1992)
[124] G. Kun, Constraints, MMSNP and expander structures, Combinatorica (submitted for publication); G. Kun, Constraints, MMSNP and expander structures, Combinatorica (submitted for publication)
[125] G. Kun, M. Szegedy, A new line of attack on the dichotomy conjecture, manuscript 2008; G. Kun, M. Szegedy, A new line of attack on the dichotomy conjecture, manuscript 2008 · Zbl 1304.68076
[126] Kun, G.; Nešetřil, J., Forbidden lifts (NP and CSP for combinatorists), European J. Combin., 29, 930-945 (2008) · Zbl 1213.68323
[127] Ladner, R. E., On the structure of polynomial time reducibility, J. Assoc. Comput. Mach., 22, 155-171 (1975) · Zbl 0322.68028
[128] Larose, B., Taylor operations on finite reflexive structures, Internat. J. Math. Comput. Sci., 1, 1-26 (2006) · Zbl 1100.08003
[129] Larose, B.; Tardif, C., Projectivity and independent sets in powers of graphs, J. Graph Theory, 40, 162-171 (2002) · Zbl 1003.05077
[130] Larose, B.; Loten, C.; Tardif, C., A characterization of first-order constraint satisfaction problems, Logical Methods Comput. Sci., 3, 4 (2007), 6, 22pp (electronic) · Zbl 1131.68098
[131] Larose, B.; Loten, C.; Zádori, L., A polynomial-time algorithm for near-unanimity graphs, J. Algorithms, 55, 177-191 (2005) · Zbl 1101.68960
[132] Larose, B.; Zádori, L., Finite posets and topological spaces in locally finite varieties, Algebra Universalis, 52, 119-136 (2004) · Zbl 1090.06004
[133] Larose, B.; Zádori, L., The complexity of the extendibility problem for finite posets, SIAM J. Discrete Math., 17, 114-121 (2003) · Zbl 1034.06004
[134] P. Lincoln, J.C. Mitchell, Algorithmic aspects of type inference with subtypes, in: Conf. Rec. 19th ACM Symp. on Principles of Programming Languages, 1992, pp. 293-304; P. Lincoln, J.C. Mitchell, Algorithmic aspects of type inference with subtypes, in: Conf. Rec. 19th ACM Symp. on Principles of Programming Languages, 1992, pp. 293-304
[135] Lotfi, V.; Sarin, S., A graph coloring algorithm for large scale scheduling problems, Comput. Oper. Res., 13, 27-32 (1986) · Zbl 0633.90031
[136] Łuczak, T.; Nešetřil, J., A note on projective graphs, J. Graph Theory, 47, 81-86 (2004) · Zbl 1055.05131
[137] T. Łuczak, J. Nešetřil, Towards probabilistic analysis of the dichotomy problem, KAM-DIMATIA Series 2003-640, Charles Univ. Prague; T. Łuczak, J. Nešetřil, Towards probabilistic analysis of the dichotomy problem, KAM-DIMATIA Series 2003-640, Charles Univ. Prague
[138] R. McKenzie, Personal communication, 2007; R. McKenzie, Personal communication, 2007
[139] M. Maŕoti, R. McKenzie, Existence theorems for weakly symmetric operations, manuscript 2006, Algebra Universalis (in press); M. Maŕoti, R. McKenzie, Existence theorems for weakly symmetric operations, manuscript 2006, Algebra Universalis (in press)
[140] Marx, D., Precoloring extension on chordal graphs, (Graph Theory in Paris, Trends in Mathematics (2007), Birkhäuser), 255-270 · Zbl 1123.05041
[141] J. Matoušek, J. Nešetřil, Constructions of sparse graphs with given homomorphisms, manuscript, 2004; J. Matoušek, J. Nešetřil, Constructions of sparse graphs with given homomorphisms, manuscript, 2004
[142] Meseguer, P., Constraint satisfaction problem: An overview, AICOM, 2, 3-16 (1989)
[143] J.C. Mitchell, Coercion and type inference (summary), in: Conf. Rec. 11th ACM Symp. on Principles of Programming Languages, 1984, pp. 175-185; J.C. Mitchell, Coercion and type inference (summary), in: Conf. Rec. 11th ACM Symp. on Principles of Programming Languages, 1984, pp. 175-185
[144] Müller, V., On colorable critical and uniquely colorable critical graphs, (Fiedler, M., Recent Advances in Graph Theory (1975), Academia: Academia Prague) · Zbl 0329.05105
[145] Müller, V., On coloring of graphs without short cycles, Discrete Math., 26, 165-179 (1979)
[146] Montanari, U., Networks of constraints: Fundamental properties and applications to picture processing, Inform. Sci., 7, 95-132 (1974) · Zbl 0284.68074
[147] Nešetřil, J., Aspects of structural combinatorics, Taiwanese J. Math., 3, 4, 381-424 (1999) · Zbl 0939.05001
[148] Nešetřil, J., Ramsey Theory, (Graham, R. L.; Grötschel, M.; Lovász, L., Handbook of Combinatorics (1995), Elsevier), 1331-1403 · Zbl 0848.05065
[149] Nešetřil, J., Many facets of dualities, (Cook, W.; Lovász, L.; Vygen, J., Research Trends in Combinatorial Optimization (2009), Springer: Springer Berlin) · Zbl 1359.05060
[150] Nešetřil, J.; Ossona de Mendez, P., Cuts and bounds, Discrete Math., 302, 211-224 (2005) · Zbl 1076.05089
[151] Nešetřil, J.; Ossona de Mendez, P., Folding, J. Combin. Theory B, 96, 730-739 (2006) · Zbl 1100.05037
[152] Nešetřil, J.; Ossona de Mendez, P., Tree depth, subgraph coloring and homomorphism bounds, European J. Combin., 27, 1022-1041 (2006) · Zbl 1089.05025
[153] Nešetřil, J.; Ossona de Mendez, P., Low tree-width decompositions and algorithmic consequences, (Proceedings of the 38th Annual ACM Symposium on Theory of Computing. Proceedings of the 38th Annual ACM Symposium on Theory of Computing, STOC’06 (2006), ACM Press), 391-400 · Zbl 1301.05268
[154] Nešetřil, J.; Ossona de Mendez, P., Structural properties of sparse graphs, (Grötschel, M.; Katona, G. O.H., Building Bridges — Between Mathematics and Computer Science (2008), Springer), 369-426 · Zbl 1260.05090
[155] Nešetřil, J.; Ossona de Mendez, P., Grad and classes with bounded expansion I. Decompositions, European J. Combin., 29, 3, 760-776 (2008) · Zbl 1156.05056
[156] Nešetřil, J.; Ossona de Mendez, P., Grad and classes with bounded expansion II. Algorithmic aspects, European J. Combin., 29, 777-791 (2008) · Zbl 1185.05131
[157] Nešetřil, J.; Ossona de Mendez, P., Grad and classes with bounded expansion III. Restricted dualities, European J. Combin., 29, 1012-1024 (2008) · Zbl 1213.05240
[158] J. Nešetřil, P. Ossona de Mendez, First order properties of nowhere dense structures, J. Symb. Logic (2008) (submitted for publication); J. Nešetřil, P. Ossona de Mendez, First order properties of nowhere dense structures, J. Symb. Logic (2008) (submitted for publication)
[159] Nešetřil, J.; Pultr, A., On classes of relations and graphs determined by subobjects and factorobjects, Discrete Math., 22, 287-300 (1978) · Zbl 0388.05039
[160] Nešetřil, J.; Rödl, V., Chromatically optimal rigid graphs, J. Combin. Th. B, 46, 122-141 (1989) · Zbl 0677.05031
[161] J. Nešetřil, M. Siggers, L. Zádori, A Combinatorial constraint satisfaction problem dichotomy classification conjecture, manuscript, 2007; J. Nešetřil, M. Siggers, L. Zádori, A Combinatorial constraint satisfaction problem dichotomy classification conjecture, manuscript, 2007
[162] Nešetřil, J.; Siggers, M., A combinatorial proof that subprojective constraint satisfaction problems are NP-complete, (32nd International Symposium MFCS 2007. 32nd International Symposium MFCS 2007, Lecture Notes in Computer Science, vol. 4708 (2007), Springer), 159-170 · Zbl 1147.68530
[163] Nešetřil, J.; Tardif, C., A dualistic approach to bounding the chromatic number of a graph, European J. Combin., 29, 254-260 (2008) · Zbl 1126.05051
[164] Nešetřil, J.; Tardif, C., Homomorphism duality: On short answers to exponentially long questions, SIAM J. Discrete Math., 19, 914-920 (2005) · Zbl 1105.05025
[165] Nešetřil, J.; Tardif, C., Duality theorems for finite structures (characterising gaps and good characterizations), J. Combin. Theory B, 80, 80-97 (2000) · Zbl 1024.05078
[166] Nešetřil, J.; Zhu, X., On sparse graphs with given colorings and homomorphisms, J. Combin. Th. B, 90, 161-172 (2004) · Zbl 1033.05044
[167] Pesch, E., Retracts of Graphs (1988), Athenaeum Verlag: Athenaeum Verlag Frankfurt · Zbl 0667.05021
[168] Pratt, V.; Tiuryn, J., Satisfiability of inequalities in a poset, Fund. Inform., 28, 165-182 (1996) · Zbl 0863.68073
[169] Pultr, A.; Trnková, V., Combinatorial, Algebraic and Topological Representations of Groups, Semigroups and Categories (1980), North-Holland: North-Holland Amsterdam · Zbl 0418.18004
[170] Quilliot, A., A retraction problem in graph theory, Discrete Math., 54, 61-71 (1985) · Zbl 0588.05043
[171] Radhakrishnan, J.; Sudan, M., On Dinur’s proof of the PCP theorem, Bull. Amer. Math. Soc., 44, 19-61 (2007) · Zbl 1112.68117
[172] B. Rossman, Existential positive types and preservation under homomorphisms, in: 20th IEEE Symposium on Logic in Computer Science, LICS, 2005, pp. 467-476; B. Rossman, Existential positive types and preservation under homomorphisms, in: 20th IEEE Symposium on Logic in Computer Science, LICS, 2005, pp. 467-476
[173] Roy, B., Nombre chromatique et plus longs chemins d’un graph, Rev. Francaise Informat. Recherche Opérationelle, 1, 129-132 (1967) · Zbl 0157.31302
[174] Vitaver, L. M., Determination of minimal coloring of vertices of a graph by means of Boolean powers of the incidence matrix, Dokl. Akad. Nauk SSSR, 147, 758-759 (1962), (in Russian)
[175] Salazar, A.; Oakford, R. V., A graph formulation of a school scheduling algorithm, Comm. ACM, 17, 696-698 (1974) · Zbl 0293.90025
[176] T.J. Schaefer, The complexity of satisfiability problems, in: Proc. 10th ACM Symp. on Theory of Computing, 1978, pp. 216-226; T.J. Schaefer, The complexity of satisfiability problems, in: Proc. 10th ACM Symp. on Theory of Computing, 1978, pp. 216-226 · Zbl 1282.68143
[177] G. Schell, Tridiagonal matrix partitions, M.Sc. Thesis, SFU 2008; G. Schell, Tridiagonal matrix partitions, M.Sc. Thesis, SFU 2008
[178] Tsang, E. P.K., Foundations of Constraint Satisfaction (1993), Academic Press: Academic Press London and San Diego
[179] M.Y. Vardi, Constraint satisfaction and database theory: A tutorial, in: Proceedings of the 19th Symposium on Principles of Database Systems, PODS 2000, pp. 76-85; M.Y. Vardi, Constraint satisfaction and database theory: A tutorial, in: Proceedings of the 19th Symposium on Principles of Database Systems, PODS 2000, pp. 76-85
[180] Vikas, N., Computational complexity of compaction to reflexive cycles, SIAM J. Comput., 32, 253-280 (2003) · Zbl 1029.68085
[181] M. Wand, P.M. O’Keefe, On the complexity of type inference with coercion, in: Conf. on Functional Programming Languages and Computer Architecture, 1989, pp. 293-298; M. Wand, P.M. O’Keefe, On the complexity of type inference with coercion, in: Conf. on Functional Programming Languages and Computer Architecture, 1989, pp. 293-298
[182] Sen, M.; Das, S.; Roy, A. B.; West, D. B., Interval digraphs: An analogue of interval graphs, J. Graph Theory, 13, 581-592 (1989) · Zbl 0671.05039
[183] M.H. Siggers, \(H\)-colouring dichotomy re-revisited, manuscript, 2008; M.H. Siggers, \(H\)-colouring dichotomy re-revisited, manuscript, 2008
[184] Tarjan, R. E., Decomposition by clique separators, Discrete Math., 55, 221-232 (1985) · Zbl 0572.05039
[185] Thomassen, C., Grötzsch’s 3-color theorem and its counterparts for torus and the projective plane, J. Combin. Th. B, 62, 268-279 (1994) · Zbl 0817.05024
[186] W. Xie, Forbidden subgraph characterizations of matrix partitions, M.Sc. Thesis, Simon Fraser University, 2006; W. Xie, Forbidden subgraph characterizations of matrix partitions, M.Sc. Thesis, Simon Fraser University, 2006
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.