15

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.

Sumit Trehan
  • 3,985
  • 3
  • 27
  • 42
starcaller
  • 979
  • 3
  • 16
  • 25
  • I didn't get your question, max independent set means what ? Do you want node having max value or what ? because the approach you described will have 2^n leaf nodes in binary tree. so, from where to start ,give brief description about the implementation of tree is it binary tree? – Omkant Nov 24 '12 at 18:44
  • 1
    So finding the maximal independent set (http://en.wikipedia.org/wiki/Maximal_independent_set) given a general tree of n nodes. – fgb Nov 24 '12 at 18:52
  • just consider a full binary tree for the sake of simplicity. – starcaller Nov 24 '12 at 18:54
  • 1
    Do you want a **maximum** independent set (one of the greatest possible size) or a **maximal** independent set (one to which no more vertices can be added)? Maximum independent sets are obviously maximal but it's easier to find maximal independent sets that aren't necessarily maximum (all trees are bipartite so just take one side of the bipartition). – David Richerby Sep 30 '14 at 00:24

3 Answers3

21

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?

Peter de Rivaz
  • 33,126
  • 4
  • 46
  • 75
  • I don't think the min dominating set is equal to the maximal/maximum independent set. A star is a tree, and there they are obviously not equal, or am I missing sth? Shouldn't the min dominating set be the complement of the maximum independent set? – yassin Mar 03 '17 at 10:17
  • What if there is a negative weight associates with each node? Is the solution above still correct? – Loc Huynh Oct 26 '17 at 20:21
2

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.

Wrdlbrmpfd
  • 21
  • 2
-2

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

Sumit Trehan
  • 3,985
  • 3
  • 27
  • 42
  • This is incorrect. It finds a **maximal** independent set (one to which no vertices can be added) but not a **maximum** independent set (one of the largest possible cardinality). Consider the tree formed by taking an edge xy and adding two leaves adjacent to x and two adjacent to y. The maximum independent set is all the leaves: four vertices. But each side of the graph contains only three vertices. – David Richerby Sep 30 '14 at 00:07
  • Couldn't you compute the maximum 2 ways then: 1) max of BLACK or WHITE list 2) perform BLACK and WHITE coloring but every time you reach a leaf node add it to the leaf node's maximum independent set The largest list returned from (1) or (2) is the final answer. – Alex Spencer Nov 02 '14 at 00:37