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

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

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 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.

Original languageEnglish
JournalJournal of Computer and System Sciences
Volume80
Issue number4
Pages (from-to)687-696
ISSN0022-0000
DOIs
Publication statusPublished - 2014
Externally publishedYes

Keywords

  • Fixed-parameter tractable
  • Kernel
  • MaxLin

Fingerprint

Dive into the research topics of 'Satisfying more than half of a system of linear equations over GF(2): A multivariate approach'. Together they form a unique fingerprint.

Cite this