The Vertex Cover AlgorithmAshay DharwadkerH501 Palam Vihar District Gurgaon Haryana 122017 India 


We present a new polynomialtime
algorithm for finding minimal vertex covers in graphs. It is shown that
every graph with n vertices and maximum vertex degree Δ
must have a minimum vertex cover of size at most n−⌈n/(Δ+1)⌉
and that this condition is the best possible in terms of n and Δ.
The algorithm finds a minimum vertex cover in all known examples of graphs.
In view of the importance of the
P versus NP question, we
ask if there exists a graph for which the algorithm cannot find a minimum
vertex cover. The algorithm is demonstrated by finding minimum vertex covers
for several famous graphs, including two large benchmark graphs with hidden
minimum vertex covers. We implement the algorithm in C++ and provide a
demonstration program for Microsoft Windows [download].


Thanks to Klaus D. Witzel
for providing Example 7.20 that serves as the main benchmark for testing
whether this algorithm actually finds a minimum vertex cover in the hardest
known cases. A team of computer scientists led by Eric Filiol at the
Virology and Cryptology Lab, ESAT, and the French Navy, ESCANSIC,
have recently used this algorithm to simulate the propagation of stealth worms and design optimal strategies for protecting
large computer networks against such virus attacks in realtime.
This algorithm has also been cited in Applications of Graph Theory published by the
Korean Society for Industrial and Applied Mathematics. We are pleased to announce that
The Vertex Cover Algorithm has been published by
Amazon in 2011.


