Parameterizing above Guaranteed Values: MaxSat and MaxCut

In this paper we investigate the parameterized complexity of the problems MaxSat and MaxCut using the framework developed by Downey and Fellows. LetGbe an arbitrary graph havingnvertices andmedges, and letfbe an arbitrary CNF formula withmclauses onnvariables. We improve Cai and Chen'sO(2^2ckcm) time algorithm for determining if at leastkclauses of ac-CNF formulafcan be satisfied; our algorithm runs inO(|f| + k²φ^k) time for arbitrary formulae and inO(cm + ckφ^k) time forc-CNF formulae, where φ is the golden ratio . We also give an algorithm for finding a cut of size at leastk; our algorithm runs inO(m + n + k4^k) time. We then argue that the standard parameterization of these problems is unsuitable, because nontrivial situations arise only for large parameter values (k ≥ m/2), in which range the fixed-parameter tractable algorithms are infeasible. A more meaningful question in the parameterized setting is to ask whether m/2 + kclauses can be satisfied, or m/2 + kedges can be placed in a cut. We show that these problems remain fixed-parameter tractable even under this parameterization. Furthermore, for up to logarithmic values of the parameter, our algorithms for these versions also run in polynomial time.