A New Satisfiability Algorithm With Applications To Max-Cut
Joachim Kneis, Peter Rossmanith
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).