2
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ Why do you think this algorithm works? $\endgroup$ – Yuval Filmus Sep 29 '14 at 23:23
5
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.