Simultaneously Satisfying Linear Equations Over F2: MaxLin2 and Max-r-Lin2 Parameterized Above Average
In the parameterized problem \textsc{MaxLin2-AA}[k], we are given a system with variables x1,...,xn consisting of equations of the form ∏i∈Ixi=b, where xi,b∈{−1,1} and I⊆[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(k2logk) variables and can be solved in time 2O(klogk)(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→R 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.