Lesson 3

We will solve the independent set problem for a non-rooted tree, even though a rooted tree is given in the problem statement. Our approach will be as follows: we will immediately take an arbitrary leaf (a vertex of degree one) into the independent set, then remove it and its parent from the tree, and continue recursively. This is an example of a greedy algorithm. Why does it always lead to an optimal solution? Consider some leaf and its parent. In the maximum independent set, at least one of them must be included: if neither were included, we could add the leaf. And if the parent is included, it can always be replaced with the leaf.

There is one subtlety in this approach. When removing the parent of a leaf from the tree, the tree may become disconnected. However, this does not cause any issues: it is clear that to find the maximum independent set in a forest of trees, it is sufficient to find the maximum independent set in each tree separately. Therefore, we will continue finding leaves while there are edges in the forest. When no edges remain, we simply add all remaining vertices to the independent set.

from networkx import number_of_edges, nx_agraph, random_tree

tree = random_tree(n=13, seed=18)
nx_agraph.to_agraph(tree).draw('ind_set_tree.png', prog='fdp')

max_ind_set = []
while number_of_edges(tree):
    leaf = [v for v in tree.nodes() if tree.degree[v] == 1][0]
    max_ind_set.append(leaf)
    neighbor = list(tree.neighbors(leaf))[0]
    tree.remove_node(leaf)
    tree.remove_node(neighbor)
max_ind_set += list(tree.nodes())
print(max_ind_set)

[0, 4, 6, 8, 3, 10, 12]