 |
Extended formulations for induced tree and path polytopes of chordal graphs
1 : Institut de Recherche en Informatique et Systèmes Aléatoires
(IRISA)
Université de Rennes, Institut National des Sciences Appliquées - Rennes, Université de Bretagne Sud, École normale supérieure - Rennes, Institut National de Recherche en Informatique et en Automatique, CentraleSupélec, Centre National de la Recherche Scientifique, IMT Atlantique
In this work, we characterize the induced tree and path polytopes of chordal graphs in an extended space, implying the polynomial resolution of finding maximum vertex and edge weighted such induced subgraphs in chordal graphs.
