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 ProceedingsResearchpeer-review

    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
    CountryIndia
    Period12/12/1114/12/11

    Fingerprint

    Linear equation
    Lower bound
    Imply
    Difference equation
    Connected graph
    Subgraph
    kernel
    Polynomial
    Theorem

    Cite this

    Crowston, R., Fellows, M., Gutin, G., Jones, M., Rosamond, F., Thomasse, S., & Yeo, A. (2011). Simultaneously satisfying linear equations over F2: MaxLin2 and Max-r-Lin2 Parameterized above average. In S. Chakraborty, & A. Kumar (Eds.), Proceedings of IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (Vol. 13, pp. 229-240). Germany: Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.FSTTCS.2011.i
    Crowston, Robert ; Fellows, Michael ; Gutin, Gregory ; Jones, Mark ; Rosamond, Frances ; Thomasse, Stephan ; Yeo, Anders. / Simultaneously satisfying linear equations over F2 : MaxLin2 and Max-r-Lin2 Parameterized above average. Proceedings of IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. editor / Supratik Chakraborty ; Amit Kumar. Vol. 13 Germany : Dagstuhl Publishing, 2011. pp. 229-240
    @inproceedings{141b459f49fb4507b3afed8f89a81263,
    title = "Simultaneously satisfying linear equations over F2: MaxLin2 and Max-r-Lin2 Parameterized above average",
    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. ",
    keywords = "Connected graph, Fixed-parameter tractability, Fourier expansion, Kernelization, Maxlin, Multilinear polynomials, Parameterized problems, Pseudo-Boolean function, Boolean functions, Software engineering, Theorem proving, Graph theory",
    author = "Robert Crowston and Michael Fellows and Gregory Gutin and Mark Jones and Frances Rosamond and Stephan Thomasse and Anders Yeo",
    year = "2011",
    doi = "10.4230/LIPIcs.FSTTCS.2011.i",
    language = "English",
    isbn = "978-3-939897-34-7",
    volume = "13",
    pages = "229--240",
    editor = "Chakraborty, {Supratik } and Kumar, {Amit }",
    booktitle = "Proceedings of IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science",
    publisher = "Dagstuhl Publishing",

    }

    Crowston, R, Fellows, M, Gutin, G, Jones, M, Rosamond, F, Thomasse, S & Yeo, A 2011, Simultaneously satisfying linear equations over F2: MaxLin2 and Max-r-Lin2 Parameterized above average. in S Chakraborty & A Kumar (eds), Proceedings of IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. vol. 13, Dagstuhl Publishing, Germany, pp. 229-240, International Conference on Foundations of Software Technology and Theoretical Computer Science (FST&TCS 2011 31st), India, 12/12/11. https://doi.org/10.4230/LIPIcs.FSTTCS.2011.i

    Simultaneously satisfying linear equations over F2 : MaxLin2 and Max-r-Lin2 Parameterized above average. / Crowston, Robert; Fellows, Michael; Gutin, Gregory; Jones, Mark; Rosamond, Frances; Thomasse, Stephan; Yeo, Anders.

    Proceedings of IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. ed. / Supratik Chakraborty; Amit Kumar. Vol. 13 Germany : Dagstuhl Publishing, 2011. p. 229-240.

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

    TY - GEN

    T1 - Simultaneously satisfying linear equations over F2

    T2 - MaxLin2 and Max-r-Lin2 Parameterized above average

    AU - Crowston, Robert

    AU - Fellows, Michael

    AU - Gutin, Gregory

    AU - Jones, Mark

    AU - Rosamond, Frances

    AU - Thomasse, Stephan

    AU - Yeo, Anders

    PY - 2011

    Y1 - 2011

    N2 - 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. 

    AB - 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. 

    KW - Connected graph

    KW - Fixed-parameter tractability

    KW - Fourier expansion

    KW - Kernelization

    KW - Maxlin

    KW - Multilinear polynomials

    KW - Parameterized problems

    KW - Pseudo-Boolean function

    KW - Boolean functions

    KW - Software engineering

    KW - Theorem proving

    KW - Graph theory

    U2 - 10.4230/LIPIcs.FSTTCS.2011.i

    DO - 10.4230/LIPIcs.FSTTCS.2011.i

    M3 - Conference Paper published in Proceedings

    SN - 978-3-939897-34-7

    VL - 13

    SP - 229

    EP - 240

    BT - Proceedings of IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science

    A2 - Chakraborty, Supratik

    A2 - Kumar, Amit

    PB - Dagstuhl Publishing

    CY - Germany

    ER -

    Crowston R, Fellows M, Gutin G, Jones M, Rosamond F, Thomasse S et al. Simultaneously satisfying linear equations over F2: MaxLin2 and Max-r-Lin2 Parameterized above average. In Chakraborty S, Kumar A, editors, Proceedings of IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Vol. 13. Germany: Dagstuhl Publishing. 2011. p. 229-240 https://doi.org/10.4230/LIPIcs.FSTTCS.2011.i