<p>An example might be that the edges of the graph represent roads while the vertices represent the crossroads.
The task is to place security cameras at the crossroads in a way that will let you see the whole city but it is desirable to use as less cameras as possible in order to save money.</p>

CC BY-SA 3.0
2011-05-20T17:47:55.567Z
The problem with examples like this is that they tend to be toy examples. They can be used to illustrate the definition, but I don't think it is possible to find references to *real-world* examples where where people have actually chosen the locations of the security cameras by finding a minimum vertex cover. Real-world problems like this tend to have additional constraints, many of which are not even well-defined, and the solutions tend to be greedy and incremental (first install a couple of security cameras in the most critical locations, and then put some more when we get more funds).
Jukka Suomela
CC BY-SA 4.0
2019-10-12T16:36:02.760Z
I would push back a bit on Jukka's objection. It is valuable to distill a problem to the core part that is computationally or conceptually challenging. Despite all of the additional real-world constraints, I think that the *core computational difficulty* in selecting cameras to cover a space in the real world is, essentially, a vertex cover problem. Of course in this case an approximation algorithm is perfectly fine; finding the best vertex cover is not necessary. And in this case the graphs will be fairly simple, perhaps planar for example.
Caleb Stanford
CC BY-SA 3.0
2011-05-20T15:24:51.207Z
2011-05-20T15:24:51.207Z
galbarm
<p>Some problems in the area of computational biology seem suitable for practical applications that are not artificial - or at least not as artificial as the problems mentioned by Jukka Suomela.</p>

<p>For instance, people often mention the work by F. Abu-Khzam, R. Collins, M. Fellows, M. Langston, W. Suters C. Symons, <em>Kernelization Algorithms for the Vertex Cover Problem: Theory and Experiments</em>, Proceedings of the 6th Workshop on Algorithm Engineering and Experiments (ALENEX), ACM/SIAM, Proc. Applied Mathematics 115, 2004.</p>

<p>As the authors state, "One of the applications to which we have applied our methods involves finding phylogenetic trees based on protein domain information, ..." (section 8 of above paper).</p>

<p>A subset of the authors have similar papers on this topic, see, e.g., Faisal N. Abu-Khzam, Michael A. Langston, Pushkar Shanbhag and Christopher T. Symons, <em>Scalable Parallel Algorithms for FPT Problems</em>, Algorithmica, Volume 45, Number 3, 269-284.</p>

<p>I'm not sure whether the instances used in the experiments were real-world instances or artificial, but I hope the two references give you a good starting point.</p>

CC BY-SA 3.0
2011-05-22T21:44:32.790Z
"at least not as artificial as the problems mentioned by Jukka Suomela" – and I tried to be careful to not mention *any* problems here!
Jukka Suomela
CC BY-SA 3.0
2011-05-22T21:15:48.193Z
2011-05-22T21:15:48.193Z
Alexander Langer
<p>You may also take a look at <a href="http://www.dharwadker.org/pirzada/applications/">http://www.dharwadker.org/pirzada/applications/</a>.
It's about applications of Graph Theory. It states some applications for vertex cover too, like in biochemistry and solving the SNP assembly problem or in a computer network security problem.</p>

CC BY-SA 3.0
2012-10-29T09:09:41.917Z
2012-10-29T09:09:41.917Z
saeedn
<p>Vertex cover (rather, various computations/approximations of it) was the main algorithmic engine in our paper on nearest-neighbor classification:
<a href="http://ieeexplore.ieee.org/document/6867374/" rel="nofollow noreferrer">http://ieeexplore.ieee.org/document/6867374/</a></p>

CC BY-SA 3.0
2017-05-16T19:15:54.857Z
2017-05-16T19:15:54.857Z
Aryeh
<p>To me it was somewhat surprising that minimal vertex cover is a subproblem of the <a href="https://en.wikipedia.org/wiki/Hungarian_algorithm" rel="nofollow noreferrer">Hungarian Algorithm</a>, namely when determining a minimal set of horizontal or vertical lines that cover all the zeros that were generated by subtracting row and column minima.  </p>

<p>That amounts to finding a minimal vertex cover in a <em>bipartite</em> graph which, also surprisingly, can be solved in polynomial time <a href="https://tryalgo.org/en/matching/2016/08/05/konig/" rel="nofollow noreferrer">nicely described here</a>  </p>

CC BY-SA 4.0
2019-10-12T13:58:57.887Z
2019-10-12T13:58:57.887Z
Manfred Weis
<p>What applications does the <a href="http://en.wikipedia.org/wiki/Vertex_cover">Vertex Cover Problem</a> have in the real world?</p>

