27
$\begingroup$

What applications does the Vertex Cover Problem 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
Improve this question
$\endgroup$
9
  • 6
    $\begingroup$ one of the good example is at wiki on race condition: 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. $\endgroup$
    – singhsumit
    May 20, 2011 at 13:40
  • 5
    $\begingroup$ Why do you think that vertex cover has any real-world applications? $\endgroup$
    – Jukka Suomela
    May 20, 2011 at 14:00
  • 3
    $\begingroup$ 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. $\endgroup$
    – Jukka Suomela
    May 20, 2011 at 14:13
  • 3
    $\begingroup$ As noted at 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. $\endgroup$
    – András Salamon
    May 20, 2011 at 16:00
  • 5
    $\begingroup$ @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. $\endgroup$
    – Jukka Suomela
    May 20, 2011 at 17:53

5 Answers 5

Reset to default
14
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 5
    $\begingroup$ "at least not as artificial as the problems mentioned by Jukka Suomela" – and I tried to be careful to not mention any problems here! $\endgroup$
    – Jukka Suomela
    May 22, 2011 at 21:44
12
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 22
    $\begingroup$ 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). $\endgroup$
    – Jukka Suomela
    May 20, 2011 at 17:47
  • 1
    $\begingroup$ 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. $\endgroup$
    – Caleb Stanford
    Oct 12, 2019 at 16:36
10
$\begingroup$

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.

Improve this answer
$\endgroup$
1
$\begingroup$

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/

Improve this answer
$\endgroup$
1
$\begingroup$

To me it was somewhat surprising that minimal vertex cover is a subproblem of the 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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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