The vertex-cover problem

Problem Description

Given a universe U of n elements, a collection of subsets of U say S = {S1, S2…,Sm} where every subset Si has an associated cost. Find a minimum cost subcollection of S that covers all elements of U.

It was one of Karp’s NP-complete problems, shown to be so in 1972. Other applications: edge covering, vertex cover Interesting example: IBM finds computer viruses (wikipedia) Elements- 5000 known viruses Sets- 9000 substrings of 20 or more consecutive bytes from viruses, not found in ‘good’ code. A set cover of 180 was found. It suffices to search for these 180 substrings to verify the existence of known computer viruses.

Improvement Table

Complexity Classes	Algorithm Paper Links	Lower Bounds Paper Links
Exp/Factorial	[ Naive algorithm (1940)] [ Random Split Exponential algorithm (1940)] Horowitz and Sahni (1974) [- dynamic programming algorithm (1956)] Psinger; 1999 (1999) Koiliaris and Xu 2015 (2015) Bringmann 2017 (2017) [ Pisinger 2003 (2003)] Faaland 1973 (1973) [ Pferschy 1999 (1999)] [ Klinz 1999 (1999)] [ Epstein 1997 (1997)] [ Serang 2014 (2014)] [ Serang 2015 (2015)] [ Lokshtanov (2010)]
Polynomial > 3
Cubic
Quadratic
nlogn
Linear
logn