<p>Computing min rank is NP-hard:</p>

<ul>
<li><p>Rene Peeters, "<a href="http://arno.uvt.nl/show.cgi?fid=95878" rel="nofollow">Orthogonal Representation over Finite Fields and the Chromic Numbr of Graphs</a>", 1996.</p></li>
<li><p>Salim Y. El Rouayheb, Mohammad Asad R. Chaudhry, Alex Sprintson, "<a href="http://arxiv.org/abs/0707.0860v1" rel="nofollow">On the Minimum Number of Transmissions in Single-Hop Wireless Coding Networks</a>", 2007.</p></li>
</ul>

CC BY-SA 3.0
2014-03-07T03:55:25.830Z
2014-03-07T04:58:26.597Z
2014-03-07T04:58:26.597Z
Salim
<p>In 1978 Willem H. Haemmers published "<a href="http://arno.uvt.nl/show.cgi?fid=80314" rel="nofollow">An upper bound on the Shannon capacity of a graph</a>".</p>

<p>Tims has a survey of more recent results <a href="http://orion.math.iastate.edu/lhogben/GeoffTimsThesis.pdf" rel="nofollow">his thesis</a>.</p>

<p>What is the computational complexity of computing Haemmer's minimum rank function?</p>

CC BY-SA 3.0
2014-02-18T18:13:25.173Z
I think this is the python code Timms used in his thesis if it is of any help in wrapping your head around the problem. https://github.com/jasongrout/minimum_rank/blob/master/minrank.py
Chad Brewbaker
<np-hardness><graph-colouring>
Complexity of Haemers' minimum rank
Chad Brewbaker
# Complexity of Haemers' minimum rank

(Asked by: username_0 on 2014-02-18)

In 1978 Willem H. Haemmers published "[An upper bound on the Shannon capacity of a graph](http://arno.uvt.nl/show.cgi?fid=80314)".

Tims has a survey of more recent results [his thesis](http://orion.math.iastate.edu/lhogben/GeoffTimsThesis.pdf).

What is the computational complexity of computing Haemmer's minimum rank function?

**Tags:** np-hardness, graph-colouring

> **Comments:**
> **username_0**: I think this is the python code Timms used in his thesis if it is of any help in wrapping your head around the problem. https://github.com/jasongrout/minimum_rank/blob/master/minrank.py  

---

## 1 answers

### Answer by username_1 on 2014-03-07. Score: 3 | Accepted answer

Computing min rank is NP-hard:

* Rene Peeters, "[Orthogonal Representation over Finite Fields and the Chromic Numbr of Graphs](http://arno.uvt.nl/show.cgi?fid=95878)", 1996.
* username_1 Y. El Rouayheb, Mohammad Asad R. Chaudhry, Alex Sprintson, "[On the Minimum Number of Transmissions in Single-Hop Wireless Coding Networks](http://arxiv.org/abs/0707.0860v1)", 2007.


---

