Optimal Extended Formulations from Optimal Dynamic Programming Algorithms
Vertex Subset Problems (VSPs) are a class of combinatorial optimization problems on graphs where the goal is to find a subset of vertices satisfying a predefined condition. Two prominent approaches for solving VSPs are dynamic programming over tree-like structures, such as tree decompositions or clique decompositions, and linear...