![](https://csdnimg.cn/release/download_crawler_static/10519536/bg12.jpg)
1.3 A Branching Algorithm for Independent Set 7
1.3 A Branching Algorithm for Independent Set
A fundamental and powerful technique to design fast exponential time algorithms
is Branch & Reduce. It actually comes with many different names: branching al-
gorithm, search tree algorithm, backtracking algorithm, Davis-Putnam type algo-
rithm etc. We shall introduce some of the underlying ideas of the Branch & Reduce
paradigm by means of a simple example.
Maximum Independent Set. In the MAXIMUM INDEPENDENT SET problem (MIS),
we are given an undirected graph G = (V,E). The task is to find an independent
set I ⊆V , i.e. any pair of vertices of I is non-adjacent, of maximum cardinality. For
readers unfamiliar with terms from Graph Theory, we provide the most fundamental
graph notions in Appendix .
A trivial algorithm for this problem would be to try all possible vertex subsets
of G, and for each subset to check (which can be easily done in polynomial time),
whether this subset is an independent set. At the end this algorithm outputs the size
of the maximum independent set or a maximum independent set found. Since the
number of vertex subsets in a graph on n vertices is 2
n
, the naive approach here
requires time Ω (2
n
).
Here we present a simple branching algorithm for MIS to introduce some of the
major ideas. The algorithm is based on the following observations. If a vertex v is
in an independent set I, then none of its neighbors can be in I. On the other hand,
if I is a maximum (and thus maximal) independent set, and thus if v is not in I then
at least one of its neighbors is in I. This is because otherwise I ∪{v} would be an
independent set, which contradicts the maximality of I. Thus for every vertex v and
every maximal independent set I, there is a vertex y from the closed neighborhood
N[v] of v, which is the set consisting of v and vertices adjacent to v, such that y is
in I, and no other vertex from N[y] is in I. Therefore to solve the problem on G,
we solve problems on different reduced instances, and then pick up the best of the
obtained solutions. We will refer to this process as branching.
The algorithm in Fig.
1.2 exploits this idea. We pick a vertex of minimum degree
and for each vertex from its closed neighborhood we consider a subproblem, where
we assume that this vertex belongs to a maximum independent set.
Algorithm mis1(G).
Input: Graph G = (V,E).
Output: The maximum cardinality of an independent set of G.
if |V | = 0 then
return 0
choose a vertex v of minimum degree in G
return 1 + max{mis1(G \N[y]) : y ∈ N[v]}
Fig. 1.2 Algorithm mis1 for MAXIMUM INDEPENDENT SET