# Is it possible to solve maximum weight independent set in linear time for a cycle?

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})$.

• You can solve this using dynamic programming. Work out the slightly easier case of a path first. Aug 14, 2018 at 4:46
• More generally, you can find a maximum weight independent set in graphs of bounded treewidth. See for example wwwmayr.in.tum.de/konferenzen/Jass03/presentations/krause.pdf. Aug 14, 2018 at 5:36
• I don't understand your brute force approach. A cycle can have more than three vertices, and given any three consecutive vertices in a cycle of length four or more, the max-weight IS might contain two of them. Aug 14, 2018 at 10:46

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$.