zbMATH — the first resource for mathematics

New exact algorithms for the 2-constraint satisfaction problem. (English) Zbl 1290.68144
Summary: Many optimization problems can be phrased in terms of constraint satisfaction. In particular MAX-2-SAT and MAX-2-CSP are known to generalize many hard combinatorial problems on graphs. Algorithms solving the problem exactly have been designed but the running time is improved over trivial brute-force solutions only for very sparse instances. Despite many efforts, the only known algorithm [R. Williams, Theor. Comput. Sci. 348, No. 2–3, 357–365 (2005; Zbl 1081.68095)] solving MAX-2-CSP over \(n\) variables in less than \(O^\ast(2^n)\) steps uses exponential space.
Several authors have designed algorithms with running time \(O^\ast(2^{nf(d)})\) where \(f:\mathbb R^+\to (0,1)\) is a slowly growing function and \(d\) is the average variable degree of the input formula. The current best known algorithm for MAX-2-CSP [A. D. Scott and G. B. Sorkin, Discrete Optim. 4, No. 3–4, 260–287 (2007; Zbl 1153.90505)] runs in time \(O^\ast(2^{n(1-\frac{2}{d+1})})\) and polynomial space. In this paper we continue this line of research and design new algorithms for the MAX-2-SAT and MAX-2-CSP problems.
First, we present a general technique for obtaining new bounds on the running time of a simple algorithm for MAX-2-CSP analyzed with respect to the number of vertices from algorithms that are analyzed with respect to the number of constraints. The best known bound for the problem is improved to \(O^\ast(2^{n(1-\frac{3}{d+1})})\) for \(d\geqslant 3\). We further improve the bound for MAX-2-SAT, in particular for \(d\geqslant 6\) we achieve \(O^\ast(2^{n(1-\frac{3.677}{d+1})})\).
As a second result we present an algorithm with asymptotically better running time for the case when the input instance is not very sparse. Building on recent work of U. Feige and S. Kogan [J. Graph Theory 64, No. 4, 277–291 (2010; Zbl 1205.05087)] we derive an upper bound on the size of a vertex separator for graphs in terms of the average degree of the graph. We then design a simple algorithm solving MAX-2-CSP in time \(O^\ast(2^{c_dn})\), \(c_d=1-\frac{2\alpha\ln d}{d}\) for some \(\alpha<1\) and \(d=o(n)\).

