A New Upper Bound for Max-2-Sat: A Graph-Theoretic Approach

Daniel Raible, Henning Fernau

In {\sc MaxSat}, we ask for an assignment which satisfies the maximum number of clauses for a boolean formula in CNF. We present an algorithm yielding a run time upper bound of $O^…