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?
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.
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.
eh? I can't understand how cost of root node can be doubled..
Do you add the first node as the n+1th node? Because if you do, the cost of tye first node is doubled.
please read my solution again..