zbMATH — the first resource for mathematics

Linear-programming design and analysis of fast algorithms for Max 2-CSP. (English) Zbl 1153.90505
Summary: The class Max \((r,2)\)-CSP, or simply Max 2-CSP, consists of constraint satisfaction problems with at most two \(r\)-valued variables per clause. For instances with \(n\) variables and \(m\) binary clauses, we present an \(O(nr^{5+19m/100})\)-time algorithm which is the fastest polynomial-space algorithm for many problems in the class, including Max Cut. The method also proves a treewidth bound \(\text{tw}(G)\leq(13/75+o(1))m\), which gives a faster Max 2-CSP algorithm that uses exponential space: running in time \(O^\star(2^{(13/75+o(1))m})\), this is fastest for most problems in Max 2-CSP. Parametrizing in terms of \(n\) rather than \(m\), for graphs of average degree \(d\) we show a simple algorithm running time \(O^\star(2^{(1-\frac{2}{d+1})^n})\), the fastest polynomial-space algorithm known.
In combination with ‘Polynomial CSPs’ introduced in a companion paper, these algorithms also allow (with an additional polynomial factor overhead in space and time) counting and sampling, and the solution of problems like Max Bisection that escape the usual CSP framework.
Linear programming is key to the design as well as the analysis of the algorithms.

