CODEWITHSUNDEEP
algorithmdynamic-programminggraph-theory
Red Apple
Red Apple

Reputation: 109

Maximum-weight independent set problem for a cycle (path graph modification)

Problem: A Graph G = (V, E) with non-negative weights on vertices. Desired Output: An independent set of vertices (non-adjacent) of maximum total weight in a cycle C with n vertices v1. . . vn (for every i < n, vi is connected to vi + 1, vn is connected to v1 and these are the only edges in C).

This problem is a modification of this problem: Maximum-weight independent set problem for a path graph

I know that for the original problem with the path graph that contains no cycle, the solution is

a[i] = max(a[i - 1], a[i - 2] + w[i])

This is because the IS can be either one that contains vn or one that doesn't, and the running time is O(n) worst case because each subproblem is taking just a portion of n and reducing it since it is divide and conquer.

For the cycle modification, this is my approach:

  1. the IS contains v1 but not vn,
  2. the IS contains vn but not v1,
  3. the IS contains neither v1 nor vn.

I'm not sure if the equation is going to be the same as the path graph (shown above) for the cycle modification and not sure how to write it, and I'm not sure if the running time would still be the same as well. Please help.

Upvotes: 1

Views: 457

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65458

We don't need the cases not to overlap. If we find the max of solutions that exclude v1, and the max of solutions that exclude vn, then the overall max has to be matched by one of these two candidate solutions, since no solution includes both v1 and vn. For these subproblems, the path DP works great.

Upvotes: 1

Related Questions