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

Original · EN

In the parameterized problem MaxLin2-AA[k], we are given a system with variables x₁,...,xₙ consisting of equations of the form ∏ᵢ ∈ ᵢxᵢ = b, where xᵢ,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 MaxLin2-AA[k] has a kernel with at most O(k² k) variables and can be solved in time 2O(k k)(nm)ᵒ⁽¹⁾. This solves an open problem of Mahajan et al. (2006). The problem Max-r-Lin2-AA[k,r] is the same as MaxLin2-AA[k] with two differences: each equation has at most r variables and r is the second parameter. We prove a theorem on Max-r-Lin2-AA[k,r] which implies that 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}ⁿ → R of degree r. We show applicability of the lower bound by giving a new proof of the Edwards-Erd os 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.