TR97-033 Authors: Meena Mahajan, Venkatesh Raman

Publication: 10th September 1997 21:10

Downloads: 973

Keywords:

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(2^{2k}m)$ 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| + k^2\phi^k)$ time for arbitrary

formulae and in $O(m + k\phi^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

$\lceil \frac{m}{2} \rceil$ and that there exists an

assignment to the variables of $f$ that satisfies at least

$\lceil \frac{m}{2} \rceil$ 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

$\lceil \frac{m}{2} \rceil + k$ clauses can be satisfied, or

$\lceil \frac{m}{2} \rceil + 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.