In 1972, Karp [1]
introduced a list of twentyone
NPcomplete problems, one of which
was the problem of finding a minimum vertex cover in a graph. Given a graph,
one must find a smallest set of vertices such that every edge has at least
one end vertex in the set. Such a set of vertices is called a minimum vertex
cover of the graph and in general can be very difficult to find. For example,
try to find a minimum vertex cover with seven vertices in the Frucht graph
[2]
shown below in Figure 1.1.
We present a new polynomialtime VERTEX COVER ALGORITHM for finding minimal vertex covers in graphs. In Section 2, we provide precise DEFINITIONS of all the terminology used. In Section 3, we present a formal description of the ALGORITHM followed by a small example to show how the algorithm works stepbystep. In Section 4, we show that the algorithm has polynomialtime COMPLEXITY. In Section 5, we give a new condition of SUFFICIENCY for a graph to have a minimum vertex cover of a certain size. We prove that every graph with n vertices and maximum vertex degree Δ must have a minimum vertex cover of size at most n−⌈n/(Δ+1)⌉ and that the algorithm will always find a vertex cover of at most this size. Furthermore, we prove that this condition is the best possible in terms of n and Δ by explicitly constructing graphs for which the size of a minimum vertex cover is exactly n−⌈n/(Δ+1)⌉. For all known examples of graphs, the algorithm finds a minimum vertex cover. In view of the importance of the P versus NP question [3], we ask: does there exist a graph for which this algorithm cannot find a minimum vertex cover? In Section 6, we provide an IMPLEMENTATION of the algorithm as a C++ program, together with demonstration software for Microsoft Windows. In Section 7, we demonstrate the algorithm by finding minimum vertex covers for several EXAMPLES of famous graphs, including two large benchmark graphs with hidden minimum vertex covers. In Section 8, we list the REFERENCES. 
We begin with precise definitions of all
the terminology and notation used in this presentation, following [4].
We use the usual notation
⌊x⌋
to denote the floor function i.e. the greatest integer not greater
than x and ⌈x⌉
to denote the ceiling function i.e. the least integer not less than
x.
A simple graph G with n vertices consists of a set of vertices V, with V = n, and a set of edges E, such that each edge is an unordered pair of distinct vertices. Note that the definition of G explicitly forbids loops (edges joining a vertex to itself) and multiple edges (many edges joining a pair of vertices), whence the set E must also be finite. We may label the vertices of G with the integers 1, 2, …, n. If the unordered pair of vertices {u, v} is an edge in G, we say that u is a neighbor of v and write uv∈E. Neighborhood is clearly a symmetric relationship: uv∈E if and only if vu∈E. The degree of a vertex v, denoted by d(v), is the number of neighbors of v. The maximum degree over all vertices of G is denoted by Δ. The adjacency matrix of G is an n×n matrix with the entry in row u and column v equal to 1 if uv∈E and equal to 0 otherwise. A clique Q of G is a set of vertices such that every unordered pair of vertices in Q is an edge. An independent set S of G is a set of vertices such that no unordered pair of vertices in S is an edge. A vertex cover C of G is a set of vertices such that for every edge {u,v} of G at least one of u or v is in C. Given a vertex cover C of G and a vertex v in C, we say that v is removable if the set C−{v} is still a vertex cover of G. Denote by ρ(C) the number of removable vertices of a vertex cover C of G. A minimal vertex cover has no removable vertices. A minimum vertex cover is a vertex cover with the least number of vertices. Note that a minimum vertex cover is always minimal but not necessarily vice versa. An algorithm is a problemsolving method suitable for implementation as a computer program. While designing algorithms we are typically faced with a number of different approaches. For small problems, it hardly matters which approach we use, as long as it is one that solves the problem correctly. However, there are many problems for which the only known algorithms take so long to compute the solution that they are practically useless. A polynomialtime algorithm is one whose number of computational steps is always bounded by a polynomial function of the size of the input. Thus, a polynomialtime algorithm is one that is actually useful in practice. The class of all such problems that have polynomialtime algorithms is denoted by P. For some problems, there are no known polynomialtime algorithms but these problems do have nondeterministic polynomialtime algorithms: try all candidates for solutions simultaneously and for each given candidate, verify whether it is a correct solution in polynomialtime. The class of all such problems is denoted by NP. Clearly P ⊆ NP. On the other hand, there are problems that are known to be in NP and are such that any polynomialtime algorithm for them can be transformed (in polynomialtime) into a polynomialtime algorithm for every problem in NP. Such problems are called NPcomplete. The problem of finding a minimum vertex cover is known to be NPcomplete [1]. Thus, if we are able to show the existence of a polynomialtime algorithm that finds a minimum vertex cover in any graph, we could prove that P = NP. The present algorithm is, so far as we know, a promising candidate for the task. One of the greatest unresolved problems in mathematics and computer science today is whether P = NP or P ≠ NP [3]. 
We now present a formal description of
the algorithm. This is followed by a small example illustrating the steps
of the algorithm. We start by defining two procedures.
3.1. Procedure. Given a simple graph G with n vertices and a vertex cover C of G, if C has no removable vertices, output C. Else, for each removable vertex v of C, find the number ρ(C−{v}) of removable vertices of the vertex cover C−{v}. Let v_{max} denote a removable vertex such that ρ(C−{v_{max}}) is a maximum and obtain the vertex cover C−{v_{max}}. Repeat until the vertex cover has no removable vertices. 3.2. Procedure. Given a simple graph G with n vertices and a minimal vertex cover C of G, if there is no vertex v in C such that v has exactly one neighbor w outside C, output C. Else, find a vertex v in C such that v has exactly one neighbor w outside C. Define C^{v}^{,w} by removing v from C and adding w to C. Perform procedure 3.1 on C^{v}^{,w} and output the resulting vertex cover. 3.3. Algorithm. Given as input a simple graph G with n vertices labeled 1, 2, …, n, search for a vertex cover of size at most k. At each stage, if the vertex cover obtained has size at most k, then stop.
V = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10,11, 12}.
We search for a vertex cover of size at most k = 7. Part I for i = 1 and i = 2 yields vertex covers C_{1} and C_{2} of size 8, so we give the details starting from i = 3. We initialize the vertex cover as C_{3 }= V−{3}={1, 2, 4, 5, 6, 7, 8, 9, 10, 11, 12}. We now perform procedure 3.1. Here are the results in tabular form:
We obtain a minimal vertex cover C_{3 }= {1, 2, 4, 6, 8, 9, 10} of the requested size k = 7 and the algorithm terminates. 
The algorithm may be applied to any simple
graph and will always terminate in polynomialtime, finding many minimal
vertex covers. The propositions below establish sufficient conditions on
the input graph which guarantee that the algorithm will find minimal vertex
covers of a certain size. Specifically, we prove that every graph with
n
vertices and maximum vertex degree Δ must have
a minimum vertex cover of size at most n−⌈n/(Δ+1)⌉
and that the algorithm will always find a vertex cover of at most this
size. Furthermore, we prove that this condition is the best possible in
terms of n and Δ by explicitly constructing
graphs for which the size of a minimum vertex cover is exactly
n−⌈n/(Δ+1)⌉.
The proofs use two fundamental axioms: Euclid's Division Lemma [5]
and the Pigeonhole Principle [6].
Euclid's Division Lemma. Given a positive integer m and any integer n, there exist unique integers q and r with 0 ≤ r < m such that n = qm+r. Pigeonhole Principle. If l letters are distributed into p pigeonholes, then some pigeonhole receives at least ⌈l/p⌉ letters and some pigeonhole receives at most ⌊l/p⌋ letters. 5.1. Proposition. Given a simple graph G with n vertices and an initial vertex cover C. At each stage of procedure 3.1, if the vertex cover C has l vertices and the maximum degree among the vertices outside C is less than ⌈l/(n−l)⌉, then procedure 3.1 produces a strictly smaller vertex cover. Proof. By contradiction. Suppose the vertex cover C is minimal. Then there are no removable vertices and every vertex in C must have a neighbor outside C. Thus there are at least l edges (letters) with one end vertex in C and the other end vertex outside C, there being exactly p = n−l vertices outside C (pigeonholes). By the pigeonhole principle, some vertex outside C must receive at least ⌈l/p⌉ edges contradicting the hypothesis that the maximum degree among the vertices outside C is less than ⌈l/p⌉. ☐ 5.2. Proposition. Given a vertex cover C of G, procedure 3.1 always produces a minimal vertex cover of G. Proof. Procedure 3.1 terminates only when there are no removable vertices. By definition, the resulting vertex cover must be minimal. ☐ 5.3. Proposition. Given a simple graph G with n vertices and an initial minimal vertex cover C. If the minimal vertex cover C has m vertices and the maximum degree among the vertices outside C is less than ⌈2m/(n−m)⌉, then there exists a vertex v in C such that v has exactly one neighbor w outside C and procedure 3.2 produces a minimal vertex cover different from C and of size less than or equal to the size of C. Proof. By contradiction. Note that since C is minimal, there are no removable vertices and every vertex in C has at least one neighbor outside C. Suppose every vertex in C has more than one neighbor outside C. Then there are at least l = 2m edges (letters) with one end vertex in C and the other end vertex outside C, there being exactly p = n−m vertices outside C (pigeonholes). By the pigeonhole principle, some vertex outside C must receive at least ⌈l/p⌉ edges contradicting the hypothesis that the maximum degree among the vertices outside C is less than ⌈l/p⌉. Thus, there exists a vertex v in C such that v has exactly one neighbor w outside C. Now since procedure 3.2 exchanges v and w, a vertex cover different from C but of the same size as C is created. Note that in the process some vertices of the vertex cover might have become removable. Then, procedure 3.2 applies procedure 3.1 that produces a minimal vertex cover different from C and of size less than or equal to the size of C. ☐ 5.4. Proposition. Given a simple graph G with n vertices and maximum vertex degree Δ, the algorithm always finds a minimal vertex cover of size at most n−⌈n/(Δ+1)⌉. Proof. Consider any one turn of part I in the algorithm. After t vertices have been removed from a total of n, the vertex cover C has l = n−t vertices and the maximum degree among the vertices outside C is certainly less than or equal to Δ. By proposition 5.1, if Δ is less than ⌈l/(n−l)⌉ = ⌈(n−t)/(n−(n−t))⌉ = ⌈(n−t)/t⌉ = ⌈(n/t)−1⌉, then a strictly smaller vertex cover is produced by the removal of a vertex. Hence, as long as t is less than ⌈n/(Δ+1)⌉, a vertex can still be removed and procedure 1 continues. Thus, at least ⌈n/(Δ+1)⌉ are removed, leaving a vertex cover of size at most n−⌈n/(Δ+1)⌉. By propositions 5.1, 5.2 and 5.3, all of the vertex covers produced by the algorithm are minimal and of size at most n−⌈n/(Δ+1)⌉. ☐ 5.5. Proposition. A simple graph G with n vertices and maximum vertex degree Δ has a minimal vertex cover of size at most n−⌈n/(Δ+1)⌉. Proof. By proposition 5.4, the algorithm finds a minimal vertex cover of size at most n−⌈n/(Δ+1)⌉. ☐ 5.6. Proposition. Given any positive integers n and Δ such that 0 < Δ < n, there exists a graph G with maximum vertex degree Δ and a minimum vertex cover of size n−⌈n/(Δ+1)⌉. For any such graph the algorithm always finds a minimum vertex cover. Proof. Let n = q(Δ+1)+r with 0 ≤ r < Δ+1 by Euclid's division lemma. There are two cases.

