TR14-096 Authors: Vikraman Arvind, Sebastian Kuhnert, Johannes Köbler, Jacobo Toran

Publication: 29th July 2014 14:30

Downloads: 2210

Keywords:

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.