In this paper we investigate the parametrized complexity of the problems MaxSat and MaxCut using the framework developed by Downey and Fellows. 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(22km) time algorithm for determining if at least k clauses of of a c-CNF formula f can be satisfied; our algorithm runs in O(f+k2k) time for arbitrary formulae and in O(m+kk) 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+k4k) time. Since it is known that G has a cut of size at least 2m and that there exists an assignment to the variables of f that satisfies at least 2m 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 algorithms are infeasible. A more meaningful question in the parametrized setting is to ask whether 2m+k clauses can be satisfied, or 2m+k edges can be placed in a cut. We show that these problems remain fixed-parameter tractable even under this parametrization. Furthermore, for upto logarithmic values of the parameter, our algorithms run in polynomial time. We also discuss the complexity of the parametrized versions of these problems where all but k clauses have to satisfied or all but k edges have to be in the cut.
展开▼
