Opening Trees and Series-Parallel Graphs
Trees and Series-Parallel Graphs
- Length
- 21 min
- Level
- Graduate
- Recorded
- Carnegie Mellon University2020
Chapter 1 of 4: Before the lecture
Maximum independent set and constraint satisfaction problems, NP-hard in general, become tractable on trees and series-parallel graphs, and this observation leads up to the definition of treewidth. O'Donnell starts from the linear-time dynamic program over subtrees that solves maximum independent set on a tree. He then defines the primal graph of a CSP instance, which joins variables that share a constraint. Series-parallel graphs, roughly the graphs of treewidth 2, are built recursively from single edges by series and parallel composition with designated source and target vertices. A bottom-up pass over this decomposition keeps four table entries, recording whether the source and target are included. Lecture 22(a) of CMU's graduate CS Theory Toolkit assumes NP-hardness, dynamic programming and basic graph theory, and closes with questions on planar graphs and decompositions.
Your comment is kept while you sign up.Sign in
O'Donnell extends the tree dynamic program for maximum independent set to series-parallel graphs via four-entry tables.
Maximum independent set and constraint satisfaction problems, NP-hard in general, become tractable on trees and series-parallel graphs, and this observation leads up to the definition of treewidth. O'Donnell starts from the linear-time dynamic program over subtrees that solves maximum independent set on a tree. He then defines the primal graph of a CSP instance, which joins variables that share a constraint. Series-parallel graphs, roughly the graphs of treewidth 2, are built recursively from single edges by series and parallel composition with designated source and target vertices. A bottom-up pass over this decomposition keeps four table entries, recording whether the source and target are included. Lecture 22(a) of CMU's graduate CS Theory Toolkit assumes NP-hardness, dynamic programming and basic graph theory, and closes with questions on planar graphs and decompositions.
This lecture
Lecture 70 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.