Solving Linear Equations Parameterized by Hamming Weight

Given a system of linear equations $$Ax=b$$Ax=b over the binary field $$\mathbb {F}_2$$F2 and an integer $$t\ge 1$$tź1, we study the following three algorithmic problems:1.Does $$Ax=b$$Ax=b have a solution of weight at most t?2.Does $$Ax=b$$Ax=b have a solution of weight exactly t?3.Does $$Ax=b$$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$$Ax=b influences the complexity of the problem. We show a sharp dichotomy: for each $$k\ge 3$$kź3 the first two problems are $$\textsf {W[1] }$$W[1]-hard [which strengthens and simplifies a result of Downey et al. (SIAM J Comput 29(2), 545---570, 1999)]. For $$k=2$$k=2, the problems turn out to be intimately connected to well-studied matching problems and can be efficiently solved using matching algorithms.