winaichan263's blog

Maximum Independent Set on graph with one simple cycle
By winaichan263, history, 9 years ago, In English

Hi. I've just started working on some DP + graph problems recently, but I've gotten stuck on one. It gives you a graph with exactly one simple cycle with no other vertices (all n vertices are on the cycle) and ask you to find the total cost of the maximum independent set of the graph. I know that it is a modification of maximum independent set on trees, but I don't know how to deal with the cycle. The farthest I've gotten is adding the first node as node n+1 and the dp recurrence. Can someone help me?

  • Vote: I like it
  • +4
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
9 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Cut any arbitrary edge u — v in cycle. now the graph is a tree.

There are two cases : 1. MIS without selecting node v 2. MIS without selecting node u

Solving this is a slight modification to maximum independent set on trees.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for the comment. I'm already aware of what you said, but I'm not sure how to deal with the doubled cost of the root node.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      eh? I can't understand how cost of root node can be doubled..

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Do you add the first node as the n+1th node? Because if you do, the cost of tye first node is doubled.

        → Reply