Parametrizing Above Guaranteed Values: MaxSat and MaxCut

Meena Mahajan, Venkatesh Raman

1997 · 25 citations · 0 references

Concepts

Abstract

In this paper we investigate the parametrized complexity of the problems MaxSat and MaxCut using the framework developed by Downey and Fellows[7]. Let G be an arbitrary graph having n vertices and m edges, and let f be an arbitrary CNF formula with m clauses on n variables. We improve Cai and Chen's O(2 2k m) time algorithm for determining if at least k clauses of of a c-CNF formula f can be satisfied[4]; our algorithm runs in O(jf j +k 2 OE k ) time for arbitrary formulae and in O(m + kOE k ) time for c-CNF formulae. We also give an algorithm for finding a cut of size at least k; our algorithm runs in O(m + n + k4 k ) time. Since it is known that G has a cut of size at least d m 2 e and that there exists an assignment to the variables of f that satisfies at least d m 2 e clauses of f , we argue that the standard parametrization of these problems is unsuitable. Non-trivial situations arise only for large parameter values, in which range the fixed-parameter tractable a...