2
$\begingroup$

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

$\endgroup$
3
  • 2
    $\begingroup$ You can solve this using dynamic programming. Work out the slightly easier case of a path first. $\endgroup$ Aug 14, 2018 at 4:46
  • 1
    $\begingroup$ 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. $\endgroup$ Aug 14, 2018 at 5:36
  • 1
    $\begingroup$ 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. $\endgroup$ Aug 14, 2018 at 10:46

1 Answer 1

3
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ It may be worth mentioning that this is a linear time algorithm. $\endgroup$ Aug 14, 2018 at 12:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.