Simultaneously Satisfying Linear Equations Over F_2: MaxLin2 and Max-r-Lin2 Parameterized Above Average. / Crowston, Robert; Fellows, Michael; Gutin, Gregory; Jones, Mark; Rosamond, Fran; Thomasse, Stefan; Yeo, Anders.

IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. 2011. p. 229--240 (LIPICS - Leibniz International Proceedings in Informatics; Vol. 13).

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

Published

Abstract

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
\textsc{Max-$r$-Lin2-AA}[$k,r$]
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
Pages229--240
Publication statusPublished - 2011

Publication series

NameLIPICS - Leibniz International Proceedings in Informatics
Volume13

ID: 4731424