On the feedback vertex set polytope of a series–parallel graph

AbstractThe minimum weight feedback vertex set problem (FVS) on series–parallel graphs can be solved in O(n) time by dynamic programming. This solution, however, does not provide a “nice” certificate of optimality. We prove a min–max relation for FVS on series–parallel graphs with no induced subdivision of K2,3 (a class of graphs containing the outerplanar graphs), thereby establishing the existence of nice certificates for these graphs. Our proof relies on the description of a complete set of inequalities defining the feedback vertex set polytope of a series–parallel graph with no induced subdivision of K2,3. We also prove that many of the inequalities described are facets of this polytope