An independent set in a graph is a subset of vertices such that no two vertices in the subset are connected by an edge. An incomplete scheme for a greedy algorithm to find a maximum independent set in a tree is given below: V : Set of all vertices in the tree; I := phi; while V != phi do begin select a vertex u in V such that ________ ; V := V - {u}; if u is such that ________ then I := I union {u} end; Output(I); A. Complete the algorithm by specifying the property of vertex u in each case. B. What is the time complexity of the algorithm?
GATE 1994 · Discrete Mathematics · Graph Connectivity · medium
Answer: First blank: u is a leaf (degree <= 1). Second blank: no neighbour of u is already in I. Time complexity = O(n).
First blank: pick a leaf: The vertex u must be a leaf, that is a vertex of degree at most one in the current graph. A leaf has a single neighbour (its parent), so taking the leaf is never worse than taking that neighbour. Hence the first blank is 'u is a leaf (deg(u) <= 1)'.
Second blank: avoid conflicts: Add u to the independent set only when including it keeps I independent, i.e. when none of u's neighbours is already in I. Because we always grabbed leaves first, a freshly chosen leaf usually has no neighbour in I and is taken; once a leaf is in I its parent will fail this test and be skipped. So the second blank is 'no neighbour of u is in I'.
Running time: Every vertex is selected and removed exactly once. Maintaining which vertices are leaves and updating neighbour degrees can be done in O(1) amortised per removal (each edge is touched a constant number of times). With n vertices and n-1 edges in a tree, the total work is O(n).