3
$\begingroup$

I was attempting to solve "Maximum Independent Set of a Tree" and came up with an algorithm that resembled this one Why is greedy algorithm not finding maximum independent set of a graph?

Code extract shown here:

Greedy(G):
S = {}
While G is not empty:
    Let v be a node with minimum degree in G
    S = union(S, {v})
    remove v and its neighbors from G
return S

Would this algorithm work for trees? Why or why not?

$\endgroup$

1 Answer 1

2
$\begingroup$

Yes, it would work for trees (acyclic graphs in general).

You need to prove one thing. Let $\ell$ be a leaf in a tree. Then there exists a maximum independent set that contains $\ell$.

The proof sketch is as follows. Let $S^*$ be a maximum independent set and assume that $\ell \notin S^*$. Since it is maximum, the unique neighbor $v$ of $\ell$ is in $S^*$. Since $v$ is $\ell$'s only neighbor, we can create a new independent set $S = S^* \setminus \{v\} \cup \{\ell\}$ with the same size.

This proves that your code is correct. (Strictly speaking you also have to argue that you can put isolated vertices in $S$, but that's fine.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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