License: 
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2011.229
URN: urn:nbn:de:0030-drops-33416
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2011/3341/
Crowston, Robert ;
Fellows, Michael ;
Gutin, Gregory ;
Jones, Mark ;
Rosamond, Frances ;
Thomassé, Stéphan ;
Yeo, Anders
Simultaneously Satisfying Linear Equations Over F_2: MaxLin2 and Max-r-Lin2 Parameterized Above Average
Abstract
In the parameterized problem MaxLin2-AA[$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 MaxLin2-AA[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 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 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 Edwards-Erdös 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.
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 Max-r-Lin2 Parameterized Above Average}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)},
pages = {229--240},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-34-7},
ISSN = {1868-8969},
year = {2011},
volume = {13},
editor = {Supratik Chakraborty and Amit Kumar},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2011/3341},
URN = {urn:nbn:de:0030-drops-33416},
doi = {10.4230/LIPIcs.FSTTCS.2011.229},
annote = {Keywords: MaxLin, fixed-parameter tractability, kernelization, pseudo-boolean functions}
}
|
Keywords: |
|
MaxLin, fixed-parameter tractability, kernelization, pseudo-boolean functions |
|
Collection: |
|
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011) |
|
Issue Date: |
|
2011 |
|
Date of publication: |
|
01.12.2011 |
