The Independent Set AlgorithmAshay DharwadkerH501 Palam Vihar District Gurgaon Haryana 122017 India 


We present a new polynomialtime
algorithm for finding maximal independent sets in graphs. It is shown that
every graph with n vertices and maximum vertex degree Δ
must have a maximum independent set of size at least ⌈n/(Δ+1)⌉
and that this condition is the best possible in terms of n and Δ.
As a corollary, we obtain new bounds on the famous Ramsey numbers in terms
of the maximum and minimum vertex degrees of the corresponding Ramsey graphs.
The algorithm finds a maximum independent set 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 maximum
independent set. The algorithm is demonstrated by finding maximum independent
sets for several famous graphs, including two large benchmark graphs with
hidden maximum independent sets. 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 maximum independent set in the hardest
known cases. We are pleased to announce that
The Independent Set 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 maximum independent set in a graph. Given
a graph, one must find a largest set of vertices such that no two vertices
in the set are connected by an edge. Such a set of vertices is called a
maximum independent set of the graph and in general can be very difficult
to find. For example, try to find a maximum independent set with five vertices
in the Frucht graph
[2] shown below in Figure 1.1.
We present a new polynomialtime INDEPENDENT SET ALGORITHM for finding maximal independent sets 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 maximum independent set of a certain size. We prove that every graph with n vertices and maximum vertex degree Δ must have a maximum independent set of size at least ⌈n/(Δ+1)⌉ and that the algorithm will always find an independent set of at least 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 maximum independent set is exactly ⌈n/(Δ+1)⌉. As a corollary, we obtain new bounds on the famous Ramsey numbers in terms of the maximum and minimum vertex degrees of the corresponding Ramsey graphs. For all known examples of graphs, the algorithm finds a maximum independent set. 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 maximum independent set? 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 maximum independent sets for several EXAMPLES of famous graphs, including two large benchmark graphs with hidden maximum independent sets. 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. 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. An independent set S of G is a set of vertices such that no unordered pair of vertices in S is an edge. Given an independent set S of G and a vertex v outside S, we say that v is adjoinable if the set S∪{v} is still an independent set of G. Denote by ρ(S) the number of adjoinable vertices of an independent set S of G. A maximal independent set has no adjoinable vertices. A maximum independent set is an independent set with the largest number of vertices. Note that a maximum independent set is always maximal 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 maximum independent set is known to be NPcomplete [1]. Thus, if we are able to show the existence of a polynomialtime algorithm that finds a maximum independent set 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 an independent set S of G, if S has no adjoinable vertices, output S. Else, for each adjoinable vertex v of S, find the number ρ(S∪{v}) of adjoinable vertices of the independent set S∪{v}. Let v_{max} denote an adjoinable vertex such that ρ(S∪{v_{max}}) is a maximum and obtain the independent set S∪{v_{max}}. Repeat until the independent set has no adjoinable vertices. 3.2. Procedure. Given a simple graph G with n vertices and a maximal independent set S of G, if there is no vertex v outside S such that v has exactly one neighbor w inside S, output S. Else, find a vertex v outside S such that v has exactly one neighbor w inside S. Define S^{v}^{,w} by adjoining v to S and removing w from S. Perform procedure 3.1 on S^{v}^{,w} and output the resulting independent set. 3.3. Algorithm. Given as input a simple graph G with n vertices labeled 1, 2, …, n, search for an independent set of size at least k. At each stage, if the independent set obtained has size at least k, then stop.
V = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10,11, 12}.
We search for an independent set of size at least k = 5. Part I for i = 1 and i = 2 yields independent sets S_{1} and S_{2} of size 4, so we give the details starting from i = 3. We initialize the independent set as S_{3 }= {i} = {3}. We now perform procedure 3.1. Here are the results in tabular form:
We obtain a maximal independent set S_{3 }= {3, 5, 7, 11, 12} of the requested size k = 5 and the algorithm terminates. 
The algorithm may be applied to any simple
graph and will always terminate in polynomialtime, finding many maximal
independent sets. The propositions below establish sufficient conditions
on the input graph which guarantee that the algorithm will find maximal
independent sets of a certain size. Specifically, we prove that every graph
with
n vertices and maximum vertex degree Δ
must have a maximum independent set of size at least ⌈n/(Δ+1)⌉
and that the algorithm will always find an independent set of at least
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 maximum independent set is exactly
⌈n/(Δ+1)⌉.
As a corollary, we obtain new bounds on the famous Ramsey numbers in terms
of the maximum and minimum vertex degrees of the corresponding Ramsey graphs.
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 independent set S. At each stage of procedure 3.1, if there are l vertices outside S and the maximum degree among the vertices inside S is less than ⌈l/(n−l)⌉, then procedure 3.1 produces a strictly larger independent set. Proof. By contradiction. Suppose the independent set S is maximal. Then there are no adjoinable vertices and every vertex outside S must have a neighbor inside S. Thus there are at least l edges (letters) with one end vertex outside S and the other end vertex inside S, there being exactly p = n−l vertices inside S (pigeonholes). By the pigeonhole principle, some vertex inside S must receive at least ⌈l/p⌉ edges contradicting the hypothesis that the maximum degree among the vertices inside S is less than ⌈l/p⌉. ☐ 5.2. Proposition. Given an independent set S of G, procedure 3.1 always produces a maximal independent set of G. Proof. Procedure 3.1 terminates only when there are no adjoinable vertices. By definition, the resulting independent set must be maximal. ☐ 5.3. Proposition. Given a simple graph G with n vertices and an initial maximal independent set S. If there are m vertices outside the maximal independent set S and the maximum degree among the vertices inside S is less than ⌈2m/(n−m)⌉, then there exists a vertex v outside S such that v has exactly one neighbor w inside S and procedure 3.2 produces a maximal independent set different from S and of size greater than or equal to the size of S. Proof. By contradiction. Note that since S is maximal, there are no adjoinable vertices and every vertex outside S has at least one neighbor inside S. Suppose every vertex outside S has more than one neighbor inside S. Then there are at least l = 2m edges (letters) with one end vertex outside S and the other end vertex inside S, there being exactly p = n−m vertices inside S (pigeonholes). By the pigeonhole principle, some vertex inside S must receive at least ⌈l/p⌉ edges contradicting the hypothesis that the maximum degree among the vertices inside S is less than ⌈l/p⌉. Thus, there exists a vertex v outside S such that v has exactly one neighbor w inside S. Now since procedure 3.2 exchanges v and w, an independent set different from S but of the same size as S is created. Note that in the process some vertices outside the independent set might have become adjoinable. Then, procedure 3.2 applies procedure 3.1 that produces a maximal independent set different from S and of size greater than or equal to the size of S. ☐ 5.4. Proposition. Given a simple graph G with n vertices and maximum vertex degree Δ, the algorithm always finds a maximal independent set of size at least ⌈n/(Δ+1)⌉. Proof. Consider any one turn of part I in the algorithm. After t vertices have been adjoined from a total of n, there are l = n−t vertices outside the independent set S and the maximum degree among the vertices inside S 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 larger independent set is produced by adjoining a vertex. Hence, as long as t is less than ⌈n/(Δ+1)⌉, a vertex can still be adjoined and procedure 1 continues. Thus, at least ⌈n/(Δ+1)⌉ vertices are adjoined, producing an independent set of size at least ⌈n/(Δ+1)⌉. By propositions 5.1, 5.2 and 5.3, all of the independent sets produced by the algorithm are maximal and of size at least ⌈n/(Δ+1)⌉. ☐ 5.5. Proposition. A simple graph G with n vertices and maximum vertex degree Δ has a maximal independent set of size at least ⌈n/(Δ+1)⌉. Proof. By proposition 5.4, the algorithm finds a maximal independent set of size at least ⌈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 maximum independent set of size ⌈n/(Δ+1)⌉. For any such graph the algorithm always finds a maximum independent set. Proof. Let n = q(Δ+1)+r with 0 ≤ r < Δ+1 by Euclid's division lemma. There are two cases.
5.7. Corollary. A Ramsey graph R(k, l) with minimum vertex degree δ, maximum vertex degree Δ and n = r(k, l)−1 vertices must satisfy ⌈kδ/(k−1)⌉ < n < l(Δ+1). Proof. By definition, the graph G = R(k,
l)
has no clique of size k and no independent set of size
l.
5.8. Question. For all known examples of graphs, the algorithm finds a maximum independent set. 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 maximum independent set? 
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 maximum independent sets. In each case, the algorithm finds a maximum
independent set 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 maximum independent set of size k = 1.
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 maximum independent set
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 maximum independent set of size k = 2.
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 maximum independent set of size k
= 3.
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 maximum independent set of size k
= 3.
7.6. The Cube [8]. We run the program on the
graph of the Cube with
n = 8 vertices. The algorithm finds a maximum
independent set 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 maximum independent set of size k = 4.
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 maximum independent set of size k
= 4.
7.9. The Grötzsch Graph [11]. We run the
program on the Grötzsch graph with
n = 11 vertices. The algorithm
finds a maximum independent set of size
k = 5.
7.10. The Herschel Graph [12]. We run the program
on the Herschel graph with
n = 11 vertices. The algorithm finds
a maximum independent set of size
k = 6.
7.11. The Icosahedron [8]. We run the program
on the graph of the Icosahedron with n = 12 vertices. The algorithm
finds a maximum independent set of size k = 3.
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 maximum independent set 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 maximum independent set of size k
= 9.
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 maximum independent set of size k = 3.
7.15. The Folkman Graph [13]. We run the program
on the Folkman graph with n = 20 vertices. The algorithm finds a
maximum independent set 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 maximum independent set of size k = 8.
7.17. The TutteCoxeter Graph [14]. We run the
program on the TutteCoxeter graph with n = 30 vertices. The algorithm
finds a maximum independent set 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 maximum independent set of size
k = 14.
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 an independent
set with at least twenty vertices. Indeed, the algorithm finds a maximum
independent set of size k = 20.
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 maximum independent set with at least 30 vertices (one vertex
from each original clique). Moreover, the maximum independent set is well
and truly hidden. Indeed, the algorithm finds a maximum independent set
of size k = 30.

[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 Vertex Cover Algorithm, http://www.dharwadker.org/vertex_cover , 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. 
Copyright © 2006 by Ashay Dharwadker. All rights reserved. 