# Algorithm for maximum independent set in trees

While studying the dynamic programing algorithm for the maximum independent set problem in trees I thought about the following simple alternative algorithm. I tried to prove it's correctness but I do not know how to attack the proof.

The algorithm iteratively finds a two vertices $u,v$ of the tree which have maximum distance among all pairs of vertices, puts $u$ in the independent set and removes $u$ and its neighbor from the tree. This procedure is continued until no more vertices are in the tree.

Does anybody have an idea how to prove that this indeed yields a maximum independent set?

• Why do you think this algorithm works? – Yuval Filmus Sep 29 '14 at 23:23

## 1 Answer

Lemma. Every tree $T$ with at least three vertices has a maximum-cardinality independent set which includes all its leaves.

Proof. Let $I$ be a maximum-cardinality independent set containing the greatest number of leaves of $T$ of all such independent sets. Suppose that $v\notin I$ for some leaf $v$ of $T$ and let $w$ be $v$'s unique neighbour. If $w\notin I$, then $I\cup\{v\}$ is independent, contradicting the supposed maximality of $I$. Otherwise, $w\in I$ but $I' = (I\setminus\{w\}) \cup \{v\}$ is an independent set of the same cardinality as $I$. Since $T$ has at least three vertices, $w$ has degree at least two, so is not a leaf. Therefore, $I'$ contains one more leaf than $I$, again contradicting the choice of $I$. $\square$

Now we can see that the algorithm proposed in the question produces a maximum-cardinality independent set because it actually mimics a particular set of choices by the dynamic programming algorithm. Let $v$ and $w$ be vertices in the tree at maximal distance (which must, of course, be leaves). By the lemma, there is a maximum-cardinality independent set that includes both of these vertices. Therefore, we can pick either one to add to our independent set.

Note that there is a slight wrinkle in the algorithm as presented in the question. Suppose $v$ and $w$ are at maximal distance in $T$ and we decide to add $v$ to our independent set. We delete $v$ and its neighbour $v'$ from $T$. However, if $v'$ had degree at least three, we have disconnected the tree. This is OK because, by maximality of the distance from $v$ to $w$, all but one of the neighbours of $v'$ must have been leaves, so all but one of the components of $T-\{v,v'\}$ are isolated vertices. But these isolated vertices must also be added to the independent set and deleted from $T$. If they are not, then $d(v'',x)=\infty$ for any isolated vertex $v''$ and any other vertex $x$. Thus, the algorithm would be entitled to add any vertex $x$ to the independent set at the next step, which is not guaranteed to lead to a maximum-cardinality independent set (and, indeed, might disconnect the graph even more when we delete it and its neighbours).