Crowston, Robert ;
Fellows, Michael ;
Gutin, Gregory ;
Jones, Mark ;
Rosamond, Frances ;
Thomassé, Stéphan ;
Yeo, Anders
Simultaneously Satisfying Linear Equations Over F_2: MaxLin2 and MaxrLin2 Parameterized Above Average
Abstract
In the parameterized problem MaxLin2AA[$k$], we are given a system with variables x_1,...,x_n consisting of equations of the form Product_{i in I}x_i = b, where x_i,b in {1, 1} and I is a nonempty subset of {1,...,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 MaxLin2AA[k] has a kernel with at most O(k^2 log k) variables and can be solved in time 2^{O(k log k)}(nm)^{O(1)}. This solves an open problem of Mahajan et al. (2006).
The problem MaxrLin2AA[k,r] is the same as MaxLin2AA[k] with two
differences: each equation has at most r variables and r is the second parameter. We prove a theorem on Max$r$Lin2AA[k,r] which implies that MaxrLin2AA[k,r] has a kernel with at most (2k1)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 that maps {1,1}^n to the set of reals and whose Fourier expansion (which is a multilinear polynomial) is of degree r. We show applicability of the lower bound by giving a new proof of the EdwardsErdös bound (each connected graph on n vertices and m edges has a bipartite subgraph with at least m/2 +(n1)/4 edges) and obtaining a generalization.
BibTeX  Entry
@InProceedings{crowston_et_al:LIPIcs:2011:3341,
author = {Robert Crowston and Michael Fellows and Gregory Gutin and Mark Jones and Frances Rosamond and St{\'e}phan Thomass{\'e} and Anders Yeo},
title = {{Simultaneously Satisfying Linear Equations Over F_2: MaxLin2 and MaxrLin2 Parameterized Above Average}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)},
pages = {229240},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897347},
ISSN = {18688969},
year = {2011},
volume = {13},
editor = {Supratik Chakraborty and Amit Kumar},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2011/3341},
URN = {urn:nbn:de:0030drops33416},
doi = {10.4230/LIPIcs.FSTTCS.2011.229},
annote = {Keywords: MaxLin, fixedparameter tractability, kernelization, pseudoboolean functions}
}
01.12.2011
Keywords: 

MaxLin, fixedparameter tractability, kernelization, pseudoboolean functions 
Seminar: 

IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)

Issue date: 

2011 
Date of publication: 

01.12.2011 