<p>Which industry or research projects use actually implemented software that is based on theoretical results for the Vertex Cover problem? In particular, are any of the following theoretical results implemented in used software?</p>

<ul>
<li>Approximation algorithms for Vertex Cover</li>
<li>Exponential-time algorithms for Vertex Cover</li>
<li>Fixed-parameter tractable algorithms for Vertex Cover</li>
<li>Kernelization algorithms for Vertex Cover</li>
</ul>

CC BY-SA 3.0
2011-05-20T13:40:52.383Z
one of the good example is at wiki on race condition: http://en.wikipedia.org/wiki/Vertex_cover#Examples Also as a motivation people give example of monitoring. At each vertex of the solution, we keep a monitor. I personally think that googling out this answer is a better option than asking it here.
singhsumit
CC BY-SA 3.0
2011-05-20T13:52:49.283Z
i tried to Google.. but all i can find are papers about vertex cover.
scatman
CC BY-SA 3.0
2011-05-20T14:00:08.227Z
Why do you think that vertex cover has any real-world applications?
Jukka Suomela
CC BY-SA 3.0
2011-05-20T14:09:45.120Z
debating whether this is too localized ? OTOH, I've wondered this myself for a long time.
Suresh Venkat
CC BY-SA 3.0
2011-05-20T14:13:00.040Z
I guess the answer is that vertex covers don't have significant applications. But people study them because vertex covers are a simple special case of the set cover problem. Set covers do have applications. And you can't really understand the computational complexity of the set cover problem if you don't first understand the simple (and not-so-simple) special cases such as vertex covers, edge covers, dominating sets, etc.
Jukka Suomela
CC BY-SA 3.0
2011-05-20T16:00:56.687Z
As noted at http://en.wikipedia.org/wiki/Vertex_cover#Properties the vertices not in a smallest vertex cover form a largest independent set, so these are essentially the same problem.  There are many real-world applications of the independent set problem, for instance because every constraint satisfaction problem can be directly reduced to it.
András Salamon
CC BY-SA 3.0
2011-05-20T17:53:46.513Z
@András: This is a good point, but the correspondence only hold for the smallest vertex cover and the largest independent set. From the perspective of exact algorithms, these are essentially the same problem, but if we are interested in efficient algorithms, we are usually content with some kind of approximations. And then it turns out that the vertex cover problem has unique properties that are not shared with the independent set problem. My favourite example comes from distributed computing: small vertex covers do not require symmetry-breaking, large independent sets require it.
Jukka Suomela
CC BY-SA 3.0
2011-05-20T18:21:11.107Z
@Jukka: Good point.  Expanding, vertex cover is FPT while independent set is W[1]-hard.  Niedermeier and Rossmanith actually mentioned some applications of vertex cover in http://dx.doi.org/10.1007/3-540-49116-3_53 related to resolving conflicts in gene sequencing.
András Salamon
CC BY-SA 3.0
2011-06-16T15:42:56.647Z
this should probably be a community wiki.
Holger
<ds.algorithms><graph-theory><graph-algorithms>
Vertex Cover applications in the real world
scatman
# Vertex Cover applications in the real world

(Asked by: username_0 on 2011-05-20)