We demonstrate the algorithm with a C++
program following the style of [7]. The demonstration
program package [download] contains
a detailed help file and section 7 gives several examples of input/output
files for the program.

We demonstrate the algorithm by running
the program on several famous graphs and two large benchmark graphs with
hidden minimum vertex covers. In each case, the algorithm finds a minimum
vertex cover in polynomialtime.
7.1. The Tetrahedron [8]. We run the program
on the graph of the Tetrahedron with n = 4 vertices. The algorithm
finds a minimum vertex cover of size k = 3.
7.2. The Kuratowski Bipartite Graph K_{3, 3 }[9].
We run the program on the Kuratowski bipartite graph
K_{3, 3}
with n = 6 vertices. The algorithm finds a minimum vertex cover
of size k = 3.
7.3. The Octahedron [8]. We run the program
on the graph of the Octahedron with n = 6 vertices. The algorithm
finds a minimum vertex cover of size k = 4.
7.4. The BondyMurty Graph G_{1 }[4].
We run the program on the BondyMurty graph G_{1} with n
= 7 vertices. The algorithm finds a minimum vertex cover of size k
= 4.
7.5. The Wheel Graph W_{8 }[4].
We run the program on the Wheel graph W_{8} with n
= 8 vertices. The algorithm finds a minimum vertex cover of size k
= 5.
7.6. The Cube [8]. We run the program on the
graph of the Cube with
n = 8 vertices. The algorithm finds a minimum
vertex cover of size
k = 4.
7.7. The Petersen Graph [10]. We run the program
on the Petersen graph with n = 10 vertices. The algorithm finds
a minimum vertex cover of size k = 6.
7.8. The BondyMurty graph G_{2 }[4].
We run the program on the BondyMurty graph G_{2} with n
= 11 vertices. The algorithm finds a minimum vertex cover of size k
= 7.
7.9. The Grötzsch Graph [11]. We run the
program on the Grötzsch graph with
n = 11 vertices. The algorithm
finds a minimum vertex cover of size
k = 6.
7.10. The Herschel Graph [12]. We run the program
on the Herschel graph with
n = 11 vertices. The algorithm finds
a minimum vertex cover of size
k = 5.
7.11. The Icosahedron [8]. We run the program
on the graph of the Icosahedron with n = 12 vertices. The algorithm
finds a minimum vertex cover of size k = 9.
7.12. The BondyMurty graph G_{3 }[4].
We run the program on the BondyMurty graph G_{3} with n
= 14 vertices. The algorithm finds a minimum vertex cover of size k
= 7.
7.13. The BondyMurty graph G_{4 }[4].
We run the program on the BondyMurty graph G_{4} with n
= 16 vertices. The algorithm finds a minimum vertex cover of size k
= 7.
7.14. The Ramsey Graph R(4,4) [6]. We
run the program on the Ramsey graph R(4,4) with n = 17 vertices.
The algorithm finds a minimum vertex cover of size k = 14.
7.15. The Folkman Graph [13]. We run the program
on the Folkman graph with n = 20 vertices. The algorithm finds a
minimum vertex cover of size k = 10.
7.16. The Dodecahedron [8]. We run the program
on the graph of the Dodecahedron with n = 20 vertices. The algorithm
finds a minimum vertex cover of size k = 12.
7.17. The TutteCoxeter Graph [14]. We run the
program on the TutteCoxeter graph with n = 30 vertices. The algorithm
finds a minimum vertex cover of size k = 15.
7.18. The Thomassen Graph [15]. We run the program
on the Thomassen graph with
n = 34 vertices. The algorithm finds
a minimum vertex cover of size
k = 20.
7.19. The Berge Graph [16]. This is the first
benchmark graph with
n = 60 vertices, following a construction due
to Claude Berge. Let G denote the graph of the Dodecahedron and
let H = K_{3} denote the graph of the Triangle i.e.
the clique on three vertices. The
Berge graph G ×
H
is defined as the graph whose set of vertices is V(G)
×
V(H)
with an edge connecting vertex (u_{1},v_{1})
with vertex (u_{2},v_{2}) if and only if
either u_{1 }= u_{2} and {v_{1},
v_{2}}
is an edge in H or v_{1 }=
v_{2}
and {u_{1},
u_{2}} is an edge in G.
It is known that the vertices of the Dodecahedron can be properly coloured
with three colours. As a consequence, the Berge graph should have a vertex
cover with at most forty vertices. Indeed, the algorithm finds a minimum
vertex cover of size k = 40.
7.20. The Witzel Graph [17]. This is the second
benchmark graph with
n = 450 vertices, following a construction
due to Klaus D. Witzel. Take thirty disjoint cliques on fifteen vertices
and connect random pairs of cliques by random edges. Shuffle the labels
of the vertices well so that the original cliques are hidden. Provided
this is done carefully without adding too many extra edges, such a graph
should have a minimum vertex cover with at most 420 vertices (all but one
vertex from each original clique). Moreover, the minimum vertex cover is
well and truly hidden. Indeed, the algorithm finds a minimum vertex cover
of size k = 420.

