TY - JOUR

T1 - Satisfying more than half of a system of linear equations over GF(2)

T2 - A multivariate approach

AU - Crowston, Robert

AU - Fellows, Michael

AU - Gutin, Gregory

AU - Jones, Mark

AU - Kim, E.J

AU - Rosamond, Frances

AU - Ruzsa, I.Z

AU - ThomassÃ©, S

AU - Yeo, A

PY - 2014/6

Y1 - 2014/6

N2 - In the parameterized problem MaxLin2-AA[k ], we are given a system with variables x1,…,xnx1,…,xn consisting of equations of the form ∏i∈Ixi=b∏i∈Ixi=b, where xi,b∈{−1,1}xi,b∈{−1,1} and I⊆[n]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+kW/2+k, where W is the total weight of all equations and k is the parameter (it is always possible for k=0k=0). We show that MaxLin2-AA[k ] has a kernel with at most View the MathML sourceO(k2logk) variables and can be solved in time 2O(klogk)(nm)O(1)2O(klogk)(nm)O(1). This solves an open problem of Mahajan et al. (2006). The problem Max-r-Lin2-AA[k,rk,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 that Max-r-Lin2-AA[k,rk,r] has a kernel with at most (2k−1)r(2k−1)r variables.

AB - In the parameterized problem MaxLin2-AA[k ], we are given a system with variables x1,…,xnx1,…,xn consisting of equations of the form ∏i∈Ixi=b∏i∈Ixi=b, where xi,b∈{−1,1}xi,b∈{−1,1} and I⊆[n]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+kW/2+k, where W is the total weight of all equations and k is the parameter (it is always possible for k=0k=0). We show that MaxLin2-AA[k ] has a kernel with at most View the MathML sourceO(k2logk) variables and can be solved in time 2O(klogk)(nm)O(1)2O(klogk)(nm)O(1). This solves an open problem of Mahajan et al. (2006). The problem Max-r-Lin2-AA[k,rk,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 that Max-r-Lin2-AA[k,rk,r] has a kernel with at most (2k−1)r(2k−1)r variables.

UR - http://www.scopus.com/inward/record.url?scp=84894104903&partnerID=8YFLogxK

U2 - 10.1016/j.jcss.2013.10.002

DO - 10.1016/j.jcss.2013.10.002

M3 - Article

SN - 0022-0000

VL - 80

SP - 687

EP - 696

JO - Journal of Computer and System Sciences

JF - Journal of Computer and System Sciences

IS - 4

ER -