2026-07-22T18:11:06Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:3341 2024-03-06T10:34:05Z ddc:004 open_access

Simultaneously Satisfying Linear Equations Over F_2: MaxLin2 and Max-r-Lin2 Parameterized Above Average Crowston, Robert Fellows, Michael Gutin, Gregory Jones, Mark Rosamond, Frances Thomassé, Stéphan Yeo, Anders MaxLin fixed-parameter tractability kernelization pseudo-boolean functions 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Robert Crowston and Michael Fellows and Gregory Gutin and Mark Jones and Frances Rosamond and Stéphan Thomassé and Anders Yeo 2011 Is Part Of LIPIcs, Volume 13, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2011.229 urn:nbn:de:0030-drops-33416 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2011.229 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode