Maximum Weight Independent Set Problem: Difference between revisions

From NovaOrdis Knowledge Base
Jump to navigation Jump to search
 
(17 intermediate revisions by the same user not shown)
Line 5: Line 5:


=Internal=
=Internal=
* [[Algorithms#Dynamic_Programming_Algorithms|Dynamic Programming Algorithms]]
* [[Dynamic_Programming#Canonical_Use|Dynamic Programming]]
 
=Overview=
=Overview=
This article introduces the maximum weight [[Graph_Concepts#Independent_Set|independent set]] of a [[Graph_Concepts#Path_Graph|path graph]] and provides a dynamic programming algorithm to solve it.
This article introduces the maximum weight [[Graph_Concepts#Independent_Set|independent set]] of a [[Graph_Concepts#Path_Graph|path graph]] and provides a dynamic programming algorithm to solve it.
Line 12: Line 13:
Given a [[Graph_Concepts#Path_Graph|path graph]] G=(V, E) where V consists in a set of n vertices v<sub>0</sub>, v<sub>1</sub> ... v<sub>n-1</sub> that form a path, each of vertices with its own positive weight w<sub>i</sub>, compute a maximum weight [[Graph_Concepts#Independent_Set|independent set]] of the graph. An independent set is a set of vertices in which none is [[Graph_Concepts#Vertex_Adjacency|adjacent]] to the other.
Given a [[Graph_Concepts#Path_Graph|path graph]] G=(V, E) where V consists in a set of n vertices v<sub>0</sub>, v<sub>1</sub> ... v<sub>n-1</sub> that form a path, each of vertices with its own positive weight w<sub>i</sub>, compute a maximum weight [[Graph_Concepts#Independent_Set|independent set]] of the graph. An independent set is a set of vertices in which none is [[Graph_Concepts#Vertex_Adjacency|adjacent]] to the other.
=A Dynamic Programming Approach=
=A Dynamic Programming Approach=
The key to finding a [[Algorithms#Dynamic_Programming_Algorithms|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:
The key to finding a [[Algorithms#Dynamic_Programming_Algorithms|dynamic programming algorithm]] is to identify a small set of subproblems whose solution can be computed using the previous subproblems' solutions.  


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>.
In this case, we start with the observation that for the full n vertex path graph G {v<sub>1</sub>, .... v<sub>n</sub>}, we have two situations:


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>.
1. v<sub>n</sub> belongs to the solution. In this case, v<sub>n-1</sub> does not belong to the solution, by the properties of an independent set. The maximum weight of the independent set for the graph G is W = w<sub>n</sub> + W<sup>&#39;'</sup>, where W<sup>&#39;'</sup> is the maximum weight independent set for the n-2 vertices path graph {v<sub>1</sub>, .... v<sub>n-2</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.  
2. v<sub>n</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>1</sub>, .... v<sub>n-1</sub>}, annotated as W<sup>'</sup>.
 
There is no other possibility, so if we compute recursively W<sup>'</sup> and W<sup>&#39;'</sup> we can decide, after the computation is completed, 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.
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.
=Dynamic Programming Algorithm=
The actual solution involves computing the maximum weights W of the independent set starting with the vertex v<sub>1</sub> and storing the intermediate solutions in the array W:
<font size=-1>
initialize an n+1 element W array
W[0] = 0
W[1] = w<sub>1</sub>
for i = 2 to n:
  W[i] = max(W[i-1], w[i] + W[i-2])
</font>
After computing the subgraph weights and the maximum weight in W[n], the array containing the maximum weight for subgraphs can be walked back to display the actual vertices that are part of the independent set. <font color=darkkhaki>TODO: provide pseudocode algorithm, working solution in playground.</font>
==Playground Implementation==
{{External|https://github.com/ovidiuf/playground/blob/master/learning/stanford-algorithms-specialization/13-dynamic-programming-max-weight-independent-set/src/main/java/playground/stanford/mwis/Main.java}}

Latest revision as of 21:53, 11 November 2021

External

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 G {v1, .... vn}, we have two situations:

1. vn belongs to the solution. In this case, vn-1 does not belong to the solution, by the properties of an independent set. The maximum weight of the independent set for the graph G is W = wn + W'', where W'' is the maximum weight independent set for the n-2 vertices path graph {v1, .... vn-2}.

2. vn does not belong to the solution, and in this case the solution consists in the maximum weight independent set of the graph {v1, .... vn-1}, annotated as W'.

There is no other possibility, so if we compute recursively W' and W'' we can decide, after the computation is completed, 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.

Dynamic Programming Algorithm

The actual solution involves computing the maximum weights W of the independent set starting with the vertex v1 and storing the intermediate solutions in the array W:

initialize an n+1 element W array
W[0] = 0
W[1] = w1
for i = 2 to n:
  W[i] = max(W[i-1], w[i] + W[i-2])

After computing the subgraph weights and the maximum weight in W[n], the array containing the maximum weight for subgraphs can be walked back to display the actual vertices that are part of the independent set. TODO: provide pseudocode algorithm, working solution in playground.

Playground Implementation

https://github.com/ovidiuf/playground/blob/master/learning/stanford-algorithms-specialization/13-dynamic-programming-max-weight-independent-set/src/main/java/playground/stanford/mwis/Main.java