[1]  R.M. Karp, Reducibility among combinatorial problems, Complexity of Computer Computations, Plenum Press, 1972. 
[2]  R. Frucht, Graphs of degree three with a given abstract group, Canad. J. Math., 1949. 
[3]  Stephen Cook, The P versus NP Problem, Official Problem Description, Millennium Problems, Clay Mathematics Institute, 2000. 
[4]  J.A. Bondy and U.S.R. Murty, Graph Theory with Applications, Elsevier Science Publishing Co., Inc, 1976. 
[5]  Euclid, Elements, circa 300 B.C. 
[6]  F.P. Ramsey, On a problem of formal logic, Proc. London Math. Soc., 1930. 
[7]  Stanley Lippman, Essential C++, AddisonWesley, 2000. 
[8]  Plato, Timaeaus, circa 350 B.C. 
[9]  K. Kuratowski, Sur le problème des courbes gauches en topologie, Fund. Math., 1930. 
[10]  J. Petersen, Die Theorie der regulären Graphen, Acta Math., 1891. 
[11]  H. Grötzsch, Ein Dreifarbensatz für dreikreisfreie Netz auf der Kugel, Z. MartinLutherUniv., 1958. 
[12]  A.S. Herschel, Sir Wm. Hamilton's Icosian Game, Quart. J. Pure Applied Math., 1862. 
[13]  J. Folkman, Regular linesymmetric graphs, J. Combinatorial Theory, 1967. 
[14]  H.S.M. Coxeter and W.T. Tutte, The Chords of the NonRuled Quadratic in PG(3,3), Canad. J. Math., 1958. 
[15]  C. Thomassen, Hypohamiltonian and hypotraceable graphs, Discrete Math., 1974. 
[16]  C. Berge, Graphes et Hypergraphes, Dunod, 1970. 
[17]  Klaus D. Witzel, Personal Communication, 2006. 
[18]  Ashay Dharwadker, The Independent Set Algorithm, http://www.dharwadker.org/independent_set , 2006. 
[19]  Ashay Dharwadker, The Clique Algorithm, http://www.dharwadker.org/clique , 2006. 
[20]  Ashay Dharwadker, The Vertex Coloring Algorithm, http://www.dharwadker.org/vertex_coloring , 2006. 
[21]  Eric Filiol, Edouard Franc, Alessandro Gubbioli, Benoit Moquet and Guillaume Roblot, Combinatorial Optimisation of Worm Propagation on an Unknown Network, Proc. World Acad. Science, Engineering and Technology, Vol 23, August 2007. 
Copyright © 2006 by Ashay Dharwadker. All rights reserved. 