Complex Networks: An Algorithmic Perspective
6.2 Maximal Independent Sets
Constructing independent sets in graphs provides us with basic structures in complex
networks that can be used for more complex operations such as clustering. Given a
graph G(V,E), an independent set can be formally deﬁned as follows.
Deﬁnition 6.1 independent set An independent set (IS) of a graph G(V,E) is a
vertex set IS ∈V such that for any vertices u ∈IS and v ∈ IS, (u, v) /∈E, that is, there
is not an edge joining two elements of the set IS.
The size of an independent set is the number of vertices it contains. Finding an
IS of minimal size is trivial as even a single node of a graph would be an IS. Our
main concern is to ﬁnd an IS of maximal order, that is, the IS cannot be enlarged
any further by the addition of any other vertices. Such an IS is called a maximal
independent set (MIS) of the graph G. The maximum independent set (MaxIS) is
the independent set with the largest size among all possible independent sets of a
given graph G and its size is shown by
(G). Here, we mean the number of vertices
by the size of the IS. Finding the maximum independent set of a graph is an NP-
hard optimization problem and deciding whether a graph has a MIS of size k is an
NP-complete problem .
We have also seen in Chapter 3 that a set is independent if and only if it is a
clique in the complement of the graph and also a set is independent if and only if
its complement is a vertex cover. The sum of
(G) and the size of minimum vertex
(G)) are the number of vertices in the graph. Figure 6.1 displays IS examples
on the same graph.
As an attempt to ﬁnd an algorithm that ﬁnds the IS of a given graph, we may
include an arbitrary vertex u in the MIS, but whenever we include this vertex, we
need to delete it along with all of its neighbors from the graph so that they cannot be
included in the MIS in the further iterations of the algorithm, as shown in Alg. 6.1.
The algorithm stops when there are no more vertices that can be selected.
Figure 6.1: Independent set examples. a) An independent set of size 2 which is also
maximal. b) A maximum independent set of size 4 in the same graph