International Journal of Computer science engineering Techniques– Volume 2 Issue 5, July  Aug 20!
ISSN: 2455135X http://www.ijcsejournal.org
Page 7
A Heuristic Approach for the Independent Set Problem
Omar Kettani*,
*(Scientific Institute, Physics of the Earth Laboratory/Mohamed V University, Rabat)
INTRODUCTION
In graph theory, the stable set (or maximum independent set) of a graph is a maximum cardinality subset of vertices in which no two vertices are adjacent. This problem which has many applications in computer science and operations research is computationally intractable in general [5] but can be solved in polynomial time on some special graph classes, like bipartite graphs [8], chairfree graphs [3] or clawfree graphs [7] [11]. Therefore, for large and hard instances one must design heuristic approaches to obtain near optimal solutions within reasonable time. Given an undirected graph G = (V, E) with vertex set V = V (G) of cardinality V (G) = n, and edge set E = E(G) of cardinality E(G) = m. The neighborhood of a vertex v
∈
V is the set N(v) = {u
∈ ∈
V: vu E} . A set S
⊆
V (G) is independent if no two vertices from S are adjacent; by Ind(G) we mean the set of all the independent sets of G. An independent set of maximum size will be referred to a maximum stable set of G. A vertex cover is a subset Vc
⊆
V , such that every edge in G has at least one endpoint in Vc. The rest of this paper is organized as follows: In section 2 we describe the proposed approach, whereas section 3 provides some examples of the application of the proposed heuristic on some famous graphs taken from the literature. Finally, concluding remarks are given in section 4.
P
ROPOSED APPROACH
The main idea of the proposed heuristic is to build a maximal stable set I
by considering incrementally a minimal vertex cover Vc.
Abstract:
Given a graph G =(V, E), the independent set problem is to find a maximum cardinality subset S of V such that all vertices in S are pairwise nonadjacent. This problem is NPhard in general but can be solved in polynomial time on some special graph classes, like bipartite graphs, chairfree graphs or clawfree graphs. In this article, we propose a heuristic algorithm for this problem. The results of its application on some famous graphs taken from the literature, with known optimal solutions demonstrates that this approach is effective.
RESEARCH ARTICLE OPEN ACCESS
International Journal of Computer science engineering Techniques– Volume 2 Issue 5, July  Aug 20!
ISSN: 2455135X http://www.ijcsejournal.org
Page 8
The pseudocode of the proposed heuristic algorithm is given below. Input: G(V, E) Output: A stable set I of G. J
←
[1,n] I
←
[]
for i=1:n J1
←
{j
∈
J/ a(j,1)=i} J2
←
{j
∈
J/ a(j,2)=i} c
←{
a(J1,1)
}
∪{
a(J1,2)
}
v(i)
←
c L(i)
←
c

end for i1
←
ArgMin(L(i)) i
∈
J Vc
←
v(i1) I(1)
←{
i1
} Κ ←
J(I
∪
Vc) while K
≠∅
do w
←
[] L
←
[] for i=1:n w(i)
←
v(i)
∪
Vc
if i
∈
K L(i)
←
w
(i)

else
L(i)
←
n+
1
end end for i1
←
ArgMin(L(i)) i
∈
J I
←Ι ∪ {
i1
}
Vc
←
w(
i1)
Κ ←
J(I
∪
Vc) end while output I
3.
Some examples
In the following examples, we demonstrates the application of the proposed heuristic on some instance of famous graphs defined by their adjacency matrix. We report, the outputs of the heuristic as a list of the maximal stable sets S
v
that contain vertex v (v=1,...,n), the independence number
α
of G and the stable set S of G. (The vertices of S=I are colored in white in the following figures)
fig.1 The graph of the Cube
α
=4 S={ 1 , 3 , 5 , 7 }
fig.2 the Icosahedron graph [10]
α
=3 S= { 1 , 4 , 11 } Fig. 1 A sample line graph using colors which contrast well both on screen and on a blackandwhite hardcopy
International Journal of Computer science engineering Techniques– Volume 2 Issue 5, July  Aug 20!
ISSN: 2455135X http://www.ijcsejournal.org
Page 9
fig.3 The graph K3,3 [6]
α
=3 S= { 1 , 2 , 3 } fig.4 The Dodecahedron graph [10]
α
=8 S={ 1 , 3 , 6 , 8 , 11 , 13 , 16 , 18 } fig.5 The Folkman graph [4]
α
=10 S= { 1 , 10 , 2 , 9 , 3 , 8 , 4 , 5 , 6 , 7 }
fig.6 The Petersen graph [9]
α
=4 S={ 1 , 3 , 6 , 10 } fig.7 The Thomassen graph [12]
α
=14 S= { 1 , 2 , 15 , 8 , 13 , 9 , 17 , 19 , 29 , 25 , 21 , 32 , 24 , 33 } fig.9 The BondyMurty graph G4 [2]
α
=9 S={ 1 , 3 , 4 , 5 , 12 , 14 , 16 , 9 , 2 }
International Journal of Computer science engineering Techniques– Volume 2 Issue 5, July  Aug 20!
ISSN: 2455135X http://www.ijcsejournal.org
Page 10
f
ig.8 The BondyMurty graph G1 [2]
α
=3 S={ 4 , 5 , 6 } fig.9 The BondyMurty graph G2 [2]
α
=4 S={3 , 5 , 8,10 }
fig.10:The BondyMurty graph G3 [2]
α
=7 S={ 1,3 ,7 ,13 ,5 , 9 ,11 }
fig.11:The Grötzsch graph [15]
α
=5 S={ 2, 3 , 4 , 5 , 6} fig.12:The Herschel graph [16]
α
=6 S={2 , 4 , 9, 5 , 7 , 11}
fig.13:The TutteCoxeter graph [17]