Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
Given a cycle of $n$ vertices and each vertices of the input graph $G$ assigned a weight.
We want to find an independent set of cycle such that weight of the vertices taken in the independent set is maximum.
A brute force way is consider cycle as a set of three consecutive vertices and pick the one with max weight, but the runtime of this algorithm will be $O(2^\frac{n}{3})$.
This can be done in polynomial time by dynamic programming. Let the cycle be $x_1\dots x_\ell x_1$ and let $I$ be a maximum-weight independent set.
First, observe that either $x_1\in I$ or $x_1\notin I$. In the first case, $I$ is the union of $\{x\}$ and a maximum-weight independent set in the path $x_3\dots x_{\ell-1}$ and, in the second case, $I$ is a max-weight ind-set in the path $x_2\dots x_\ell$.
So it suffices to be able to find a max-weight ind-set in a path $y_1\dots y_k$. But we can do this by the same trick: either the set is $y_1$ plus a max-weight ind-set in $y_3\dots y_k$ or it's a max-weight ind-set in $y_2\dots y_k$.
