AIB 2005-08: A New Satisfiability Algorithm With Applications To Max-Cut

The following technical report is available from http://aib.informatik.rwth-aachen.de/:

A New Satisfiability Algorithm With Applications To Max-Cut Joachim Kneis, Peter Rossmanith AIB 2005-08

We prove an upper bound of m/5.217+3 on the treewidth of a graph with m edges. Moreover, we can always find efficiently a set of no more than m/5.217 nodes whose removal yields a very simple graph. As an application, we immediately get simple algorithms for several problems, including Max-Cut, Max-2-SAT and Max-2-XSAT. The resulting algorithms have running times of O*(2^t/5.217), where t is the number of distinct clause types. In particular, this implies a record-breaking time complexity of O*(2^m/5.217).