Question

Given an undirected graph$\mathit{G}\mathbf{=}\mathbf{(}\mathbf{V}\mathbf{,}\mathbf{E}\mathbf{)}$ in which each node has$\mathit{d}\mathit{e}\mathit{g}\mathit{r}\mathit{e}\mathit{e}\mathbf{\le }\mathit{d}$ , show how to efficiently find an independent set whose size is at least$\frac{\mathbf{1}}{\mathbf{d}\mathbf{+}\mathbf{1}}$times that of the largest independent set.

Short answer

This algorithm is proved.

Step-by-step solution

Step 1:

An undirected graph in which each node has degree ≤ d, efficiently an independent set whose size is at least$\frac{1}{d+1}$ times that of the largest independent set is defined below.

Step 2:  

Let$G$ be the graph with vertex set of V having d the maximum degree, and in an empty set.

The following process will get an independent set whose size is atleast$\frac{1}{d+1}$ times that of the largest independent set.

1). Pick a vertex with smallest degree and add to it.

2). Delete vertex and all its adjacent vertices from the graph.

3). Repeat this process until the vertex set is empty.

The set is now the independent set of the graph$G$ .

Since a vertex in the graph has most d neighbours , thus at each iteration , maximum $d+1$vertices are deleted. Thus, the vertex set reduces by$d+1$ vertices at each and every iteration.

Hence there are atleast$\frac{\left|V\right|}{(d+1)}$ iteration to get the I. At each iteration, one vertex is added in the set I.

Hence, I contains atleat $\frac{\left|V\right|}{(d+1)}$vertices.

$\frac{\left|V\right|}{(d+1)}$

Let k be the size of the maximum independent as $\left|V\right|\ge K$

Therefore,

$\left|1\right|\ge$$\frac{\left|V\right|}{(d+1)}$$\ge \frac{K}{d+1}$