Parameterized complexity of satisfying almost all linear equations over F₂

DOI10.1007/S00224-012-9415-2MaRDI QIDQ2392244zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 1 August 2013

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1110.5915

zbMATH Keywords

finite fieldlinear equationsparameterized complexity

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Abstract: The problem MaxLin2 can be stated as follows. We are given a system $S$ of $m$ equations in variables $x_1,\mathrm{...},x_n$, where each equation is $su{m}_{iin{I}_j}{x}_i=b_j$ is assigned a positive integral weight $w_j$ and $x_i,b_{j}inmathbb{F}_2$, $I_{j}subseteq1,2,\mathrm{...},n$ for $j=1,\mathrm{...},m$. We are required to find an assignment of values to the variables in order to maximize the total weight of the satisfied equations. Let $W$ be the total weight of all equations in $S$. We consider the following parameterized version of MaxLin2: decide whether there is an assignment satisfying equations of total weight at least $W-k$, where $k$ is a nonnegative parameter. We prove that this parameterized problem is W[1]-hard even if each equation of $S$ has exactly three variables and every variable appears in exactly three equations and, moreover, each weight $w_j$ equals 1 and no two equations have the same left-hand side. We show the tightness of this result by proving that if each equation has at most two variables then the parameterized problem is fixed-parameter tractable. We also prove that if no variable appears in more than two equations then we can maximize the total weight of satisfied equations in polynomial time.

Recommendations

• Satisfying more than half of a system of linear equations over GF(2): a multivariate approach
• Simultaneously satisfying linear equations over \(\mathbb {F}_2\): MaxLin2 and Max-\(r\)-Lin2 parameterized above average
• Note on Max Lin-2 above average
• Systems of linear equations over \(\mathbb{F}_2\) and problems parameterized above average
• Solving linear equations parameterized by Hamming weight

Cites work

• A probabilistic approach to problems parameterized above or below tight bounds
• Algorithms with large domination ratio
• Almost 2-SAT is fixed-parameter tractable
• Compression via matroids: a randomized polynomial kernel for odd cycle transversal
• Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
• Faster parameterized algorithms using linear programming
• Improved parameterized algorithms for above average constraint satisfaction
• Parameterizing above or below guaranteed values
• Paths, flowers and vertex cover
• Simultaneously satisfying linear equations over \(\mathbb {F}_2\): MaxLin2 and Max-\(r\)-Lin2 parameterized above average
• Solving MAX-\(r\)-SAT above a tight lower bound
• Some optimal inapproximability results
• Systems of linear equations over \(\mathbb{F}_2\) and problems parameterized above average
• The Parametrized Complexity of Some Fundamental Problems in Coding Theory

Cited in

(11)

• Satisfying more than half of a system of linear equations over GF(2): a multivariate approach
• Simultaneously satisfying linear equations over \(\mathbb {F}_2\): MaxLin2 and Max-\(r\)-Lin2 parameterized above average
• Solving linear equations parameterized by Hamming weight
• Solving linear equations parameterized by Hamming weight
• Systems of linear equations over \(\mathbb{F}_2\) and problems parameterized above average
• scientific article; zbMATH DE number 6823767 (Why is no real title available?)
• Fixed-parameter tractability of error correction in graphical linear systems
• Parameterized constraint satisfaction problems: a survey
• Note on Max Lin-2 above average
• Almost consistent systems of linear equations
• Parameterized complexity classification for interval constraints

This page was built for publication: Parameterized complexity of satisfying almost all linear equations over \(\mathbb F_2\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2392244)