ECCC-Report TR14-096https://eccc.weizmann.ac.il/report/2014/096Comments and Revisions published for TR14-096en-usTue, 29 Jul 2014 14:30:24 +0300
Paper TR14-096
| Solving Linear Equations Parameterized by Hamming Weight |
Vikraman Arvind,
Johannes Köbler,
Sebastian Kuhnert,
Jacobo Toran
https://eccc.weizmann.ac.il/report/2014/096Given a system of linear equations $Ax=b$ over the binary field $\mathbb{F}_2$ and an integer $t\ge 1$, we study the following three algorithmic problems:
1. Does $Ax=b$ have a solution of weight at most $t$?
2. Does $Ax=b$ have a solution of weight exactly $t$?
3. 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, 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.Tue, 29 Jul 2014 14:30:24 +0300https://eccc.weizmann.ac.il/report/2014/096