CODEWITHSUNDEEP
algorithmgraphsetpseudocodesubset
Govind Parmar
Govind Parmar

Reputation: 21572

Is this algorithm for finding a maximum independent set in a graph correct?

We have the following input for the algorithm:

A graph G with no cycles (aka a spanning-tree) where each node has an associated weight.

I want to find an independent set S such that:

This is the high-level pseudocode I have so far: 

MaxWeightNodes(SpanningTree S):
    output = {0}
    While(length(S)):
        o = max(node in S)
        output = output (union) o
        S = S \ (o + adjacentNodes(o))
    End While
    Return output

Can someone tell me off the bat whether I've made any errors, or if this algorithm will give me the result I want?

Upvotes: 2

Views: 1864

Answers (2)

G. Bach
G. Bach

Reputation: 3909

I think the weights of the vertices make greedy solutions difficult. If all weights are equal, you can try choosing a set of levels of the tree (which obviously is easiest with a full k-ary tree, but spanning trees generally don't fall into that class). Maybe it'll be useful for greedy approximation to think about the levels as having a combined weight, since you can always choose all vertices of the same level of the tree (independent of which vertex you root it at) to go into the same independent set; there can't be an edge between two vertices of the same level. I'm not offering a solution because this seems like a difficult problem to me. The main problems seem to be the weights and the fact that you can't assume that you're dealing with full trees.

EDIT: actually, always choosing all vertices of one level seems to be a bad idea as well, as Rubens's example helps visualize; imagine the vertex on the second level on the right of his tree had a weight of 200.

Upvotes: 2

Rubens
Rubens

Reputation: 14778

The algorithm is not valid, since you'll soon face a case when excluding the adjacent nodes of an initial maximum may be the best local solution, but not the best global decision.

For example, output = []:

        10
      /    \
   100      20
   /  \    /  \
  80  90  10   30

output = [100]:

         x
      /    \
     x      20
   /  \    /  \
  x    x  10   30

output = [100, 30]:

         x
      /    \
     x      x
   /  \    /  \
  x    x  10   x

output = [100, 30, 10]:

         x
      /    \
     x      x
   /  \    /  \
  x    x  x    x

While we know there are better solutions.

This means you're down on a greedy algorithm, without an optimal substructure.

Upvotes: 5

Related Questions