Finding the *Maximum Weighted Independent Set* for graph is an $NP$-hard
problem. Therefore, this section focuses on finding the Maximum Weight
Independent Set for the specific case of *Path Graphs*. Although not explicitly
demonstrated here, the algorithm is expandable to tree graphs with some minor
alterations. First, we review the salient graph concepts including *Independent
Sets* and *Path Graphs*.

Conceptually, an Independent Set (IS) is comparable to the inverse of a graph. It’s a set of vertices that do not contain both endpoints of any edge. Consider a connected graph with only three vertices as shown below. There are five independent sets.

The `[]`

(empty set) is always considered an IS because it technically fits the
definition. The sets `[A]`

, `[B]`

, and `[C]`

are also ISs because no edge
contains only one vertex. The set `[B, C]`

also qualifies because there are no
edges connecting `B`

and `C`

. One important thing to note is that the number of
ISs grows exponentially as the number of vertices grow. This has important
algorithmic implications.

At first glance, this concept seems a bit academic; however, ISs are useful in practice. Finding an IS is a way of asking, which vertices do not have a relationship. For instance, if vertices are people and edges are familial relationship, an IS would define people who are not related.

A *path graph* has vertices that can be listed in order $v_1, v_2, …,v_n$ such
that edges are ${v_i, v_{i+i}}$ where $i = 1, 2, …, n-1$. That is rather
complicated definition for a simple concept that is easily visualized. The image
below represents a path graph.

There is only one path through the graph and each vertex is connected to the preceding vertex. By this definition, there will always be $n-1$ edges.

With preliminary concepts out of the way, it’s time to define the problem that this algorithm is designed to solve. Given a path graph where each vertex has an associated non-negative weight, find the independent set with the highest cumulative weight.

## Applications

- Set packing

## Asymptotic Complexity

\(O(n)\)

## Pseudo Code

The pseudo code below is a particularly slow implementation ($O(n^2)$) of a maximum independent set algorithm. However, it will help the reader understand the mechanics before examining the more complex version below.

```
max_weight_is:
inputs:
V = array of vertices arranged to represent a path graph
n = number of vertices
if n = 0:
return [] // Empty Set
if n = 1:
return V
result1 = max_weight_is V[0] - V[n - 1] // recurse
result2 = max_weight_is V[0] - V[n - 2] // recurse
if(result1 > result2 + V[n])
return result 1
else
return result2 + V[n]
```

The version below has an optimal run time ($O(n)$).

```
max_weight_is:
inputs:
V = array of vertices arranged to represent a path graph
n = number of vertices
S = solutions array of size n + 1
S[0] = []
S[1] = V[0]
i = 2 to n:
if S[i-1] > S[i-2] + V[i-1]:
S[i] = S[i-1]
else
S[i] = S[i-2] + V[i-1]
return S[n+1]
```

## Source Code

Relevant Files:

Click here for build and run instructions