Simultaneously satisfying linear equations over F2: MaxLin2 and Max-r-Lin2 Parameterized above average

Robert Crowston, Michael Fellows, Gregory Gutin, Mark Jones, Frances Rosamond, Stephan Thomasse, Anders Yeo

    Research output: Chapter in Book/Report/Conference proceedingConference Paper published in Proceedingspeer-review

    25 Citations (Scopus)

    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 (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 : {−1, 1} n → R 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. 
    Original languageEnglish
    Title of host publicationProceedings of IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science
    EditorsSupratik Chakraborty, Amit Kumar
    Place of PublicationGermany
    PublisherDagstuhl Publishing
    Pages229-240
    Number of pages12
    Volume13
    ISBN (Print)978-3-939897-34-7
    DOIs
    Publication statusPublished - 2011
    EventInternational Conference on Foundations of Software Technology and Theoretical Computer Science (FST&TCS 2011 31st) - India, India
    Duration: 12 Dec 201114 Dec 2011
    Conference number: 2011 (31st)

    Conference

    ConferenceInternational Conference on Foundations of Software Technology and Theoretical Computer Science (FST&TCS 2011 31st)
    Abbreviated titleFST&TCS
    Country/TerritoryIndia
    Period12/12/1114/12/11

    Fingerprint

    Dive into the research topics of 'Simultaneously satisfying linear equations over F2: MaxLin2 and Max-r-Lin2 Parameterized above average'. Together they form a unique fingerprint.

    Cite this