Opening Algorithms for Bounded Treewidth
Algorithms for Bounded Treewidth
- Length
- 29 min
- Level
- Graduate
- Recorded
- Carnegie Mellon University2020
Chapter 1 of 4: Algorithms for bounded treewidth
O'Donnell runs a 3-coloring dynamic program on nice tree decompositions and states Courcelle's theorem.
Treewidth algorithms either find a low-width tree decomposition or use one to solve NP-hard graph problems. O'Donnell surveys decomposition results, from the 1987 algorithm of Arnborg, Corneil and Proskurowski to later linear-time and approximate methods. Courcelle's theorem then shows that any property expressible in extended monadic second-order logic is decidable in linear time on bounded-treewidth graphs. For a concrete algorithm, he converts decompositions into nice ones with leaf, introduce, forget and join nodes, then fills 3-coloring tables bottom-up. Planar graphs close the session through Epstein's diameter–treewidth theorem and Baker's edge partition, which yields approximation schemes. Lecture 22(c) of CMU's graduate CS Theory Toolkit, it assumes graph theory, NP-completeness and basic logic.
Treewidth algorithms either find a low-width tree decomposition or use one to solve NP-hard graph problems. O'Donnell surveys decomposition results, from the 1987 algorithm of Arnborg, Corneil and Proskurowski to later linear-time and approximate methods. Courcelle's theorem then shows that any property expressible in extended monadic second-order logic is decidable in linear time on bounded-treewidth graphs. For a concrete algorithm, he converts decompositions into nice ones with leaf, introduce, forget and join nodes, then fills 3-coloring tables bottom-up. Planar graphs close the session through Epstein's diameter–treewidth theorem and Baker's edge partition, which yields approximation schemes. Lecture 22(c) of CMU's graduate CS Theory Toolkit, it assumes graph theory, NP-completeness and basic logic.
Arnborg, Corneil, Proskurowski '87
Bodlander '96
Bodlander, Drange, Dregi, Fomin, Lokshtanov, Pilipchuk '13

This lecture
Lecture 72 of 89 of A Theorist's Toolkit.
Choose a node to see how it connects to this lecture. What comes before is on the leftat the top. What comes after is on the rightat the bottom. The ring is what it teaches. People and places are above. Other lectures and books are below.
Press a chosen node again to open it.
Your comment is kept while you sign up.Sign in
Feige, Hajiaghayi, J. Lee '08