Group for Research in Decision Analysis

Une relation de type min-max pour les transversaux de cycles dans les graphes séries-parallèles

Samuel Fiorini Université libre de Bruxelles, Belgium

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).