Dynamic Programming

16.1 Weighted Independent Set Problem

Input: An undirected graph G = (V, E) and a nonnegative weight w_v for each vertex v in V.
Output: An independent set S in V of G with maximum-possible sum w_v of vertex weights.

Simply put, we need to attain the independent set where none of each two vertex are connected.

However, here the greedy algorithm is not applicable considering the features of the problem.

Also, the divide and conqure approach is also not suitable here, because however we defuse the problem into 2 subproblems, we would lose the information containing the connections between 2 subproblems.

But, worth of noticing, the problem can be solved in $O(n^2)$ time by divide and conquer algorithm.

16.2 Optimal Substructure

Notation: Let $S \in V$ be a max-weight independent set (IS). Let $v_n$ = last vertex of path.

A Case Analysis

Case 1: Suppose $v_n \notin S$. Let $G’=G$ with $v_n$ Deleted.

• Note: $S$ also an IS of $G’$.
• Note: $S$ must be a max-weight IS of $G’ $. if $S^*$ was better, it would also be better than $S$ in $G$. [contradiction].

Case 2: Suppose $v_n \in S$. Let $G”=G$ with $v_{n-1}, v_n$ Deleted.

• Note: $S – {v_n}$ is an IS of $G”$.
• Note: Must in fact be a max-weight IS of $G”$ if $S^$ is better than $S$ in $G”$, then $S^\cup {v_n}$ is better than $S$ in $G$. [contradiction].

Toward an Algotirhm

• Upshot: A max-weight IS must-be either: (i) a max-weight IS of $G’$ or (ii) $v_n + a$ max weight IS of $G”$
• Corollary: If we knew whether or not $v_n$ was in the max-weight IS, could recursively compute the max-weight IS of $G”$ and be done.

Recursive-based DP

As we discussed above, the algorithm we designed so far can be described as follows:

- recursively compute S1 = max-weight IS of G'
- recursively compute S2 = max-weight IS of G''
- return S1 or S2 + v_n, whichever is better

Even though it’s correct, it usually costs EXPONENTIAL time. However, we can simplify the process by memoization.

Important question: How many distinct subproblems ever get solved by this algorithm?

• $\Theta(n)$.

Thus, we can solve the subproblem while cache its solution in a global table for $O(1)$-time lookup later on.

Even better: Reformulate as a bottom-up iterative algorithm. Let $G_i = $ 1st $i$ vertices of $G$.

So the problem can be depicted as: Main loop:

for i in range(2, n):
A[i] = max{A[i-1], A[i-2] + w_i}

Run Time: $O(n)$.

Reconstruction Algorithm

Even though we are able to get the optimal solution in linear time, we aren’t able to retrace the process of decision-making, i.e. algorithm computes the value of a max-weight IS, not such an IS itself.

Trace back through filled-in array to reconstruct optimal solution.

Key point: We know that a vertex $v_i$ belongs to a max-weight IS of $G_i$ <-> $w_i$ + max-weight IS of $G_{i – 2}\ge$ max-weight IS of $G_{i-1}$.