68W40 Analysis of algorithms
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
90C27 Combinatorial optimization
Full Text: DOI
[1] Alon, N.; Kahn, J.; Seymour, P. D., Large induced degenerate subgraphs, Graphs Comb., 3, 1, 203-211, (1987) · Zbl 0624.05039
[2] Binkele-Raible, D.; Fernau, H., A new upper bound for MAX-2-SAT: A graph-theoretic approach, J. Discrete Algorithms, 8, 4, 388-401, (2010) · Zbl 1203.90130
[3] Björklund, A.; Husfeldt, T.; Koivisto, M., Set partitioning via inclusion-exclusion, SIAM J. Comput., 39, 2, 546-563, (2009) · Zbl 1215.05056
[4] Calabro, C.; Impagliazzo, R.; Paturi, R., The complexity of satisfiability of small depth circuits, (IWPEC, (2009)), 75-85 · Zbl 1273.68159
[5] Chen, J.; Kanj, I. A., Improved exact algorithms for MAX-SAT, Discrete Appl. Math., 142, 1-3, 17-27, (2004) · Zbl 1077.68116
[6] Croce, F. D.; Kaminski, M. J.; Paschos, V. Th., An exact algorithm for MAX-CUT in sparse graphs, Oper. Res. Lett., 35, 3, 403-408, (2007) · Zbl 1163.90767
[7] Dantsin, E.; Wolpert, A., MAX-SAT for formulas with constant clause density can be solved faster than in \(O(2^n)\) time, (SAT, (2006)), 266-276 · Zbl 1187.68258
[8] Feige, U.; Kogan, S., Balanced coloring of bipartite graphs, J. Graph Theory, 64, 4, 277-291, (2010) · Zbl 1205.05087
[9] Fürer, M.; Kasiviswanathan, S. P., Exact MAX 2-sat: easier and faster, SOFSEM, 1, 272-283, (2007) · Zbl 1131.68522
[10] Gaspers, S.; Sorkin, G. B., A universally fastest algorithm for MAX 2-sat, MAX 2-CSP, and everything in between, J. Comput. Syst. Sci., 78, 1, 305-335, (2012) · Zbl 1238.68066
[11] Golovnev, A., New upper bounds for MAX-2-SAT and MAX-2-CSP w.r.t. the average variable degree, (IPEC, (2011)), 106-117 · Zbl 1352.68107
[12] Gramm, J.; Hirsch, E. A.; Niedermeier, R.; Rossmanith, P., Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT, Discrete Appl. Math., 130, 2, 139-155, (2003) · Zbl 1051.68078
[13] Håstad, J., Some optimal inapproximability results, J. ACM, 48, 4, 798-859, (2001) · Zbl 1127.68405
[14] Held, M.; Karp, R. M., A dynamic programming approach to sequencing problems, J. SIAM, 10, 196-210, (1962) · Zbl 0106.14103
[15] Hirsch, E. A., A new algorithm for MAX-2-SAT, (STACS, (2000)), 65-73 · Zbl 0959.68047
[16] Horowitz, E.; Sahni, S., Computing partitions with applications to the knapsack problem, J. ACM, 21, 277-292, (1974) · Zbl 0329.90046
[17] Impagliazzo, R.; Paturi, R.; Zane, F., Which problems have strongly exponential complexity?, J. Comput. Syst. Sci., 63, 4, 512-530, (2001) · Zbl 1006.68052
[18] Kojevnikov, A.; Kulikov, A. S., A new approach to proving upper bounds for MAX-2-SAT, (SODA, (2006)), 11-17 · Zbl 1192.68368
[19] Kulikov, A. S.; Kutzkov, K., New upper bounds for the problem of maximal satisfiability, Discrete Math. Appl., 155-172, (2009) · Zbl 1234.68154
[20] Kutzkov, K., An exact exponential time algorithm for counting bipartite cliques, Inf. Process. Lett., 112, 13, 535-539, (2012) · Zbl 1243.05227
[21] Lawler, E. L., A note on the complexity of the chromatic number problem, Inf. Process. Lett., 5, 66-67, (1976) · Zbl 0336.68021
[22] Lipton, R. J.; Tarjan, R. E., Applications of a planar separator theorem, SIAM J. Comput., 9, 3, 615-627, (1980) · Zbl 0456.68077
[23] Moser, R. A.; Scheder, D., A full derandomization of schöning’s k-SAT algorithm, (STOC, (2011)), 245-252 · Zbl 1288.68245
[24] Schöning, U., A probabilistic algorithm for k-SAT based on limited local search and restart, Algorithmica, 32, 4, 615-623, (2002) · Zbl 1050.68049
[25] Scott, A. D.; Sorkin, G. B., Linear-programming design and analysis of fast algorithms for MAX 2-CSP, Discrete Optim., 4, 3-4, 260-287, (2007) · Zbl 1153.90505
[26] Tarjan, R. E.; Trojanowski, A. E., Finding a maximum independent set, SIAM J. Comput., 6, 537-546, (1977) · Zbl 0357.68035
[27] Vassilevska Williams, V., Multiplying matrices faster than coppersmith-Winograd, (STOC, (2012)), 887-898 · Zbl 1286.65056
[28] Williams, R., A new algorithm for optimal 2-constraint satisfaction and its implications, Theor. Comput. Sci., 348, 2-3, 357-365, (2005) · Zbl 1081.68095
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.