The minimum weight feedback vertex set problem (FVS) on series-parallel graphs can be solved in linear time by dynamic programming. However, such an algorithm does not provide nice certificates of optimality. We prove a min-max relation for FVS on series-parallel graphs without an induced subdivision of K(2,3) (a class of graphs containing the outerplanar graphs), thereby establishing the existence of nice certificates for these graphs. Our proof technique consists of determining a complete set of inequalities describing the feedback vertex set polytope of a series-parallel graph with no induced subdivision of K(2,3).
Group for Research in Decision Analysis