Maximum Weight Independent Set Problem: Difference between revisions
| Line 15: | Line 15: | ||
1. v<sub>n-1</sub> belongs to the solution. In this case, v<sub>n-2</sub> does not belong to the solution, by the properties of an independent set, and the maximum weight of the independent set for the graph G<sub>n</sub> is W<sub>n</sub> = w<sub>n-1</sub> + W<sub>n-2</sub>, where W<sub>n-2</sub> is the maximum weight independent set for the path graph v<sub>0</sub>, .... v<sub>n-3</sub>. | 1. v<sub>n-1</sub> belongs to the solution. In this case, v<sub>n-2</sub> does not belong to the solution, by the properties of an independent set, and the maximum weight of the independent set for the graph G<sub>n</sub> is W<sub>n</sub> = w<sub>n-1</sub> + W<sub>n-2</sub>, where W<sub>n-2</sub> is the maximum weight independent set for the path graph v<sub>0</sub>, .... v<sub>n-3</sub>. | ||
2. v<sub>n-1</sub does not belong to the solution, and in this case the solution consists in the maximum weight independent set of the graph v<sub>0</sub>, .... v<sub>n-2</sub>, which is W<sub>n-1</sub>. | |||
There is no other possibility, so if we compute recursively W<sub>n-2</sub> and W<sub>n-1</sub> we can decide at this which one is larger. | |||
This idea might suggest a recursive solution of the algorithm, but solution is inefficient, the running time is exponential. The inefficiency of the solution comes from the fact that both recurrences compute redundantly almost the same thing. | |||
Revision as of 21:49, 27 October 2021
External
- https://www.coursera.org/learn/algorithms-greedy/lecture/t9XAF/wis-in-path-graphs-optimal-substructure
- https://www.coursera.org/learn/algorithms-greedy/lecture/w040v/wis-in-path-graphs-a-linear-time-algorithm
- https://www.coursera.org/learn/algorithms-greedy/lecture/TZgJM/wis-in-path-graphs-a-reconstruction-algorithm
Internal
Overview
This article introduces the maximum weight independent set of a path graph and provides a dynamic programming algorithm to solve it.
The Maximum Weight Independent Set Problem
Given a path graph G=(V, E) where V consists in a set of n vertices v0, v1 ... vn-1 that form a path, each of vertices with its own positive weight wi, compute a maximum weight independent set of the graph. An independent set is a set of vertices in which none is adjacent to the other.
A Dynamic Programming Approach
The key to finding a dynamic programming algorithm is to identify a small set of subproblems whose solution can be computed using the previous subproblems' solutions. In this case, we start with the observation that for the full n vertex path graph, we have two situation:
1. vn-1 belongs to the solution. In this case, vn-2 does not belong to the solution, by the properties of an independent set, and the maximum weight of the independent set for the graph Gn is Wn = wn-1 + Wn-2, where Wn-2 is the maximum weight independent set for the path graph v0, .... vn-3.
2. vn-1</sub does not belong to the solution, and in this case the solution consists in the maximum weight independent set of the graph v0, .... vn-2, which is Wn-1.
There is no other possibility, so if we compute recursively Wn-2 and Wn-1 we can decide at this which one is larger.
This idea might suggest a recursive solution of the algorithm, but solution is inefficient, the running time is exponential. The inefficiency of the solution comes from the fact that both recurrences compute redundantly almost the same thing.