Maximal independent set algorithm

Maximal independent set problem

You have a set of radio stations all having the same transmission frequency. Signals from adjacent stations interfere with each other which causes data loss. We need to choose the largest set of stations that can operate at the same time without data loss. Assume the list of stations is represented using a tree structure where nodes are stations and an edge between two nodes means they are neighbors and can not transmit at the same time. In other words two stations can transmit at the same time only if there is no connecting edge between them. Describe an algorithm to choose such a group of stations.

Maximal independent set greedy algorithm

This is a well known graph problem called Maximal Independent Set. It is an NP-Hard problem which means there is no known efficient solution for it. A greedy approach to choose a maximal set of independent stations works by choosing a leaf node in the tree because a leaf node has a maximum of one neighbor. Basically you remove the node from the tree and add it to the solution then delete its neighbor from the tree. You repeat the same procedure on the remaining tree until there is no nodes to choose. For general graphs we need to choose a node with the fewest number of neighbors but in the case of a tree a leaf node guarantees the least number of neighbors. Note that we can apply the exchange property for problems that can be solved in a greedy method. The exchange property states that given a solution for the problem at hand, can we improve the solution by adding or removing elements to or from the given solution. In our case if you choose a none leaf node like a parent node as part of the solution then you can exchange that parent node with all of its neighbors which in terns expands the solution and make it better.