×

The power of Sherali-Adams relaxations for general-valued CSPs. (English) Zbl 1371.68125

Summary: We give a precise algebraic characterization of the power of Sherali-Adams relaxations for solvability of valued constraint satisfaction problems (CSPs) to optimality. The condition is that of bounded width, which has already been shown to capture the power of local consistency methods for decision CSPs and the power of semidefinite programming for robust approximation of CSPs. Our characterization has several algorithmic and complexity consequences. On the algorithmic side, we show that several novel and well-known valued constraint languages are tractable via the third level of the Sherali-Adams relaxation. For the known languages, this is a significantly simpler algorithm than those previously obtained. On the complexity side, we obtain a dichotomy theorem for valued constraint languages that can express an injective unary function. This implies a simple proof of the dichotomy theorem for conservative valued constraint languages established by V. Kolmogorov and the second author [J. ACM 60, No. 2, Article No. 10, 38 p. (2013; Zbl 1281.68134)], and also a dichotomy theorem for the exact solvability of minimum-solution problems. These are generalizations of minimum-ones problems to arbitrary finite domains. Our result improves on several previous classifications by S. Khanna et al. [SIAM J. Comput. 30, No. 6, 1863–1920 (2001; Zbl 0992.68059)], P. Jonsson et al. [SIAM J. Comput. 38, No. 1, 329–365 (2008; Zbl 1162.68015)], and H. Uppman [Lect. Notes Comput. Sci. 7965, 804–815 (2013; Zbl 1336.68148)].

MSC:

68Q25 Analysis of algorithms and problem complexity
08A70 Applications of universal algebra in computer science
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Software:

