Last time we spoke a bit about dynamic programming; specifically about solving Weighted Independent Set on trees. You can read about it here. Today things will get a bit more serious. I’ll start by briefly explaining how the algorithm we sketched for trees extends to graphs of bounded tree-width and then I’ll speak about the thing that makes dynamic programming fast: namely the quotinenting of solution spaces.
This last part is work in progress; feel free to share any feedback in the comments below.
This is a companion discussion topic for the original entry at https://bmbumpus.com/2022/11/16/compositional-algorithms-%c2%a72-quotienting-solution-spaces/