Is there a reference for direct reduction of computing maximum independent set of a suitably constructed graph to computing minimum distance of a linear code when the code is specified by its parity check matrix?

  • $\begingroup$ maximal indpendent set is NP complete right? so just prove the 1st part ie "reduction of computing minimum distance of code from parity check matrix" [what exactly is that anyway?] is NP complete. then that does not give a "direct" reduction but one can be assured a reduction exists. $\endgroup$ – vzn Feb 7 '12 at 1:57
  • 5
    $\begingroup$ maximal independent set $\neq$ maximum independent set! $\endgroup$ – Sasho Nikolov Feb 7 '12 at 15:19
  • $\begingroup$ Can you give some reference (like wiki) about "minimum distance of code from parity check matrix"? $\endgroup$ – Peng Zhang Feb 7 '12 at 16:43
  • $\begingroup$ yeah ok Q for poster can he convert to maximum independent set instead given the two problems are closely related $\endgroup$ – vzn Feb 7 '12 at 17:54
  • $\begingroup$ @SashoNikolov corrected $\endgroup$ – v s Feb 7 '12 at 18:30

For the benefit of the others, the minimum code distance problem for codes over $\mathbb{F}_2$ is: given a matrix $H$ ($m$ by $n$, with elements from $\mathbb{F}_2$) and a positive integer $w$, does there exist a vector $x$ such that $Hx = 0$ and the hamming weight (number of 1's) of $x$ is at most $w$.

Since both max ind set and the minimum distance of a linear code are NP complete, there are many-one reductions in either direction. However, it doesn't seem that any of the reductions in the literature that I have seen are directly from max independent set. Actually it seems that the known reductions are from other problems related to coding. Alexander Vardy proved the NP-hardness of computing the min distance by reducing from the max-likelihood decoding problem: given a matrix $H$ over $\mathbb{F}_2$, a vector $s$ and a positive integer $w$, does there exist a vector $x$ such that $Hx = s$ and the weight of $x$ is at most $w$. This problem was shown to be NP-hard by Berlekamp and others by reduction from 3-dimensional matching (which is one of the Karp problems and can be reduced to from 3SAT). If you want to reduce max independent set to 3SAT and piece together all these reductions, I guess you can get what you want...

There is a line of work that looks at hardness of approximating the min distance problem. However, reductions there are also from other coding problems. For example, Dumer and others show a hardness of approximation result for the min distance problem by reducing from the nearest codeword problem (given a message find the nearest codeword in hamming distance). A hardness of approximation result for the latter problem was proved by Arora and others, as far as I can tell using two methods: reducing from set cover, or reducing from label cover.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.