10.4230/LIPICS.FSTTCS.2011.229
Crowston, Robert
Robert
Crowston
Fellows, Michael
Michael
Fellows
Gutin, Gregory
Gregory
Gutin
Jones, Mark
Mark
Jones
Rosamond, Frances
Frances
Rosamond
Thomassé, Stéphan
Stéphan
Thomassé
Yeo, Anders
Anders
Yeo
Simultaneously Satisfying Linear Equations Over F_2: MaxLin2 and Max-r-Lin2 Parameterized Above Average
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
2011
Article
MaxLin
fixed-parameter tractability
kernelization
pseudo-boolean functions
Chakraborty, Supratik
Supratik
Chakraborty
Kumar, Amit
Amit
Kumar
2011
2011-12-01
2011-12-01
2011-12-01
en
urn:nbn:de:0030-drops-33416
10.4230/LIPIcs.FSTTCS.2011
978-3-939897-34-7
1868-8969
10.4230/LIPIcs.FSTTCS.2011
LIPIcs, Volume 13, FSTTCS 2011
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)
2013
13
24
229
240
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Chakraborty, Supratik
Supratik
Chakraborty
Kumar, Amit
Amit
Kumar
1868-8969
Leibniz International Proceedings in Informatics (LIPIcs)
2011
13
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
12 pages
513791 bytes
application/pdf
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license
info:eu-repo/semantics/openAccess
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.
LIPIcs, Vol. 13, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011), pages 229-240