1997 · 25 citations · 0 references
Natural SciencesMathematicsOptimizationConstrained OptimizationConstraint SatisfactionConvex OptimizationOptimization TheoryParameter OptimizationParameterized AlgorithmsOptimization Under ConstraintsParameterized InapproximabilityParameterizing Above Guarantee
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...