CLAP: a new algorithm for promise CSPs. (English) Zbl 07672223
Summary: We propose a new algorithm for Promise Constraint Satisfaction Problems (PCSPs). It is a combination of the Constraint Basic LP relaxation and the Affine IP relaxation (CLAP). We give a characterization of the power of CLAP in terms of a minion homomorphism. Using this characterization, we identify a certain weak notion of symmetry which, if satisfied by infinitely many polymorphisms of PCSPs, guarantees tractability. We demonstrate that there are PCSPs solved by CLAP that are not solved by any of the existing algorithms for PCSPs; in particular, not by the BLP + AIP algorithm of Brakensiek et al. [SIAM J. Comput., 49 (2020), pp. 1232-1248] and not by a reduction to tractable finite-domain CSPs.
MSC:
| 68Q25 | Analysis of algorithms and problem complexity |
| 68R01 | General topics of discrete mathematics in relation to computer science |
| 90C05 | Linear programming |
References:
| [1] | Arora, S., Lund, C., Motwani, R., Sudan, M., and Szegedy, M., Proof verification and the hardness of approximation problems, J. ACM, 45 (1998), pp. 501-555, doi:10.1145/278298.278306. · Zbl 1065.68570 |
| [2] | Arora, S. and Safra, S., Probabilistic checking of proofs: A new characterization of NP, J. ACM, 45 (1998), pp. 70-122, doi:10.1145/273865.273901. · Zbl 0903.68076 |
| [3] | Atserias, A. and Dalmau, V., Promise constraint satisfaction and width, in Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms (SODA’22), , 2022, pp. 1129-1153, doi:10.1137/1.9781611977073.48. · Zbl 07883629 |
| [4] | Austrin, P., Bhangale, A., and Potukuchi, A., Improved inapproximability of rainbow coloring, in Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA’20), , 2020, pp. 1479-1495, doi:10.1137/1.9781611975994.90. · Zbl 07304113 |
| [5] | 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 |
| [6] | Barto, L., The collapse of the bounded width hierarchy, J. Log. Comput., 26 (2016), pp. 923-943, doi:10.1093/logcom/exu070. · Zbl 1353.68107 |
| [7] | Barto, L., Battistelli, D., and Berg, K. M., Symmetric promise constraint satisfaction problems: Beyond the Boolean case, in Proceedings of the 38th International Symposium on Theoretical Aspects of Computer Science (STACS’21), , , Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2021, 10, doi:10.4230/LIPIcs.STACS.2021.10. |
| [8] | Barto, L., Bulín, J., Krokhin, A. A., and Opršal, J., Algebraic approach to promise constraint satisfaction, J. ACM, 68 (2021), 28, doi:10.1145/3457606. · Zbl 1499.68140 |
| [9] | Barto, L. and Kozik, M., Constraint satisfaction problems solvable by local consistency methods, J. ACM, 61 (2014), 3, doi:10.1145/2556646. · Zbl 1295.68126 |
| [10] | 9Barto, L. and Kozik, M., Robustly solvable constraint satisfaction problems, SIAM J. Comput., 45 (2016), pp. 1646-1669, doi:10.1137/130915479. · Zbl 1350.68127 |
| [11] | Barto, L., Krokhin, A., and Willard, R., Polymorphisms, and how to use them, in The Constraint Satisfaction Problem: Complexity and Approximability, Krokhin, A., and Živný, S., , Schloss Dagstuhl. Leibniz-Zent. Inform., Dagstuhl, Germany, 2017, pp. 1-44, doi:10.4230/DFU.Vol7.15301.1. · Zbl 1482.68161 |
| [12] | Barto, L., Opršal, J., and Pinsker, M., The wonderland of reflections, Isr. J. Math., 223 (2018), pp. 363-398, doi:10.1007/s11856-017-1621-9. · Zbl 1397.08002 |
| [13] | Barto, L. and Pinsker, M., Topology is irrelevant (in a dichotomy conjecture for infinite domain constraint satisfaction problems), SIAM J. Comput., 49 (2020), pp. 365-393, doi:10.1137/18M1216213. · Zbl 1432.68169 |
| [14] | Berman, J., Idziak, P., Marković, P., McKenzie, R., Valeriote, M., and Willard, R., Varieties with few subalgebras of powers, Trans. Amer. Math. Soc., 362 (2010), pp. 1445-1473. · Zbl 1190.08004 |
| [15] | Bessiere, C. and Debruyne, R., Theoretical analysis of singleton arc consistency and its extensions, Artif. Intell., 172 (2008), pp. 29-41, doi:10.1016/j.artint.2007.09.001. · Zbl 1182.68217 |
| [16] | Blum, A., New approximation algorithms for graph coloring, J. ACM, 41 (1994), pp. 470-516, doi:10.1145/176584.176586. · Zbl 0821.68092 |
| [17] | Bodirsky, M., Martin, B., and Mottet, A., Discrete temporal constraint satisfaction problems, J. ACM, 65 (2018), 9, doi:10.1145/3154832. · Zbl 1425.68135 |
| [18] | Bodirsky, M., Mottet, A., Olšák, M., Opršal, J., Pinsker, M., and Willard, R., \( \omega \) -categorical structures avoiding height 1 identities, Trans. Amer. Math. Soc., 374 (2021), pp. 327-350, doi:10.1090/tran/8179. · Zbl 1472.08006 |
| [19] | Brakensiek, J. and Guruswami, V., An algorithmic blend of LPs and ring equations for promise CSPs, in Proceedings of the 2019 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’19), , SIAM, Philadelphia, 2019, pp. 436-455, doi:10.1137/1.9781611975482.28. · Zbl 1431.68043 |
| [20] | 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 |
| [21] | Brakensiek, J., Guruswami, V., and Sandeep, S., Conditional dichotomy of Boolean ordered promise CSPs, in Proceedings of the 48th International Colloquium on Automata, Languages, and Programming (ICALP’21), , , Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2021, 37, doi:10.4230/LIPIcs.ICALP.2021.37. |
| [22] | 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 |
| [23] | 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 |
| [24] | Brandts, A. and Živný, S., Beyond PCSP(1-in-3,NAE), Inform. and Comput., 289 (2022), 104954, doi:10.1016/j.ic.2022.104954. · Zbl 07629147 |
| [25] | Bulatov, A., Bounded relational width, unpublished manuscript, 2009, https://www2.cs.sfu.ca/∼abulatov/papers/relwidth.pdf. |
| [26] | 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 |
| [27] | Bulatov, A. A., A dichotomy theorem for constraint satisfaction problems on a 3-element set, J. ACM, 53 (2006), pp. 66-120, doi:10.1145/1120582.1120584. · Zbl 1316.68057 |
| [28] | Bulatov, A. A., A dichotomy theorem for nonuniform CSPs, in Proceedings of the 58th Annual IEEE Symposium on Foundations of Computer Science (FOCS’17), 2017, pp. 319-330, doi:10.1109/FOCS.2017.37. |
| [29] | Bulatov, A. A. and Dalmau, V., A simple algorithm for Mal’tsev constraints, SIAM J. Comput., 36 (2006), pp. 16-27, doi:10.1137/050628957. · Zbl 1112.08002 |
| [30] | Chen, H., Dalmau, V., and Grußien, B., Arc consistency and friends, J. Log. Comput., 23 (2013), pp. 87-108, doi:10.1093/logcom/exr039. · Zbl 1282.68134 |
| [31] | Ciardo, L. and Živný, S., Hierarchies of minion tests for PCSPs through tensors, in Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms (SODA’23), , 2023, to appear, https://arxiv.org/abs/2207.02277. |
| [32] | Ciardo, L. and Živný, S., CLAP: A new algorithm for promise CSPs, in Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms (SODA’22), , SIAM, Philadelphia, 2022, pp. 1057-1068, doi:10.1137/1.9781611977073.46. · Zbl 07883627 |
| [33] | Cohen, D. A., Tractable decision for a constraint language implies tractable search, Constraints, 9 (2004), pp. 219-229, doi:10.1023/B:CONS.0000036045.82829.94. · Zbl 1074.68061 |
| [34] | Dalmau, V., There are no pure relational width 2 constraint satisfaction problems, Inform. Process. Lett., 109 (2009), pp. 213-218, doi:10.1016/j.ipl.2008.10.005. · Zbl 1191.68339 |
| [35] | Dalmau, V., Kozik, M., Krokhin, A. A., Makarychev, K., Makarychev, Y., and Opršal, J., Robust algorithms with polynomial loss for near-unanimity CSPs, SIAM J. Comput., 48 (2019), pp. 1763-1795, doi:10.1137/18M1163932. · Zbl 1452.68087 |
| [36] | Dalmau, V. and Krokhin, A. A., Robust satisfiability for CSPs: Hardness and algorithmic results, ACM Trans. Comput. Theory, 5 (2013), 15, doi:10.1145/2540090. · Zbl 1322.68099 |
| [37] | Dalmau, V. and Pearson, J., Closure functions and width 1 problems, in Proceedings of the 4th International Conference on Principles and Practice of Constraint Programming (CP’99), , , Springer, 1999, pp. 159-173, doi:10.1007/978-3-540-48085-3_12. · Zbl 0957.68081 |
| [38] | Debruyne, R. and Bessière, C., Some practicable ffiltering techniques for the constraint satisfaction problem, in Proceedings of the 15th International Joint Conference on Artificial Intelligence (IJCAI’97), , Morgan Kaufmann, Burlington, MA1997, pp. 412-417. |
| [39] | Dinur, I., The PCP theorem by gap amplification, J. ACM, 54 (2007), 12, doi:10.1145/1236457.1236459. · Zbl 1292.68074 |
| [40] | 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 |
| [41] | 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 |
| [42] | 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. Leibniz-Zent. Inform., Wadern, 2019, 57, doi:10.4230/LIPIcs.ICALP.2019.57. · Zbl 07561550 |
| [43] | 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 |
| [44] | 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 |
| [45] | 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’20), , , Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2020, 62, doi:10.4230/LIPIcs.ICALP.2020.62. |
| [46] | 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 |
| [47] | Horn, R. A. and Johnson, C. R., Matrix Analysis, Cambridge University Press, 2012. |
| [48] | Idziak, P. M., Markovic, P., McKenzie, R., Valeriote, M., and Willard, R., Tractability and learnability arising from algebras with few subpowers, SIAM J. Comput., 39 (2010), pp. 3023-3037, doi:10.1137/090775646. · Zbl 1216.68129 |
| [49] | Jeavons, P. G., On the algebraic structure of combinatorial problems, Theor. Comput. Sci., 200 (1998), pp. 185-204, doi:10.1016/S0304-3975(97)00230-2. · Zbl 0915.68074 |
| [50] | Jeavons, P. G., 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 |
| [51] | 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 |
| [52] | Khot, S., Improved Inaproximability results for MaxClique, chromatic number and approximate graph coloring, in Proceedings of 42nd Annual IEEE Symposium on Foundations of Computer Science (FOCS’01), , IEEE Computer Society, 2001, pp. 600-609, doi:10.1109/SFCS.2001.959936. |
| [53] | 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, 2002, pp. 767-775, doi:10.1145/509907.510017. · Zbl 1192.68367 |
| [54] | Kolmogorov, V., Krokhin, A. A., and Rolínek, M., The complexity of general-valued CSPs, SIAM J. Comput., 46 (2017), pp. 1087-1110, doi:10.1137/16M1091836. · Zbl 1371.68117 |
| [55] | Kolmogorov, V., Thapper, J., and Živný, S., The power of linear programming for general-valued CSPs, SIAM J. Comput., 44 (2015), pp. 1-36, doi:10.1137/130945648. · Zbl 1456.68059 |
| [56] | Kozik, M., Solving CSPs using weak local consistency, SIAM J. Comput., 50 (2021), pp. 1263-1286, doi:10.1137/18M117577X. · Zbl 1522.68241 |
| [57] | Kozik, M. and Ochremiak, J., Algebraic properties of valued constraint satisfaction problem, in Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP’15), , , Springer, 2015, pp. 846-858, doi:10.1007/978-3-662-47672-7_69. · Zbl 1441.68098 |
| [58] | Krokhin, A. and Opršal, J., The complexity of 3-colouring \(H\) -colourable graphs, in Proceedings of the 60th Annual IEEE Symposium on Foundations of Computer Science (FOCS’19), , 2019, pp. 1227-1239, doi:10.1109/FOCS.2019.00076. |
| [59] | Kun, G., O’Donnell, R., Tamaki, S., Yoshida, Y., and Zhou, Y., Linear programming, width-1 CSPs, and robust satisfaction, in Proceedings of the 3rd Innovations in Theoretical Computer Science (ITCS’12), , ACM, 2012, pp. 484-495, doi:10.1145/2090236.2090274. · Zbl 1347.68184 |
| [60] | Kun, G. and Szegedy, M., A new line of attack on the dichotomy conjecture, European J. Combin., 52 (2016), pp. 338-367, doi:10.1016/j.ejc.2015.07.011. · Zbl 1327.05183 |
| [61] | Mackworth, A. K., Consistency in networks of relations, Artif. Intell., 8 (1977), pp. 99-118, doi:10.1016/0004-3702(77)90007-8. · Zbl 0341.68061 |
| [62] | Malcev, A., Untersuchungen aus dem gebiete der mathematischen logik, J. Symbolic Logic, 2 (1937), 84. |
| [63] | Raghavendra, P., Optimal algorithms and inapproximability results for every CSP?, in Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC’08), , 2008, pp. 245-254, doi:10.1145/1374376.1374414. · Zbl 1231.68142 |
| [64] | Rorabaugh, D., Tardif, C., and Wehlau, D. L., Logical compactness and constraint satisfaction problems, Log. Methods Comput. Sci., 13 (2017), doi:10.23638/LMCS-13(1:1)2017. · Zbl 1448.03020 |
| [65] | Schaefer, T., The complexity of satisfiability problems, in Proceedings of the 10th Annual ACM Symposium on the Theory of Computing (STOC’78), , 1978, pp. 216-226, doi:10.1145/800133.804350. · Zbl 1282.68143 |
| [66] | Thapper, J. and Živný, S., The complexity of finite-valued CSPs, J. ACM, 63 (2016), 37, doi:10.1145/2974019. · Zbl 1410.68177 |
| [67] | Thapper, J. and Živný, S., The power of Sherali-Adams relaxations for general-valued CSPs, SIAM J. Comput., 46 (2017), pp. 1241-1279, doi:10.1137/16M1079245. · Zbl 1371.68125 |
| [68] | Thapper, J. and Živný, S., The limits of SDP relaxations for general-valued CSPs, ACM Trans. Comput. Theory, 10 (2018), 12, doi:10.1145/3201777. · Zbl 1427.90245 |
| [69] | Wigderson, A., Improving the performance guarantee for approximate graph coloring, J. ACM, 30 (1983), pp. 729-735, doi:10.1145/2157.2158. · Zbl 0627.68057 |
| [70] | Wrochna, M. and Živný, S., Improved hardness for \(H\) -colourings of \(G\) -colourable graphs, in Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA’20), , SIAM, Philadelphia, 2020, pp. 1426-1435, doi:10.1137/1.9781611975994.86. · Zbl 1502.68136 |
| [71] | Zhuk, D., A proof of the CSP dichotomy conjecture, J. ACM, 67 (2020), 30, doi:10.1145/3402029. · Zbl 1491.68128 |
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.
