Simultaneously Satisfying Linear Equations Over F_2: MaxLin2 and Max-r-Lin2 Parameterized Above Average

Robert Crowston, Michael Fellows, Gregory Gutin, Mark Jones, Fran Rosamond, Stefan Thomasse, Anders Yeo

Research output: Chapter in Book/Report/Conference proceedingConference contribution


In the parameterized problem \textsc{MaxLin2-AA}[$k$], we are given a system with variables $x_1,\ldots ,x_n$
consisting of equations of the form $\prod_{i \in I}x_i = b$, where
$x_i,b \in \{-1, 1\}$ and $I\subseteq [n],$ each equation has a positive integral weight, and we are to decide
whether it is possible to simultaneously satisfy
equations of total weight at least $W/2+k$, where $W$ is the total weight of all equations and $k$ is the parameter
(if $k=0$, the possibility is assured).
We show that \textsc{MaxLin2-AA}[$k$] has a kernel with at most $O(k^2\log k)$ variables and can be solved in time
$2^{O(k\log k)}(nm)^{O(1)}$. This solves
an open problem of Mahajan et al. (2006).

The problem \textsc{Max-$r$-Lin2-AA}[$k,r$] is the same as \textsc{MaxLin2-AA}[$k$] with two differences:
each equation has at most $r$ variables and $r$ is the second parameter. We prove a theorem on
which implies that \textsc{Max-$r$-Lin2-AA}[$k,r$] has a kernel with at most $(2k-1)r$ variables,
improving a number of results including
one by Kim and Williams (2010). The theorem also implies a lower bound on the maximum of a
function $f:\ \{-1,1\}^n \rightarrow \mathbb{R}$ whose Fourier expansion (which is a multilinear polynomial) is
of degree $r$. We show applicability of the lower bound by
giving a new proof of the Edwards-Erd{\H o}s bound (each connected graph on $n$ vertices and $m$ edges
has a bipartite subgraph with at least $m/2 + (n-1)/4$ edges) and obtaining a generalization.
Original languageEnglish
Title of host publicationIARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science
Publication statusPublished - 2011

Publication series

NameLIPICS - Leibniz International Proceedings in Informatics

Cite this