Discrete Mathematics and Optimization Seminar
ODILE MARCOTTE |
CRM - UQAM
Monday November 20th at 4.30pm
Burnside 1205
Title. On the feedback vertex set polytope of a series-parallel graph.
Abstract.
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.
This is joint work with Samuel Fiorini, from the Universite Libre de
Bruxelles.