Introduction to Dynamic Programming and Weighed Independent Set in Graph

1.  Problem Definition of WIS in Graph:

    --  Input: A path graph G = (V , E) with nonnegative weights on vertices.

    --  Output: Subset of nonadjacent vertices (an independent set ) of maximum total weight.

 

2.  Different Aproaches :

    --  Brute-force search requires exponential time.

    --  Greedy Approach: Iteratively choose the max-weight vertex not adjacent to any previously chosen vertex. ==> not correct

    --  Divide & Conquer Approach: Recursively compute the max-weight independent set of 1st half, ditto for

2nd half, then combine the solutions. ==> not clear how to fix the conflict of recursive sub-solutions

 

3.  Optimal Substructure

    --  Critical step: Reason about structure of an optimal solution. [In terms of optimal solutions of smaller subproblems]

    --  Motivation: This thought experiment narrows down the set of candidates for the optimal solution; can search through the small set using brute-force-search.

    --  Notation: Let S subset of V be a max-weight independent set (IS). Let vn = last vertex of path.

 

4.  Case Analysis

    --  Case 1: Suppose vn not in S. Let G' = G with vn deleted. ==> S must be a max-weight IS IS of G' because if S* was better, it would also be better than S in G. [contradiction]

    --  Case 2: Suppose vn in S. ==> Previous vertex vn-1 not in S then let G'' = G with vn-1 and vn deleted. ==> S - {vn} must be a max-weight IS of G'' because if S* is better than S-{vn} in G'', then S* U {vn} is better than S in G. [contradiction]

    --  A max-weight IS must be either 

       (i) a max-weight IS of G' or

       (ii) vn + a max-weight IS of G''

       Try both possibilities + return the better solution.

   

5.  Running Time Analysis

    --  Problem size only reduce 1 or 2 in each recursive call ==> exponential time in all

    --  Only O(n) distinct subproblems ever get solved by this algorithm (Only 1 for each "prefix" of the graph) [Recursion only plucks vertices off from the right]

 

6.  Eliminating Redundancy

    --  Obvious fix: The first time you solve a subproblem cache its solution in a global table for O(1)-time lookup later on.

    --  Even better: Reformulate as a bottom-up iterative algorithm:

        a) Let Gi = 1st i vertices of G.

        b) Populate array A left to right with A[i ] = value of max-weight IS of Gi .

        c) Initialization: A[0] = 0 , A[1] = w1

        d) Main loop: For i = 2, 3, ... , n:

            A[i ] = max{ A[i - 1] , A[i - 2] + wi }

    --  Running time : O(n)

 

7.  A Reconstruction Algorithm :

    --  Algorithm computes the value of a max-weight IS, not such an IS itself.

    --  Correct but not ideal: Store optimal IS of each Gi in the array in addition to its value.

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

    --  Key point: A vertex vi belongs to a max-weight IS of Gi <==> wi + max-weight IS of Gi-2 >= max-weight IS of Gi-1.

    --  Implementation: 

        a) Let A = filled-in array.

        b) Let S = empty set.

        c)  While i >= 1 [scan through array from right to left]

             - If A[i - 1] >= A[i - 2] + wi [i.e. case 1 wins]

               - Decrease i by 1

             - Else [i.e., case 2 wins]

               - Add vi to S, decrease i by 2

         d) Return S

    --  Running Time: O(n) 

 

8)  Principles of Dynamic Programming

    --  Fact: Our WIS algorithm is a dynamic programming algorithm!

    --  Key ingredients of dynamic programming:

        (1) Identify a small number of subproblems

            [e.g., compute the max-weight IS of Gi for i = 0, 1, ... , n]

        (2) Can quickly+correctly solve "larger" subproblems given the solutions to "smaller subproblems"

            [usually via a recurrence such as A[i ] = max { A[i - 1],A[i - 2] + wi } ]

        (3) After solving all subproblems, can quickly compute the final solution

            [usually, it's just the answer to the "biggest" subproblem]