Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR14-096 | 29th July 2014 14:13

Solving Linear Equations Parameterized by Hamming Weight



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

ISSN 1433-8092 | Imprint