TY - GEN

T1 - Exact MAX 2-SAT

T2 - 33rd Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2007

AU - Fürer, Martin

AU - Kasiviswanathan, Shiva Prasad

PY - 2007

Y1 - 2007

N2 - Prior algorithms known for exactly solving MAX 2-SAT improve upon the trivial upper bound only for very sparse instances. We present new algorithms for exactly solving (in fact, counting) weighted MAX 2-SAT instances. One of them has a good performance if the underlying constraint graph has a small separator decomposition, another has a slightly improved worst case performance. For a 2-SAT instance F with n variables, the worst case running time is Õ(21-1/(d̃(F)_1))n), where d̃(F) is the average degree in the constraint graph defined by F. We use strict α-gadgets introduced by Trevisan, Sorkin, Sudan, and Williamson to get the same upper bounds for problems like MAX 3-SAT and MAX CUT. We also introduce a notion of strict (α, β)-gadget to provide a framework that allows composition of gadgets. This framework allows us to obtain the same upper bounds for MAX k-SAT and MAX k-LIN-2.

AB - Prior algorithms known for exactly solving MAX 2-SAT improve upon the trivial upper bound only for very sparse instances. We present new algorithms for exactly solving (in fact, counting) weighted MAX 2-SAT instances. One of them has a good performance if the underlying constraint graph has a small separator decomposition, another has a slightly improved worst case performance. For a 2-SAT instance F with n variables, the worst case running time is Õ(21-1/(d̃(F)_1))n), where d̃(F) is the average degree in the constraint graph defined by F. We use strict α-gadgets introduced by Trevisan, Sorkin, Sudan, and Williamson to get the same upper bounds for problems like MAX 3-SAT and MAX CUT. We also introduce a notion of strict (α, β)-gadget to provide a framework that allows composition of gadgets. This framework allows us to obtain the same upper bounds for MAX k-SAT and MAX k-LIN-2.

UR - http://www.scopus.com/inward/record.url?scp=36448936802&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=36448936802&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-69507-3_22

DO - 10.1007/978-3-540-69507-3_22

M3 - Conference contribution

AN - SCOPUS:36448936802

SN - 9783540695066

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 272

EP - 283

BT - SOFSEM 2007

PB - Springer Verlag

Y2 - 20 January 2007 through 26 January 2007

ER -