Satisfying more than half of a system of linear equations over GF(2): A multivariate approach

R. Crowston; M. Fellows; G. Gutin; M. Jones; E. J. Kim; F. Rosamond; I. Z. Ruzsa; S. Thomassé; A. Yeo

doi:10.1016/j.jcss.2013.10.002

Satisfying more than half of a system of linear equations over GF(2): A multivariate approach

R. Crowston, M. Fellows, G. Gutin, M. Jones, E. J. Kim, F. Rosamond, I. Z. Ruzsa, S. Thomassé, A. Yeo

Research output: Contribution to journal › Article › peer-review

15 Citations (Scopus)

Abstract

In the parameterized problem MaxLin2-AA[k], we are given a system with variables ^x1,.,^xn consisting of equations of the form ∝_iεI^xi=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 (it is always possible for k=0). We show that MaxLin2-AA[k] has a kernel with at most O(^k2logk) variables and can be solved in time 2^O(klogk)(^nm)O(1). 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 that Max-r-Lin2-AA[k,r] has a kernel with at most (2k-1)r variables.

Original language	English
Pages (from-to)	687-696
Number of pages	10
Journal	Journal of Computer and System Sciences
Volume	80
Issue number	4
DOIs	https://doi.org/10.1016/j.jcss.2013.10.002
Publication status	Published - Jun 2014
Externally published	Yes

Keywords

Fixed-parameter tractable
Kernel
MaxLin

ASJC Scopus subject areas

Theoretical Computer Science
Computer Networks and Communications
Computational Theory and Mathematics
Applied Mathematics

Access to Document

10.1016/j.jcss.2013.10.002

Cite this

@article{88efad45c3e4487793339bf145229590,

title = "Satisfying more than half of a system of linear equations over GF(2): A multivariate approach",

abstract = "In the parameterized problem 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{\^a}{\v S}†[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 (it is always possible for k=0). We show that 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 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 that Max-r-Lin2-AA[k,r] has a kernel with at most (2k-1)r variables.",

keywords = "Fixed-parameter tractable, Kernel, MaxLin",

author = "R. Crowston and M. Fellows and G. Gutin and M. Jones and Kim, \{E. J.\} and F. Rosamond and Ruzsa, \{I. Z.\} and S. Thomass{\'e} and A. Yeo",

year = "2014",

month = jun,

doi = "10.1016/j.jcss.2013.10.002",

language = "English",

volume = "80",

pages = "687--696",

journal = "Journal of Computer and System Sciences",

issn = "0022-0000",

publisher = "Academic Press Inc.",

number = "4",

}

TY - JOUR

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

T2 - A multivariate approach

AU - Crowston, R.

AU - Fellows, M.

AU - Gutin, G.

AU - Jones, M.

AU - Kim, E. J.

AU - Rosamond, F.

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,.,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 (it is always possible for k=0). We show that 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 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 that Max-r-Lin2-AA[k,r] has a kernel with at most (2k-1)r variables.

AB - In the parameterized problem 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 (it is always possible for k=0). We show that 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 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 that Max-r-Lin2-AA[k,r] has a kernel with at most (2k-1)r variables.

KW - Fixed-parameter tractable

KW - Kernel

KW - MaxLin

UR - https://www.scopus.com/pages/publications/84894104903

U2 - 10.1016/j.jcss.2013.10.002

DO - 10.1016/j.jcss.2013.10.002

M3 - Article

AN - SCOPUS:84894104903

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 -

Satisfying more than half of a system of linear equations over GF(2): A multivariate approach

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this