期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1997
卷号：1997
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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.
