Is it possible to solve maximum weight independent set in linear time for a cycle?
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$&nbsp;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$&nbsp;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$.