# reduction of maximum independet set to minimum distance of code

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?

• 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. – vzn Feb 7 '12 at 1:57
• maximal independent set $\neq$ maximum independent set! – Sasho Nikolov Feb 7 '12 at 15:19
• Can you give some reference (like wiki) about "minimum distance of code from parity check matrix"? – Peng Zhang Feb 7 '12 at 16:43
• yeah ok Q for poster can he convert to maximum independent set instead given the two problems are closely related – vzn Feb 7 '12 at 17:54
• @SashoNikolov corrected – 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...