### Abstract

The maximum 2-satisfiability problem (MAX-2-SAT) is: given a Boolean formula in 2-CNF, find a truth assignment that satisfies the maximum possible number of its clauses. MAX-2-SAT is MAX-SNP-complete. Recently, this problem received much attention in the contexts of (polynomial-time) approximation algorithms and (exponential-time) exact algorithms. In this paper, we present an exact algorithm solving MAX-2-SAT in time poly(L) · 2^{K/5}, where K is the number of clauses and L is their total length. In fact, the running time is only poly(L) · 2^{K2/5}, where K_{2} is the number of clauses containing two literals. This bound implies the bound poly(L) · 2^{L/10}. Our results significantly improve previous bounds: poly(L) ·2 ^{K/2.88} (J. Algorithms 36 (2000) 62-88) and poly(L) · 2^{K/3.44} (implicit in Bansal and Raman (Proceedings of the 10th Annual Conference on Algorithms and Computation, ISAAC'99, Lecture Notes in Computer Science, Vol. 1741, Springer, Berlin, 1999, pp. 247-258.)). As an application, we derive upper bounds for the (MAX-SNP-complete) maximum cut problem (MAX-CUT), showing that it can be solved in time poly(M) · 2^{M/3}, where M is the number of edges in the graph. This is of special interest for graphs with low vertex degree.

Original language | English |
---|---|

Pages (from-to) | 139-155 |

Number of pages | 17 |

Journal | Discrete Applied Mathematics |

Volume | 130 |

Issue number | 2 |

DOIs | |

Publication status | Published - 15 Aug 2003 |

Event | CMMSE 2002 - Alicante Duration: 20 Sep 2002 → 25 Sep 2002 |

### Scopus subject areas

- Discrete Mathematics and Combinatorics
- Applied Mathematics

## Fingerprint Dive into the research topics of 'Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT'. Together they form a unique fingerprint.

## Cite this

*Discrete Applied Mathematics*,

*130*(2), 139-155. https://doi.org/10.1016/S0166-218X(02)00402-X