What applications does the [Vertex Cover Problem](http://en.wikipedia.org/wiki/Vertex_cover) have in the real world?

Which industry or research projects use actually implemented software that is based on theoretical results for the Vertex Cover problem? In particular, are any of the following theoretical results implemented in used software?

* Approximation algorithms for Vertex Cover
* Exponential-time algorithms for Vertex Cover
* Fixed-parameter tractable algorithms for Vertex Cover
* Kernelization algorithms for Vertex Cover

**Tags:** ds.algorithms, graph-theory, graph-algorithms
> **Comments:**
> **username_1**: one of the good example is at wiki on race condition: http://en.wikipedia.org/wiki/Vertex_cover#Examples Also as a motivation people give example of monitoring. At each vertex of the solution, we keep a monitor. I personally think that googling out this answer is a better option than asking it here.  
> **username_0**: i tried to Google.. but all i can find are papers about vertex cover.  
> **username_2**: Why do you think that vertex cover has any real-world applications?  
> **username_3**: debating whether this is too localized ? OTOH, I've wondered this myself for a long time.  
> **username_2**: I guess the answer is that vertex covers don't have significant applications. But people study them because vertex covers are a simple special case of the set cover problem. Set covers do have applications. And you can't really understand the computational complexity of the set cover problem if you don't first understand the simple (and not-so-simple) special cases such as vertex covers, edge covers, dominating sets, etc.  
> **username_4**: As noted at http://en.wikipedia.org/wiki/Vertex_cover#Properties the vertices not in a smallest vertex cover form a largest independent set, so these are essentially the same problem.  There are many real-world applications of the independent set problem, for instance because every constraint satisfaction problem can be directly reduced to it.  
> **username_2**: @András: This is a good point, but the correspondence only hold for the smallest vertex cover and the largest independent set. From the perspective of exact algorithms, these are essentially the same problem, but if we are interested in efficient algorithms, we are usually content with some kind of approximations. And then it turns out that the vertex cover problem has unique properties that are not shared with the independent set problem. My favourite example comes from distributed computing: small vertex covers do not require symmetry-breaking, large independent sets require it.  
> **username_4**: @Jukka: Good point.  Expanding, vertex cover is FPT while independent set is W[1]-hard.  Niedermeier and Rossmanith actually mentioned some applications of vertex cover in http://dx.doi.org/10.1007/3-540-49116-3_53 related to resolving conflicts in gene sequencing.  
> **username_5**: this should probably be a community wiki.  

---

## 5 answers

### Answer by username_8 on 2011-05-22. Score: 15

Some problems in the area of computational biology seem suitable for practical applications that are not artificial - or at least not as artificial as the problems mentioned by Jukka Suomela.

For instance, people often mention the work by F. Abu-Khzam, R. Collins, M. Fellows, M. Langston, W. Suters C. Symons, *Kernelization Algorithms for the Vertex Cover Problem: Theory and Experiments*, Proceedings of the 6th Workshop on Algorithm Engineering and Experiments (ALENEX), ACM/SIAM, Proc. Applied Mathematics 115, 2004.

As the authors state, "One of the applications to which we have applied our methods involves finding phylogenetic trees based on protein domain information, ..." (section 8 of above paper).

A subset of the authors have similar papers on this topic, see, e.g., Faisal N. Abu-Khzam, Michael A. Langston, Pushkar Shanbhag and Christopher T. Symons, *Scalable Parallel Algorithms for FPT Problems*, Algorithmica, Volume 45, Number 3, 269-284.

I'm not sure whether the instances used in the experiments were real-world instances or artificial, but I hope the two references give you a good starting point.

> **Comments:**
> **username_2**: "at least not as artificial as the problems mentioned by Jukka Suomela" – and I tried to be careful to not mention *any* problems here!  

---

### Answer by username_6 on 2011-05-20. Score: 12

An example might be that the edges of the graph represent roads while the vertices represent the crossroads.
The task is to place security cameras at the crossroads in a way that will let you see the whole city but it is desirable to use as less cameras as possible in order to save money.

> **Comments:**
> **username_2**: The problem with examples like this is that they tend to be toy examples. They can be used to illustrate the definition, but I don't think it is possible to find references to *real-world* examples where where people have actually chosen the locations of the security cameras by finding a minimum vertex cover. Real-world problems like this tend to have additional constraints, many of which are not even well-defined, and the solutions tend to be greedy and incremental (first install a couple of security cameras in the most critical locations, and then put some more when we get more funds).  
> **username_7**: I would push back a bit on Jukka's objection. It is valuable to distill a problem to the core part that is computationally or conceptually challenging. Despite all of the additional real-world constraints, I think that the *core computational difficulty* in selecting cameras to cover a space in the real world is, essentially, a vertex cover problem. Of course in this case an approximation algorithm is perfectly fine; finding the best vertex cover is not necessary. And in this case the graphs will be fairly simple, perhaps planar for example.  

---

### Answer by username_9 on 2012-10-29. Score: 10

You may also take a look at <http://www.dharwadker.org/pirzada/applications/>.
It's about applications of Graph Theory. It states some applications for vertex cover too, like in biochemistry and solving the SNP assembly problem or in a computer network security problem.


---

### Answer by username_10 on 2017-05-16. Score: 1

Vertex cover (rather, various computations/approximations of it) was the main algorithmic engine in our paper on nearest-neighbor classification:
<http://ieeexplore.ieee.org/document/6867374/>


---

### Answer by username_11 on 2019-10-12. Score: 1

To me it was somewhat surprising that minimal vertex cover is a subproblem of the [Hungarian Algorithm](https://en.wikipedia.org/wiki/Hungarian_algorithm), namely when determining a minimal set of horizontal or vertical lines that cover all the zeros that were generated by subtracting row and column minima.

That amounts to finding a minimal vertex cover in a *bipartite* graph which, also surprisingly, can be solved in polynomial time [nicely described here](https://tryalgo.org/en/matching/2016/08/05/konig/)


---

