In this paper we investigate the parameterized complexity of the problems MaxSat and MaxCut using the framework developed by Downey and Fellows. Let
Gbe an arbitrary graph having
nvertices and
medges, and let
fbe an arbitrary CNF formula with
mclauses on
nvariables. We improve Cai and Chen's
O(2
2ckcm) time algorithm for determining if at least
kclauses of a
c-CNF formula
fcan be satisfied; our algorithm runs in
O(|
f| +
k2φ
k) time for arbitrary formulae and in
O(
cm +
ckφ
k) time for
c-CNF formulae, where φ is the golden ratio
. We also give an algorithm for finding a cut of size at least
k; our algorithm runs in
O(
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.
相似文献