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!
