CODEWITHSUNDEEP
algorithmtreeindependent-set
starcaller
starcaller

Reputation: 979

algorithm to find max independent set in a tree

I need an algorithm to find max independent set in a tree. I'm thinking start from all leaf nodes, and then delete the direct parent nodes to these leaf nodes, then choose the parent nodes of the parent nodes we deleted, repeat this procedure recursively until we get to root. and is this done in O(n) time? any reply is appreciated. thanks.

And could anyone please point me an algorithm to find the max dominating set in a tree.

Upvotes: 15

Views: 24983

Answers (3)

Wrdlbrmpfd
Wrdlbrmpfd

Reputation: 21

Simple and fast approach:

As long as the graph is not empty, iteratively add a leaf v (degree 1) to the independent set V and remove v and its neighbor.

This should work, since

  • A tree always has a degree-1-vertex,

  • Adding a degree-1-vertex to V preserves optimality and

  • The result of such a step again gives a tree or a forest which is a union of trees.

Upvotes: 2

Peter de Rivaz
Peter de Rivaz

Reputation: 33509

MAXIMUM INDEPENDENT SET

You can compute the maximum independent set by a depth first search through the tree.

The search will compute two values for each subtree in the graph:

  1. A(i) = The size of the maximum independent set in the subtree rooted at i with the constraint that node i must be included in the set.
  2. B(i) = The size of the maximum independent set in the subtree rooted at i with the restriction that node i must NOT be included in the set.

These can be computed recursively by considering two cases:

  1. The root of the subtree is not included.

    B(i) = sum(max(A(j),B(j)) for j in children(i))

  2. The root of the subtree is included.

    A(i) = 1 + sum(B(j) for j in children(i))

The size of the maximum independent set in the whole tree is max(A(root),B(root)).

MAXIMAL DOMINATING SET

According to the definition of dominating set in wikipedia the maximum dominating set is always trivially equal to including every node in the graph - but this is probably not what you mean?

Upvotes: 21

Sumit Trehan
Sumit Trehan

Reputation: 4035

  • To find the maximal independent set of vertices, we can use an important property of a tree: Every tree is Bipartite i.e. We can color the vertices of a tree using just two colors such that no two adjacent vertices have the same color.

  • Do a DFS traversal and start coloring the vertices with BLACK and WHITE.

  • Pick the set of vertices (either BLACK or WHITE) which are more in number. This will give you the maximal independent set of vertices for a tree.

Some Intuition behind the why this algorithm works:

  • Let us first revisit the definition of the maximal independent set of vertices. We have to pick just one end point of an edge and we have to cover every edge of the tree satisfying this property. We are not allowed to choose both end points of an edge.

  • Now what does bicoloring of a graph do? It simply divides the set of vertices into two subsets (WHITE and BLACK) and WHITE colored vertices are directly connected to BLACK ones. Thus if we choose either all WHITE or all BLACK ones we are inherently choosing an independent set of vertices. Thus to choose maximal independent set, go for the subset whose size is larger.

Upvotes: -2

Related Questions