JBool
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] M. Alekhnovich, S. Arora, and I. Tourlakis, {\it Towards strong nonapproximability results in the Lovász-Schrijver hierarchy}, Comput. Complex., 20 (2011), pp. 615-648, . · Zbl 1252.68131
[2] A. Atserias, A. Bulatov, and A. Dawar, {\it Affine systems of equations and counting infinitary logic}, Theoret. Comput. Sci., 410 (2009), pp. 1666-1683. · Zbl 1168.68040
[3] B. Barak and D. Steurer, {\it Sum-of-squares proofs and the quest toward optimal algorithms}, in Proceedings of International Congress of Mathematicians (ICM), Seoul, South Korea, 2014. · Zbl 1373.68253
[4] L. Barto, {\it The collapse of the bounded width hierarchy}, J. Logic Comput., 26 (2016), pp. 923-943, . · Zbl 1353.68107
[5] L. Barto and M. Kozik, {\it Constraint satisfaction problems solvable by local consistency methods}, J. ACM, 61 (2014), 3, . · Zbl 1295.68126
[6] L. Barto and M. Kozik, {\it Robustly solvable constraint satisfaction problems}, SIAM J. Comput., 45 (2016), pp. 1646-1669, . · Zbl 1350.68127
[7] M. Bodirsky, {\it Constraint satisfaction problems with infinite templates}, in Complexity of Constraints, Lecture Notes in Comput. Sci. 5250, Springer, Berlin, 2008, pp. 196-228, . · Zbl 1171.03320
[8] E. Boros and P. L. Hammer, {\it Pseudo-Boolean optimization}, Discrete Appl. Math., 123 (2002), pp. 155-225, . · Zbl 1076.90032
[9] A. Bulatov, {\it Combinatorial problems raised from 2-semilattices}, J. Algebra, 298 (2006), pp. 321-339, . · Zbl 1110.08001
[10] A. Bulatov, {\it Bounded Relational Width}, manuscript, 2009.
[11] A. Bulatov, P. Jeavons, and A. Krokhin, {\it Classifying the complexity of constraints using finite algebras}, SIAM J. Comput., 34 (2005), pp. 720-742, . · Zbl 1071.08002
[12] A. A. Bulatov, {\it Complexity of conservative constraint satisfaction problems}, ACM Trans. Comput. Logic, 12 (2011), 24, . · Zbl 1351.68113
[13] A. A. Bulatov, {\it Graphs of relational structures: Restricted types}, in Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science (LICS’16), ACM, New York, 2016, pp. 642-651, . · Zbl 1401.68112
[14] S. O. Chan, J. R. Lee, P. Raghavendra, and D. Steurer, {\it Approximate constraint satisfaction requires large LP relaxations}, J. ACM, 63 (2016), 34, . · Zbl 1394.68170
[15] M. Charikar, K. Makarychev, and Y. Makarychev, {\it Near-optimal algorithms for maximum constraint satisfaction problems}, ACM Trans. Algorithms, 5 (2009), 32, . · Zbl 1298.68111
[16] C. Chekuri, S. Khanna, J. Naor, and L. Zosin, {\it A linear programming formulation and approximation algorithms for the metric labeling problem}, SIAM J. Discrete Math., 18 (2005), pp. 608-625, . · Zbl 1077.68036
[17] E. Chlamtáč and M. Tulsiani, {\it Convex relaxations and integrality gaps}, in Handbook on Semidefinite, Conic and Polynomial Optimization, M. F. Anjos and J. B. Lasserre, eds., Internat. Ser. Oper. Res. Manage. Sci. 166, Springer, Berlin, 2012, pp. 139-169, . · Zbl 1334.90099
[18] D. A. Cohen, M. C. Cooper, P. Creed, P. G. Jeavons, and S. Živný, {\it An algebraic theory of complexity for discrete optimization}, SIAM J. Comput., 42 (2013), pp. 1915-1939, , . · Zbl 1305.08007
[19] D. A. Cohen, M. C. Cooper, and P. G. Jeavons, {\it Generalising submodularity and Horn clauses: Tractable optimization problems defined by tournament pair multimorphisms}, Theoret. Comput. Sci., 401 (2008), pp. 36-51, . · Zbl 1154.90011
[20] D. A. Cohen, M. C. Cooper, P. G. Jeavons, and A. A. Krokhin, {\it The complexity of soft constraint satisfaction}, Artificial Intell., 170 (2006), pp. 983-1016, . · Zbl 1131.68520
[21] D. A. Cohen, M. C. Cooper, P. G. Jeavons, A. A. Krokhin, R. Powell, and S. Živný, {\it Binarisation for Valued Constraint Satisfaction Problems}, preprint, , 2016. · Zbl 1477.68121
[22] Y. Crama and P. L. Hammer, {\it Boolean Functions–Theory, Algorithms, and Applications}, Cambridge University Press, Cambridge, UK, 2011. · Zbl 1237.06001
[23] N. Creignou, {\it A dichotomy theorem for maximum generalized satisfiability problems}, J. Comput. Syst. Sci., 51 (1995), pp. 511-522, . · Zbl 1294.68090
[24] N. Creignou, S. Khanna, and M. Sudan, {\it Complexity Classification of Boolean Constraint Satisfaction Problems}, Discrete Math. Appl. 7, SIAM, Philadelphia, 2001, . · Zbl 0981.68058
[25] V. Dalmau, {\it There are no pure relational width \(2\) constraint satisfaction problems}, Inform. Process. Lett., 109 (2009), pp. 213-218, . · Zbl 1191.68339
[26] V. Dalmau, A. Krokhin, and R. Manokaran, {\it Towards a characterization of constant-factor approximable Min CSPs}, in Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’15), ACM, New York, SIAM, Philadelphia, 2015, pp. 847-857, . · Zbl 1371.90116
[27] V. Dalmau and A. A. Krokhin, {\it Robust satisfiability for CSPs: Hardness and algorithmic results}, ACM Trans. Comput. Theory, 5 (2013), 15, . · Zbl 1322.68099
[28] W. F. de la Vega and C. Kenyon-Mathieu, {\it Linear programming relaxations of maxcut}, in Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’07), ACM, New York, SIAM, Philadelphia, 2007, pp. 53-61. · Zbl 1302.90176
[29] A. Ene, J. Vondrák, and Y. Wu, {\it Local distribution and the symmetry gap: Approximability of multiway partitioning problems}, in Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’13), ACM, New York, SIAM, Philadelphia, 2013, pp. 306-325, . · Zbl 1421.68217
[30] T. Feder and M. Y. Vardi, {\it 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, . · Zbl 0914.68075
[31] P. Fulla and S. Živný, {\it A Galois connection for weighted (relational) clones of infinite size}, ACM Trans. Comput. Theory, 8 (2016), 9, , . · Zbl 1427.68120
[32] K. Georgiou, A. Magen, T. Pitassi, and I. Tourlakis, {\it Integrality gaps of 2-o(1) for vertex cover SDPs in the Lovász-Schrijver hierarchy}, SIAM J. Comput., 39 (2010), pp. 3553-3570, . · Zbl 1209.68268
[33] D. Grigoriev, {\it Linear lower bound on degrees of Positivstellensatz calculus proofs for the}{\it parity}, Theor. Comput. Sci., 259 (2001), pp. 613-622, . · Zbl 0974.68192
[34] H. Hirai, {\it Discrete convexity and polynomial solvability in minimum 0-extension problems}, Math. Program., 155 (2016), pp. 1-55, . · Zbl 1342.90163
[35] D. Hobby and R. McKenzie, {\it The Structure of Finite Algebras}, Contemp. Math. 76, American Mathematical Society, Providence, RI, 1988. · Zbl 0721.08001
[36] A. Huber, A. Krokhin, and R. Powell, {\it Skew bisubmodularity and valued CSPs}, SIAM J. Comput., 43 (2014), pp. 1064-1084, . · Zbl 1360.68512
[37] Y. Iwata, M. Wahlström, and Y. Yoshida, {\it Half-integrality, LP-branching, and FPT algorithms}, SIAM J. Comput., 45 (2016), pp. 1377-1411, . · Zbl 1343.05151
[38] P. Jeavons, D. A. Cohen, and M. Gyssens, {\it Closure properties of constraints}, J. ACM, 44 (1997), pp. 527-548, . · Zbl 0890.68064
[39] P. Jonsson, F. Kuivinen, and G. Nordh, {\it MAX ONES generalized to larger domains}, SIAM J. Comput., 38 (2008), pp. 329-365, . · Zbl 1162.68015
[40] P. Jonsson and G. Nordh, {\it Introduction to the maximum solution problem}, in Complexity of Constraints, Lecture Notes in Comput. Sci. 5250, Springer, Berlin, 2008, pp. 255-282, . · Zbl 1171.68499
[41] P. Jonsson, G. Nordh, and J. Thapper, {\it The maximum solution problem on graphs}, in Proceedings of the 32nd International Symposium on Mathematical Foundations of Computer Science (MFCS’07), Lecture Notes in Comput. Sci. 4708, Springer, Berlin, 2007, pp. 228-239, . · Zbl 1147.68532
[42] S. Khanna, M. Sudan, L. Trevisan, and D. P. Williamson, {\it The approximability of constraint satisfaction problems}, SIAM J. Comput., 30 (2001), pp. 1863-1920, . · Zbl 0992.68059
[43] V. Kolmogorov, A. A. Krokhin, and M. Rolínek, {\it The complexity of general-valued CSPs}, in Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS’15), IEEE Computer Society, Washington, DC, 2015, pp. 1246-1258. · Zbl 1371.68117
[44] V. Kolmogorov, J. Thapper, and S. Živný, {\it The power of linear programming for general-valued CSPs}, SIAM J. Comput., 44 (2015), pp. 1-36, . · Zbl 1456.68059
[45] V. Kolmogorov and S. Živný, {\it The complexity of conservative valued CSPs}, J. ACM, 60 (2013), 10, , . · Zbl 1281.68134
[46] M. Kozik, A. Krokhin, M. Valeriote, and R. Willard, {\it Characterizations of several Maltsev Conditions}, Algebra Universalis, 73 (2015), pp. 205-224. · Zbl 1319.08002
[47] M. Kozik and J. Ochremiak, {\it Algebraic properties of valued constraint satisfaction problem}, in Proceedings of the 42nd International Colloquium on Automata, Languages and Programming (ICALP’15), Lecture Notes in Comput. Sci. 9134, Springer, Berlin, 2015, pp. 846-858, . · Zbl 1441.68098
[48] A. Krokhin and S. Živný, {\it The complexity of valued CSPs}, in Complexity and Approximability of Constraint Satisfaction Problems, Dagstuhl Follow-Ups 7, A. Krokhin and S. Živný, eds., Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2017, pp. 233-266, . · Zbl 1482.68165
[49] A. Kumar, R. Manokaran, M. Tulsiani, and N. K. Vishnoi, {\it On LP-based approximability for strict CSPs}, in Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’11), ACM, New York, SIAM, Philadelphia, 2011, pp. 1560-1573, . · Zbl 1377.90077
[50] G. Kun, R. O’Donnell, S. Tamaki, Y. Yoshida, and Y. Zhou, {\it Linear programming, width-\(1\) CSPs, and robust satisfaction}, in Proceedings of the 3rd Innovations in Theoretical Computer Science (ITCS’12), ACM, New York, 2012, pp. 484-495, . · Zbl 1347.68184
[51] G. Kun and M. Szegedy, {\it A new line of attack on the dichotomy conjecture}, European J. Combin., 52 (2016), pp. 338-367, . · Zbl 1327.05183
[52] B. Larose and L. Zádori, {\it Bounded width problems and algebras}, Algebra Universalis, 56 (2007), pp. 439-466. · Zbl 1120.08002
[53] J. B. Lasserre, {\it Global optimization with polynomials and the problem of moments}, SIAM J. Optim., 11 (2001), pp. 796-817, . · Zbl 1010.90061
[54] M. Laurent, {\it A comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre relaxations for \(0--1\) programming}, Math. Oper. Res., 28 (2003), pp. 470-496, . · Zbl 1082.90084
[55] L. Lovász and A. Schrijver, {\it Cones of matrices and set-functions and 0-1 optimization}, SIAM J. Optim., 1 (1991), pp. 166-190, . · Zbl 0754.90039
[56] M. Maróti and R. McKenzie, {\it Existence theorems for weakly symmetric operations}, Algebra Universalis, 59 (2008), pp. 463-489, . · Zbl 1186.08003
[57] P. Raghavendra, {\it Optimal algorithms and inapproximability results for every CSP?}, in Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC’08), ACM, New York, 2008, pp. 245-254, . · Zbl 1231.68142
[58] G. Schoenebeck, {\it Linear level Lasserre lower bounds for certain k-CSPs}, in Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS’08), IEEE Computer Society, Washington, DC, 2008, pp. 593-602, .
[59] G. Schoenebeck, L. Trevisan, and M. Tulsiani, {\it A linear round lower bound for Lovász-Schrijver SDP relaxations of vertex cover}, in Proceedings of the 22nd Annual IEEE Conference on Computational Complexity (CCC’07), IEEE Computer Society, Washington, DC, 2007, pp. 205-216, . · Zbl 1232.90303
[60] H. D. Sherali and W. P. Adams, {\it A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems}, SIAM J. Discrete Math., 3 (1990), pp. 411-430, . · Zbl 0712.90050
[61] R. Takhanov, {\it A dichotomy theorem for the general minimum cost homomorphism problem}, in Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science (STACS’10), Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2010, pp. 657-668, . · Zbl 1230.90192
[62] J. Thapper, {\it Aspects of a Constraint Optimisation Problem}, Ph.D. thesis, Department of Computer Science and Information Science, Linköping University, Linköping, Sweden, 2010.
[63] J. Thapper and S. Živný, {\it The power of linear programming for valued CSPs}, in Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS’12), IEEE Computer Society, Washington, DC, 2012, pp. 669-678, , .
[64] J. Thapper and S. Živný, {\it Necessary conditions for tractability of valued CSPs}, SIAM J. Discrete Math., 29 (2015), pp. 2361-2384, . · Zbl 1347.08009
[65] J. Thapper and S. Živný, {\it Sherali-Adams relaxations for valued CSPs}, in Proceedings of the 42nd International Colloquium on Automata, Languages and Programming (ICALP’15), Lecture Notes in Comput. Sci. 9134, Springer, Berlin, 2015, pp. 1058-1069, , . · Zbl 1440.68132
[66] J. Thapper and S. Živný, {\it The complexity of finite-valued CSPs}, J. ACM, 63 (2016), 37, , . · Zbl 1294.68094
[67] M. Tulsiani, {\it CSP gaps and reductions in the Lasserre hierarchy}, in Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC’09), ACM, New York, 2009, pp. 303-312, . · Zbl 1304.90157
[68] H. Uppman, {\it The Complexity of three-element Min-Sol and conservative Min-Cost-Hom}, in Proceedings of the 40th International Colloquium on Automata, Languages, and Programming (ICALP’13), Lecture Notes in Comput. Sci. 7965, Springer, Berlin, 2013, pp. 804-815, . · Zbl 1336.68148
[69] H. Uppman, {\it On Some Combinatorial Optimization Problems}, Ph.D. thesis, Department of Computer Science and Information Science, Linköping University, Linköping, Sweden, 2015.
[70] Y. Yoshida and Y. Zhou, {\it Approximation schemes via Sherali-Adams hierarchy for dense constraint satisfaction problems and assignment problems}, in Innovations in Theoretical Computer Science (ITCS’14), ACM, New York, 2014, pp. 423-438, . · Zbl 1366.68369
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.