Topology and adjunction in promise constraint satisfaction. (English) Zbl 07672224
Summary: The approximate graph coloring problem, whose complexity is unresolved in most cases, concerns finding a \(c\)-coloring of a graph that is promised to be \(k\)-colorable, where \(c\geq k\). This problem naturally generalizes to promise graph homomorphism problems and further to promise constraint satisfaction problems. The complexity of these problems has recently been studied through an algebraic approach. In this paper, we introduce two new techniques to analyze the complexity of promise CSPs: one is based on topology and the other on adjunction. We apply these techniques, together with the previously introduced algebraic approach, to obtain new unconditional NP-hardness results for a significant class of approximate graph coloring and promise graph homomorphism problems.
MSC:
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 68Q25 | Analysis of algorithms and problem complexity |
| 68R05 | Combinatorics in computer science |
| 05C15 | Coloring of graphs and hypergraphs |
Keywords:
graph coloring; graph homomorphism problem; constraint satisfaction; polymorphism; promise problemReferences:
| [1] | Austrin, P., Bhangale, A., and Potukuchi, A., Simplified Inapproximability of Hypergraph Coloring via t-Agreeing Families, preprint, arXiv:1904.01163, 2019. |
| [2] | Austrin, P., Bhangale, A., and Potukuchi, A., Improved inapproximability of rainbow coloring, in Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’20), , SIAM, Philadelphia, 2020, pp. 1479-1495, doi:10.1137/1.9781611975994.90. · Zbl 07304113 |
| [3] | Austrin, P., Guruswami, V., and Håstad, J., \((2+\epsilon \) )-Sat is NP-hard, SIAM J. Comput., 46 (2017), pp. 1554-1573, doi:10.1137/15M1006507. · Zbl 1476.68188 |
| [4] | Babson, E. and Kozlov, D. N., Complexes of graph homomorphisms, Israel J. Math., 152 (2006), pp. 285-312, doi:10.1007/BF02771988. · Zbl 1205.52009 |
| [5] | Barto, L., Bulín, J., Krokhin, A., and Opršal, J., Algebraic approach to promise constraint satisfaction, J. ACM, 68 (2021), 28, doi:10.1145/3457606. · Zbl 1499.68140 |
| [6] | Barto, L. and Kozik, M., Robustly solvable constraint satisfaction problems, SIAM J. Comput., 45 (2016), pp. 1646-1669, doi:10.1137/130915479. · Zbl 1350.68127 |
| [7] | Barto, L., Krokhin, A., and Willard, R., Polymorphisms, and how to use them, in The Constraint Satisfaction Problem: Complexity and Approximability, , Schloss Dagstuhl, Dagstuhl, Germany, 2017, pp. 1-44, doi:10.4230/DFU.Vol7.15301.1. · Zbl 1482.68161 |
| [8] | Barto, L., Opršal, J., and Pinsker, M., The wonderland of reflections, Israel J. Math., 223 (2018), pp. 363-398, doi:10.1007/s11856-017-1621-9. · Zbl 1397.08002 |
| [9] | Bhangale, A., NP-hardness of coloring 2-colorable hypergraph with poly-logarithmically many colors, in Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP’18), LIPIcs, , Schloss Dagstuhl, Wadern, Germany, 2018, 15, doi:10.4230/LIPIcs.ICALP.2018.15. · Zbl 1499.68251 |
| [10] | Bodnarchuk, V. G., Kaluzhnin, L. A., Kotov, V. N., and Romov, B. A., Galois theory for post algebras. I, Cybernetics, 5 (1969), pp. 243-252. |
| [11] | Bodnarchuk, V. G., Kaluzhnin, L. A., Kotov, V. N., and Romov, B. A., Galois theory for post algebras. II, Cybernetics, 5 (1969), pp. 531-539. |
| [12] | Borsuk, K., Drei Sätze über die n-dimensionale euklidische Sphäre, Fund. Math., 20 (1933), pp. 177-190. · Zbl 0006.42403 |
| [13] | Brakensiek, J. and Guruswami, V., New hardness results for graph and hypergraph colorings, in Proceedings of the 31st Conference on Computational Complexity (CCC 2016), LIPIcs Leibniz Int. Proc. Inform. 50, , Schloss Dagstuhl, Wadern, Germany, 2016, 14, doi:10.4230/LIPIcs.CCC.2016.14. · Zbl 1380.68190 |
| [14] | Brakensiek, J. and Guruswami, V., An algorithmic blend of LPs and ring equations for promise CSPs, in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, , SIAM, Philadelphia, 2019, pp. 436-455, doi:10.1137/1.9781611975482.28. · Zbl 1431.68043 |
| [15] | Brakensiek, J. and Guruswami, V., Symmetric polymorphisms and efficient decidability of promise CSPs, in Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, , SIAM, Philadelphia, 2020, pp. 297-304, doi:10.1137/1.9781611975994.18. · Zbl 07304041 |
| [16] | Brakensiek, J. and Guruswami, V., Promise constraint satisfaction: Algebraic structure and a symmetric Boolean dichotomy, SIAM J. Comput., 50 (2021), pp. 1663-1700, doi:10.1137/19M128212X. · Zbl 1494.68094 |
| [17] | Brakensiek, J. and Guruswami, V., The quest for strong inapproximability results with perfect completeness, ACM Trans. Algorithms, 17 (2021), 17, doi:10.1145/3459668. · Zbl 07475107 |
| [18] | Brakensiek, J., Guruswami, V., Wrochna, M., and Živný, S., The power of the combined basic linear programming and affine relaxation for promise constraint satisfaction problems, SIAM J. Comput., 49 (2020), pp. 1232-1248, doi:10.1137/20M1312745. · Zbl 1496.68255 |
| [19] | Brandts, A., Wrochna, M., and Živný, S., The complexity of promise SAT on non-Boolean domains, ACM Trans. Comput. Theory, 13 (2021), 26, doi:10.1145/3470867. · Zbl 1495.68157 |
| [20] | Briceño, R., Bulatov, A. A., Dalmau, V., and Larose, B., Dismantlability, connectedness, and mixing in relational structures, J. Combin. Theory Ser. B, 147 (2021), pp. 37-70, doi:10.1016/j.jctb.2020.10.001. · Zbl 1503.08002 |
| [21] | Bulatov, A., Jeavons, P., and Krokhin, A., Classifying the complexity of constraints using finite algebras, SIAM J. Comput., 34 (2005), pp. 720-742, doi:10.1137/S0097539700376676. · Zbl 1071.08002 |
| [22] | Bulatov, A. A., A dichotomy theorem for nonuniform CSPs, in Proceedings of the 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), , IEEE Computer Society, Los Alamitos, CA, 2017, pp. 319-330, doi:10.1109/FOCS.2017.37. |
| [23] | Bulín, J., Krokhin, A., and Opršal, J., Algebraic approach to promise constraint satisfaction, in Proceedings of the 51st Annual ACM SIGACT Symposium on the Theory of Computing (STOC ’1409), , ACM, New York, 2019, pp. 602-613, doi:10.1145/3313276.3316300. · Zbl 1433.68271 |
| [24] | Csorba, P., On the simple \(\mathbb{Z}_2\) -homotopy types of graph complexes and their simple \(\mathbb{Z}_2\) -universality, Canad. Math. Bull., 51 (2008), pp. 535-544, doi:10.4153/CMB-2008-053-9. · Zbl 1169.57022 |
| [25] | Dinur, I., The PCP theorem by gap amplification, J. ACM, 54 (2007), 12, doi:10.1145/1236457.1236459. · Zbl 1292.68074 |
| [26] | Dinur, I., Khot, S., Kindler, G., Minzer, D., and Safra, M., Towards a proof of the 2-to-1 games conjecture?, in Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC’18), , ACM, New York, 2018, pp. 376-389, doi:10.1145/3188745.3188804. · Zbl 1429.68076 |
| [27] | Dinur, I., Mossel, E., and Regev, O., Conditional hardness for approximate coloring, SIAM J. Comput., 39 (2009), pp. 843-873, doi:10.1137/07068062X. · Zbl 1192.68317 |
| [28] | Dinur, I., Regev, O., and Smyth, C., The hardness of 3-uniform hypergraph coloring, Combinatorica, 25 (2005), pp. 519-535, doi:10.1007/s00493-005-0032-4. · Zbl 1106.68080 |
| [29] | Dinur, I. and Shinkar, I., On the conditional hardness of coloring a 4-colorable graph with super-constant number of colors, in Proceedings of the 13th International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques and the 14th International Workshop on Randomization and Computation (APPROX-RANDOM’10), , , Springer, 2010, pp. 138-151, https://link.springer.com/chapter/10.1007/978-3-642-15369-3_11. · Zbl 1304.68060 |
| [30] | Feder, T. and Vardi, M. Y., The computational structure of monotone monadic SNP and constraint satisfaction: A study through datalog and group theory, SIAM J. Comput., 28 (1998), pp. 57-104, doi:10.1137/S0097539794266766. · Zbl 0914.68075 |
| [31] | Ficak, M., Kozik, M., Olšák, M., and Stankiewicz, S., Dichotomy for symmetric Boolean PCSPs, in Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP’19), , , Schloss Dagstuhl, Wadern, Germany, 2019, 57, doi:10.4230/LIPIcs.ICALP.2019.57. · Zbl 07561550 |
| [32] | Foniok, J. and Tardif, C., Adjoint Functors in Graph Theory, preprint, arXiv:1304.2215, 2013. |
| [33] | Foniok, J. and Tardif, C., Digraph functors which admit both left and right adjoints, Discrete Math., 338 (2015), pp. 527-535, doi:10.1016/j.disc.2014.10.018. · Zbl 1305.05087 |
| [34] | Foniok, J. and Tardif, C., Hedetniemi’s conjecture and adjoint functors in thin categories, Appl. Categ. Structures, 26 (2018), pp. 113-128, doi:10.1007/s10485-017-9484-0. · Zbl 1431.05067 |
| [35] | Garey, M. R. and Johnson, D. S., The complexity of near-optimal graph coloring, J. ACM, 23 (1976), pp. 43-49, doi:10.1145/321921.321926. · Zbl 0322.05111 |
| [36] | Geiger, D., Closed systems of functions and predicates, Pacific J. Math., 27 (1968), pp. 95-100. · Zbl 0186.02502 |
| [37] | Greenwell, D. L. and Lovász, L., Applications of product colouring, Acta Math. Acad. Sci. Hungar., 25 (1974), pp. 335-340, doi:10.1007/BF01886093. · Zbl 0294.05108 |
| [38] | Guruswami, V. and Khanna, S., On the hardness of 4-coloring a 3-colorable graph, SIAM J. Discrete Math., 18 (2004), pp. 30-40, doi:10.1137/S0895480100376794. · Zbl 1087.68071 |
| [39] | Guruswami, V. and Lee, E., Strong inapproximability results on balanced rainbow-colorable hypergraphs, Combinatorica, 38 (2018), pp. 547-599, doi:10.1007/s00493-016-3383-0. · Zbl 1424.05087 |
| [40] | Guruswami, V. and Sandeep, S., d-to-1 hardness of coloring 3-colorable graphs with O(1) colors, in Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), Leibniz Int. ProcInform 168, Dagstuhl, Germany, 2020, , Schloss Dagstuhl, Wadern, Germany, 2020, 62, doi:10.4230/LIPIcs.ICALP.2020.62. |
| [41] | Guruswami, V. and Sandeep, S., Rainbow coloring hardness via low sensitivity polymorphisms, SIAM J. Discrete Math., 34 (2020), pp. 520-537, doi:10.1137/19M127731X. · Zbl 1448.68356 |
| [42] | Harner, C. C. and Entringer, R. C., Arc colorings of digraphs, J. Combin. Theory Ser. B, 13 (1972), pp. 219-225, doi:10.1016/0095-8956(72)90057-3. · Zbl 0231.05105 |
| [43] | Hatcher, A., Algebraic Topology, Cambridge University Press, Cambridge, 2001. |
| [44] | Hell, P. and Nešetřil, J., On the complexity of H-coloring, J. Combin. Theory Ser. B, 48 (1990), pp. 92-110, doi:10.1016/0095-8956(90)90132-J. · Zbl 0639.05023 |
| [45] | Hell, P. and Nešetřil, J., Graphs and Homomorphisms, Oxford University Press, Oxford, 2004. · Zbl 1062.05139 |
| [46] | Huang, S., Improved hardness of approximating chromatic number, in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques: 16th International Workshop, APPROX 2013, and 17th International Workshop, RANDOM 2013, Berkeley, CA, , Springer, Berlin, 2013, pp. 233-243, doi:10.1007/978-3-642-40328-6_17. · Zbl 1407.68195 |
| [47] | Jeavons, P., Cohen, D. A., and Gyssens, M., Closure properties of constraints, J. ACM, 44 (1997), pp. 527-548, doi:10.1145/263867.263489. · Zbl 0890.68064 |
| [48] | Kawarabayashi, K. and Thorup, M., Coloring 3-colorable graphs with less than \(n^{1/5}\) colors, J. ACM, 64 (2017), 4, doi:10.1145/3001582. · Zbl 1426.05166 |
| [49] | Khanna, S., Linial, N., and Safra, S., On the hardness of approximating the chromatic number, Combinatorica, 20 (2000), pp. 393-415, doi:10.1007/s004930070013. · Zbl 0964.68065 |
| [50] | Khot, S., Improved inaproximability results for maxclique, chromatic number and approximate graph coloring, in Proceedings of the 42nd Annual Symposium on Foundations of Computer Science (FOCS’01), , IEEE Computer Society, Los Alamitos, CA, 2001, pp. 600-609, doi:10.1109/SFCS.2001.959936. |
| [51] | Khot, S., On the power of unique 2-prover 1-round games, in Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC’02), , ACM, New York, 2002, pp. 767-775, doi:10.1145/509907.510017. · Zbl 1192.68367 |
| [52] | Khot, S., Minzer, D., and Safra, M., Pseudorandom sets in Grassmann graph have near-perfect expansion, in Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science (FOCS’18), , IEEE Computer Society, Los Alamitos, CA, 2018, pp. 592-601, doi:10.1109/FOCS.2018.00062. |
| [53] | Kozlov, D., Combinatorial Algebraic Topology, , Springer, Berlin, 2008, doi:10.1007/978-3-540-71962-5. · Zbl 1130.55001 |
| [54] | Krokhin, A. and Opršal, J., The complexity of 3-colouring H-colourable graphs, in Proceedings of the 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS’19), , IEEE, Piscataway, NJ, 2019, pp. 1227-1239, doi:10.1109/FOCS.2019.00076. |
| [55] | Krokhin, A. and Živný, S., The Constraint Satisfaction Problem: Complexity and Approximability, , Schloss Dagstuhl, Wadern, Germany2017, doi:10.4230/DFU.Vol7.15301. |
| [56] | Larose, B., Loten, C., and Tardif, C., A characterisation of first-order constraint satisfaction problems, Log. Methods Comput. Sci., 3 (2007), doi:10.2168/LMCS-3(4:6)2007. · Zbl 1131.68098 |
| [57] | Lovász, L., Kneser’s conjecture, chromatic number, and homotopy, J. Combin. Theory Ser. A, 25 (1978), pp. 319-324, doi:10.1016/0097-3165(78)90022-5. · Zbl 0418.05028 |
| [58] | Matoušek, J. and Ziegler, G., Topological lower bounds for the chromatic number: A hierarchy, Jahresber. Dtsch. Math.-Ver., 106 (2004), pp. 71-90. · Zbl 1063.05047 |
| [59] | Matoušek, J., Using the Borsuk-Ulam Theorem, Lectures on Topological Methods in Combinatorics and Geometry, 1st ed., Springer, Berlin, 2003, doi:10.1007/978-3-540-76649-0. · Zbl 1016.05001 |
| [60] | Matsushita, T., Box complexes and homotopy theory of graphs, Homology Homotopy Appl., 19 (2017), pp. 175-197. · Zbl 1400.55010 |
| [61] | Matsushita, T., \( \mathbb{Z}_2\) -indices and Hedetniemi’s conjecture, Discrete Comput. Geom., 62 (2019), pp. 662-673, doi:10.1007/s00454-019-00090-1. · Zbl 1422.55038 |
| [62] | Olšák, M., Loop conditions for strongly connected digraphs, Internat. J. Algebra Comput., 30 (2020), pp. 467-499, doi:10.1142/S0218196720500083. · Zbl 1454.08006 |
| [63] | Pippenger, N., Galois theory for minors of finite functions, Discrete Math., 254 (2002), pp. 405-419, doi:10.1016/S0012-365X(01)00297-7. · Zbl 1010.06012 |
| [64] | Poljak, S., Coloring digraphs by iterated antichains, Comment. Math. Univ. Carolin., 32 (1991), pp. 209-212, http://eudml.org/doc/247261. · Zbl 0758.05053 |
| [65] | Poljak, S. and Rödl, V., On the arc-chromatic number of a digraph, J. Combin. Theory Ser. B, 31 (1981), pp. 190-198, doi:10.1016/S0095-8956(81)80024-X. · Zbl 0472.05024 |
| [66] | Reingold, O., Undirected connectivity in log-space, J. ACM, 55 (2008), 17, doi:10.1145/1391289.1391291. · Zbl 1315.68156 |
| [67] | Shitov, Y., Counterexamples to Hedetniemi’s conjecture, Ann. Math. (2), 190 (2019), pp. 663-667, doi:10.4007/annals.2019.190.2.6. · Zbl 1451.05087 |
| [68] | Tardif, C., Hedetniemi’s conjecture, 40 years later, Graph Theory Notes NY, 54 (2008), pp. 46-57, https://mast.queensu.ca/ ctardif/articles/gtn5406rp.pdf. |
| [69] | Tardif, C. and Wrochna, M., Hedetniemi’s conjecture and strongly multiplicative graphs, SIAM J. Discrete Math., 33 (2019), pp. 2218-2250, doi:10.1137/19M1245013. · Zbl 1427.05090 |
| [70] | Wrochna, M., Square-free graphs are multiplicative, J. Combin. Theory Ser. B, 122 (2017), pp. 479-507, doi:10.1016/j.jctb.2016.07.007. · Zbl 1350.05074 |
| [71] | Wrochna, M., On inverse powers of graphs and topological implications of Hedetniemi’s conjecture, J. Combin. Theory Ser. B, 139 (2019), pp. 267-295, doi:10.1016/j.jctb.2019.02.008. · Zbl 1428.05259 |
| [72] | Wrochna, M., Homomorphism reconfiguration via homotopy, SIAM J. Discrete Math., 34 (2020), pp. 328-350, doi:10.1137/17M1122578. · Zbl 1448.68249 |
| [73] | Wrochna, M. and Živný, S., Improved hardness for H-colourings of G-colourable graphs, in Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’20), , SIAM, Philadelphia, 2020, pp. 1426-1435, doi:10.1137/1.9781611975994.86. · Zbl 1502.68136 |
| [74] | Zhu, X., A survey on Hedetniemi’s conjecture, Taiwanese J. Math., 2 (1998), pp. 1-24, http://www.jstor.org/stable/43834380. · Zbl 0906.05024 |
| [75] | Zhuk, D., A proof of CSP dichotomy conjecture, in Proceedings of the 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS’17), , IEEE Computer Society, Los Alamitos, CA, 2017, pp. 331-342, doi:10.1109/FOCS.2017.38. |
| [76] | Zhuk, D., A proof of the CSP dichotomy conjecture, J. ACM, 67 (2020), 30, doi:10.1145/3402029. · Zbl 1491.68128 |
| [77] | Živaljević, R. T., WI-posets, graph complexes and \(\mathbb{Z}_2\) -equivalences, J. Combin. Theory Ser. A, 111 (2005), pp. 204-223, doi:10.1016/j.jcta.2004.12.002. · Zbl 1074.05091 |
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.