90C05 Linear programming
05C35 Extremal problems in graph theory
05C85 Graph algorithms (graph-theoretic aspects)
68R10 Graph theory (including graph drawing) in computer science
Full Text: DOI
[1] Alon, N.; Kahn, J.; Seymour, P.D., Large induced degenerate subgraphs, Graphs combin., 3, 3, 203-211, (1987), MR903609 (88i:05104) · Zbl 0624.05039
[2] Arnborg, S.; Hedetniemi, S.T.; Proskurowski, A., Efficient algorithms and partial \(k\)-trees, Discrete appl. math., 54, 2-3, (1994), (special issue)
[3] Arnborg, S.; Proskurowski, A., Linear time algorithms for NP-hard problems restricted to partial \(k\)-trees, Discrete appl. math., 23, 1, 11-24, (1989) · Zbl 0666.68067
[4] Beigel, Richard; Eppstein, David, 3-coloring in time \(O(1.328 9^n)\), J. algorithms, 54, 2, 168-204, (2005) · Zbl 1101.68716
[5] Creignou, Nadia, A dichotomy theorem for maximum generalized satisfiability problems, 24th annual ACM symposium on the theory of computing, Victoria, BC, J. comput. system sci., 51, 3, 511-522, (1995), 1992. MR1368916 (97a:68076) · Zbl 1294.68090
[6] Croce, F. Della; Kaminski, Marcin J.; Paschos, Vangelis Th., An exact algorithm for MAX-CUT in sparse graphs, Oper. res. lett., 35, 3, 403-408, (2007) · Zbl 1163.90767
[7] Vilhelm Dahllöf, Peter Jonsson, An algorithm for counting maximum weighted independent sets and its applications, in: Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, January 2002 · Zbl 1093.68678
[8] Dahllöf, Vilhelm; Jonsson, Peter; Wahlström, Magnus, Counting models for 2SAT and 3SAT formulae, Theoret. comput. sci., 332, 1-3, 265-291, (2005), MR2122506 (2005j:68055) · Zbl 1070.68050
[9] Dechter, R.; Pearl, J., Network-based heuristics for constraint-satisfaction problems, Artif. intell., 34, 1, 1-38, (1987) · Zbl 0643.68156
[10] Dechter, Rina; Pearl, Judea, Tree clustering for constraint networks (research note), Artif. intell., 38, 3, 353-366, (1989) · Zbl 0665.68084
[11] Eppstein, David, Quasiconvex analysis of backtracking algorithms, (), 781-790 · Zbl 1318.68210
[12] Fomin, Fedor V.; Grandoni, Fabrizio; Kratsch, Dieter, Some new techniques in design and analysis of exact (exponential) algorithms, Bull. eur. assoc. theor. comput. sci., 87, 47-77, (2005) · Zbl 1169.68669
[13] Fomin, Fedor V.; Høie, Kjartan, Pathwidth of cubic graphs and exact algorithms, Inform. process. lett., 97, 5, 191-196, (2006), MR2195217 (2006g:05199) · Zbl 1191.68826
[14] Martin Fürer, Shiva Prasad Kasiviswanathan, Algorithms for counting 2-SAT solutions and colorings with applications, Tech. Report TR05-033, Electronic Colloquium on Computational Complexity, March 2005, See http://www.eccc.uni-trier.de/eccc/ · Zbl 1137.68620
[15] Furer, Martin; Kasiviswanathan, Shiva P., Exact MAX 2-SAT: easier and faster, () · Zbl 1131.68522
[16] Gramm, Jens; Hirsch, Edward A.; Niedermeier, Rolf; Rossmanith, Peter, Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT, Discrete appl. math., 130, 2, 139-155, (2003), MR2014655 (2004j:68077) · Zbl 1051.68078
[17] Hirsch, Edward A., A new algorithm for MAX-2-SAT, (), 65-73 · Zbl 0959.68047
[18] Jansen, Klaus; Karpinski, Marek; Lingas, Andrzej; Seidel, Eike, Polynomial time approximation schemes for MAX-bisection on planar and geometric graphs, SIAM J. comput., 35, 1, 110-119, (2005), (electronic). MR2178800 (2006f:68143) · Zbl 1087.90063
[19] Kulikov, Alexander S.; Fedin, Sergey S., Solution of the maximum cut problem in time \(2^{| E | / 4}\), Zap. nauchn. sem. S.-peterburg. otdel. mat. inst. Steklov. (POMI), 293, 7, 129-138, 183, (2002), Teor. Slozhn. Vychisl
[20] Kojevnikov, A.; Kulikov, A.S., A new approach to proving upper bounds for MAX-2-SAT, (), 11-17 · Zbl 1192.68368
[21] Kneis, Joachim; Mölle, Daniel; Richter, Stefan; Rossmanith, Peter, Algorithms based on the treewidth of sparse graphs, (), 385-396, MR2213887 · Zbl 1171.05428
[22] Joachim Kneis, Peter Rossmanith, A new satisfiability algorithm with applications to Max-Cut, Tech. Report AIB-2005-08, Department of Computer Science, RWTH Aachen, 2005
[23] Khanna, Sanjeev; Sudan, Madhu; Trevisan, Luca; Williamson, David P., The approximability of constraint satisfaction problems, SIAM J. comput., 30, 6, 1863-1920, (2001), (electronic). MR1856561 (2002k:68058) · Zbl 0992.68059
[24] Dániel Marx, Parameterized complexity of constraint satisfaction problems, in: Proceedings of the 19th IEEE Annual Conference on Computational Complexity, CCC’04, 2004, pp. 139-149
[25] Monien, Burkhard; Preis, Robert, Upper bounds on the bisection width of 3- and 4-regular graphs, J. discrete algorithms, 4, 3, 475-498, (2006), MR2258338 · Zbl 1103.05042
[26] Niedermeier, Rolf; Rossmanith, Peter, New upper bounds for maximum satisfiability, J. algorithms, 36, 1, 63-88, (2000) · Zbl 0959.68049
[27] Schöning, Uwe, A probabilistic algorithm for \(k\)-SAT and constraint satisfaction problems, (), 410-414, MR1917579
[28] Scott, Alexander D.; Sorkin, Gregory B., Faster algorithms for MAX CUT and MAX CSP, with polynomial expected time for sparse instances, (), 382-395 · Zbl 1279.68108
[29] Alexander D. Scott, Gregory B. Sorkin, A faster exponential-time algorithm for Max 2-Sat, Max Cut, and Max \(k\)-Cut, Tech. Report RC23456 (W0412-001), IBM Research Report, December 2004, See http://domino.research.ibm.com/library/cyberdig.nsf
[30] Alexander D. Scott, Gregory B. Sorkin, Generalized constraint satisfaction problems, Tech. Report cs:DM/0604079v1, arxiv.org, April 2006, See http://arxiv.org/abs/cs.DM/0604079 · Zbl 1131.90429
[31] Scott, Alexander D.; Sorkin, Gregory B., An LP-designed algorithm for constraint satisfaction, (), 588-599 · Zbl 1131.90429
[32] Scott, Alexander D.; Sorkin, Gregory B., Solving sparse random instances of MAX cut and MAX 2-CSP in linear expected time, Comb. probab. comput., 15, 1-2, 281-315, (2006) · Zbl 1082.05519
[33] Alexander D. Scott, Gregory B. Sorkin, Polynomial constraint satisfaction: A framework for counting and sampling CSPs and other problems, Tech. Report cs:DM/0604079v2, arxiv.org, February 2007, See http://arxiv.org/abs/cs.DM/0604079
[34] Trevisan, Luca; Sorkin, Gregory B.; Sudan, Madhu; Williamson, David P., Gadgets, approximation, and linear programming, SIAM J. comput., 29, 6, 2074-2097, (2000) · Zbl 0957.68048
[35] Ryan Williams, A new algorithm for optimal constraint satisfaction and its implications, in: Proc. 31st International Colloquium on Automata, Languages and Programming, ICALP, 2004 · Zbl 1098.68120
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.