Parameterized Complexity of MaxLin2 and MaxSat Above Average

6^th December 2011, 15:30 ALT
Prof. Gregory Gutin
Department of Computer Science
Royal Holloway University London
UK

Abstract

Let $P$ be a decision problem (answers are yes or no). A parameterized
problem $\Pi$ is a set of pairs $(x,k)$ where $x$ is an instance of $P$ and $k$ (usually an integer) is the parameter. One example is the $k$-Vertex Cover problem, where for a given graph $G$ we are to decide whether there is a set of $k$ vertices covering all edges of $G.$

A kernelization of $\Pi$ is a polynomial time algorithm that maps an instance $(x,k)\in \Pi$ to an instance $(x',k')\in \Pi$ (kernel) such that (i) $(x,k)$ is a yes-instance iff $(x',k')$ is a yes-instance, (ii) $k'\leq h(k)$ and $|x'|\leq g(k)$ for some functions $h$ and $g$, where $|x'|$ is the size of $x'$. For example, there is a kernelization of $k$-Vertex Cover reducing each pair ($G,k$) into ($H,k$), where $H$ has at most $2k$ vertices and $k^2$ edges.

A parameterized problem is fixed-parameter tractable (fpt) if it can be
solved in time $O(f(k)|x|^{O(1)})$ for some function $f$ in $k$ only. It is well-known that a parameterized problem is fpt if and only if it is decidable and admits a kernelization.

We will discuss MaxLin2-AA (AA stands for Above Average): given a system of linear equations over GF(2) in which each equation has a positive integral weight, decide whether there is an assignment to the variables that satisfies equations of total weight at least $W/2+k,$ where $W$ is the total weight of all equations of the system. Solving an open question of Mahajan, Raman and Sikdar (2006), we proved (FSTTCS 2011) that MaxLin2-AA is fpt and admits a kernel with at most $O(k^2\log k)$ variables.

In MaxSat, we are given a CNF formula $F$ with $n$ variables and $m$ clauses and asked to find a truth assignment satisfying the maximum number of clauses. Let $r_1,\ldots, r_m$ be the number of literals in the clauses of $F$. Then ${\rm asat}(F)=\sum_{i=1}^m (1-2^{-r_i})$ is the expected number of clauses satisfied by a random truth assignment (the truth values to the variables are distributed uniformly and
independently). It is well-known that, in polynomial time, one can find a truth assignment satisfying at least ${\rm asat}(F)$ clauses. In the parameterized problem MaxSat-AA, we are to decide whether there is a truth assignment satisfying at least ${\rm asat}(F)+k$ clauses,
where $k$ is the (nonnegative) parameter. We proved that MaxSat-AA is not fpt unless P=NP.

We will also consider a more refined version of MaxSat-AA, Max-$r(n)$-Sat-AA, where $r_j\le r(n)$ for each $j$. Alon et al. (SODA 2010) proved that if $r=r(n)$ is a constant, then Max-$r$-Sat-AA is fpt. We proved that Max-$r(n)$-Sat-AA is is not fpt unless P=NP for $r(n)=\lceil \log n\rceil.$ We also proved that assuming the exponential time hypothesis, Max-$r(n)$-Sat-AA is not fpt already for any $r(n)\ge \log \log n +\phi(n)$, where $\phi(n)$ is any unbounded strictly increasing function. This lower bound on $r(n)$ cannot be decreased much further as we proved that Max-$r(n)$-Sat-AA is fpt for any $r(n)\le \log\log n - \log\log\log n - \phi(n)$, where $\phi(n)$ is any unbounded strictly increasing function. The proof uses some results on MaxLin2-AA.

This is joint work with many coauthors who will be named during the talk.