Maximum Weight Independent Set Problem

From NovaOrdis Knowledge Base
Jump to navigation Jump to search

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