

Maximum Unweighted Independent Set in Tree

Question

An independent set of a graph $G = (V, E)$ is a subset $V’ ⊆ V$ of vertices such that each edge in $E$ is incident on at most one vertex in $V’$. The independent-set problem is to find a maximum-size independent set in $G$. This is a difficult NP-complete problem for general graph $G$. However, it is not difficult if $G$ is a tree. Let $T = (V, E)$ be a tree, where $V$ is the vertex set and E is the edge set. Please design an $O(n)$ algorithm to find a maximum-size independent set (MIS) in $T$, where $n = |V|$. We assume $T$ is represented by an adjacency list. You need to show the pseudo code for your algorithm.

for each vertex v in T:  
    children[v] = 0
    π(v) = nil
    isParent[v] = False
    visited[v] = False

Q = ∅       # create a queue
topological-Sort(T, u):
  visited[u] = True
  for each neighbor v of u:
            if visited[v] = False:
                children[u] += 1
                π(v) = u
                topological-Sort(T, v):
  Enqueue(Q,u)
End

unweighted-MIS(Q):
  while Q not empty:
        v ← Dequeue(Q)
        MIS = MIS U {v}
        if π(v) = nil   # we reach the root
            return MIS 
        children[π(v)] -= 1   # decrese No. of children of v's parent 
        if children[π(v)] >= 1
              isParent[π(v)] = True
        else 
               u ← Dequeue(Q)
               if π(u) != nil               # because root don't have parent
                    children[π(u)] -= 1     # to decrese No. of their children
                    if isParent[π(u)] = True and children[π(u)] = 0
                            u ← Dequeue(Q)
                            children[π(u)] -= 1
  return MIS                            
End