<p>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$. </p>

<p>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 <a href="http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=641542">proved</a> 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 <a href="http://authors.library.caltech.edu/5607/">Berlekamp and others</a> by reduction from <a href="http://en.wikipedia.org/wiki/3-dimensional_matching">3-dimensional matching</a> (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...</p>

<p>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, <a href="http://cseweb.ucsd.edu/~daniele/papers/DMS.pdf">Dumer and others</a> 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 <a href="http://www.di.ens.fr/~stern/data/St49b.pdf">Arora and others</a>, as far as I can tell using two methods: reducing from set cover, or reducing from label cover.</p>

CC BY-SA 3.0
2012-02-08T01:19:45.710Z
2012-02-08T04:27:33.113Z
2012-02-08T04:27:33.113Z
Sasho Nikolov
<p>Is there a reference for direct reduction of computing maximum independent set of a suitably constructed graph to computing minimum distance of a <a href="http://en.wikipedia.org/wiki/Linear_code" rel="nofollow">linear code</a> when the code is specified by its <a href="http://en.wikipedia.org/wiki/Check_matrix" rel="nofollow">parity check matrix</a>?</p>

CC BY-SA 3.0
2012-02-07T01:57:04.933Z
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
CC BY-SA 3.0
2012-02-07T15:19:23.430Z
maximal independent set $\neq$ maximum independent set!
Sasho Nikolov
CC BY-SA 3.0
2012-02-07T16:43:09.567Z
Can you give some reference (like wiki) about "minimum distance of code from parity check matrix"?
Peng Zhang
CC BY-SA 3.0
2012-02-07T17:54:46.237Z
yeah ok Q for poster can he convert to _maximum_ independent set instead given the two problems are closely related
vzn
CC BY-SA 3.0
2012-02-07T18:30:01.810Z
@SashoNikolov corrected
v s
CC BY-SA 3.0
2012-02-07T18:30:49.423Z
@PengZhang http://www.maths.manchester.ac.uk/~pas/code/notes/part12.pdf
v s
<cc.complexity-theory><reference-request><graph-theory><np-hardness><coding-theory>
reduction of maximum independet set to minimum distance of code
v s
# reduction of maximum independet set to minimum distance of code

(Asked by: username_0 on 2012-02-06)

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](http://en.wikipedia.org/wiki/Linear_code) when the code is specified by its [parity check matrix](http://en.wikipedia.org/wiki/Check_matrix)?

**Tags:** cc.complexity-theory, reference-request, graph-theory, np-hardness, coding-theory
> **Comments:**
> **username_1**: 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.  
> **username_2**: maximal independent set $\neq$ maximum independent set!  
> **username_3**: Can you give some reference (like wiki) about "minimum distance of code from parity check matrix"?  
> **username_1**: yeah ok Q for poster can he convert to _maximum_ independent set instead given the two problems are closely related  
> **username_0**: @SashoNikolov corrected  
> **username_0**: @PengZhang http://www.maths.manchester.ac.uk/~pas/code/notes/part12.pdf  

---

## 1 answers

### Answer by username_2 on 2012-02-08. Score: 5 | Accepted answer

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](http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=641542) 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](http://authors.library.caltech.edu/5607/) by reduction from [3-dimensional matching](http://en.wikipedia.org/wiki/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](http://cseweb.ucsd.edu/~daniele/papers/DMS.pdf) 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](http://www.di.ens.fr/~stern/data/St49b.pdf), as far as I can tell using two methods: reducing from set cover, or reducing from label cover.


---

