Groupe d’études et de recherche en analyse des décisions

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

Samuel Fiorini Université libre de Bruxelles, Belgique

Le problème du transversal de cycles de poids minimum dans un graphe série-parallèle peut être résolu en temps linéaire par un algorithme de programmation dynamique. Cependant un tel algorithme ne fournit pas de certificat d'optimalité satisfaisant. Nous donnons une relation de type min-max pour les transversaux de cycles dans les graphes séries-parallèles ne contenant pas de subdivision de \(K(2,3)\) induite. Notre preuve revient à trouver une description complète du polytope des transversaux de cycles dans les graphes séries-parallèles sans subdivision de \(K(2,3)\) induite.