Solving Linear Equations Parameterized by Hamming Weight

Given a system of linear equations $Ax=b$ over the binary field ${{F}}_2$ and an integer $t\ge 1$ , we study the following three algorithmic problems:

Does $Ax=b$ have a solution of weight at most t?

Does $Ax=b$ have a solution of weight exactly t?

Does $Ax=b$ have a solution of weight at least t?

We investigate the parameterized complexity of these problems with t as parameter. A special aspect of our study is to show how the maximum multiplicity k of variable occurrences in $Ax=b$ influences the complexity of the problem. We show a sharp dichotomy: for each $k\ge 3$ the first two problems are $‐{W}[‐{1}]$ ‐hard [which strengthens and simplifies a result of Downey et al. (SIAM J Comput 29(2), 545–570, 1999)]. For $k=2$ , the problems turn out to be intimately connected to well‐studied matching problems and can be efficiently solved using matching algorithms.