This section describes an algorithm for finding the *Maximum Weighted
Independent Set* in a *Path Graph*. First, we’ll review the salient graph
concepts starting with *Independent Set*. 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.

The next salient concept is *Path Graph*. 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

## 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