On the Wikipedia page of Tree decomposition, there is a dynamic programming algorithm for finding the maximum independent set in a graph of treewidth $k$.
- For a node $X_i$ of the tree decomposition, let $D_i$ be the union of the sets $X_j$ descending from $X_i$.
- For an independent set $S\subset X_i$, let $A(S,i)$ denote the size of the largest independent subset $I$ of $D_i$ such that $I \cap X_i = S$.
- Similarly, for an adjacent pair of nodes $X_i$ and $X_j$, with $X_i$ farther from the root of the tree than $X_j$, and an independent set $S \subset Xi \cap Xj$, let $B(S,i,j)$ denote the size of the largest independent subset $I$ of $D_i$ such that $I \cap X_i \cap X_j = S$.
- We may calculate these $A$ and $B$ values by a bottom-up traversal of the tree: $$ \begin{aligned} &A(S, i)=|S|+\sum_{j}\left(B\left(S \cap X_{j}, j, i\right)-\left|S \cap X_{j}\right|\right) \\ &B(S, i, j)=\max _{S^{\prime} \subset X_{i} \atop S=S^{\prime} \cap X_{j}} A\left(S^{\prime}, i\right) \end{aligned} $$
I'm curious about the source and proof of this algorithm. Up to now, I have consulted many articles such as
- Bertelè, U., & Brioschi, F. (1972). Nonserial Dynamic Programming.,
- Arnborg, S. (1985). Efficient algorithms for combinatorial problems on graphs with bounded decomposability — A survey. BIT Numerical Mathematics, 25, 1-23.,
- Bern, M.W., Lawler, E.L., & Wong, A.L. (1987). Linear-Time Computation of Optimal Subgraphs of Decomposable Graphs. J. Algorithms, 8, 216-235.,
- Bodlaender, H.L. (1988). Dynamic Programming on Graphs with Bounded Treewidth. ICALP.
- Arnborg, S., & Proskurowski, A. (1989). Linear time algorithms for NP-hard problems restricted to partial k-trees. Discret. Appl. Math., 23, 11-24.,
- Bodlaender, H.L., & Koster, A.M. (2008). Combinatorial Optimization on Graphs of Bounded Treewidth. Comput. J., 51, 255-269.,
but none of them seems to be consistent with this algorithm. Does anyone know the source of the algorithm? Thanks!
To the best of my knowledge, this algorithm oringinated from the following paper:
This paper actually introduced a general dynamic programming approach which solves many problems such as dominating set, vertex cover and independent set. The notion of partial $k$-tree in this paper is equivalent to a graph of treewidth at most $k$.
If you are only interested in the DP for independent set on graphs of bounded treewidth, I suggest to read chapter 7 of the followinng text book named Parameterized Algorithms, which will be more readable.