G-2006-52
On the Feedback Vertex Set Polytope of a Series-Parallel Graph
et référence BibTeX
The 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.
Paru en septembre 2006 , 31 pages
Ce cahier a été révisé en juillet 2008