Chemins disjoints avec congestion dans les graphes à mineur exclu
Guyslain Naves, McGill University

Nous étudions le problème de trouver un nombre maximum de chemins disjoints dans des classes de graphes fermées par mineur. En général, ce problème est très difficile à approximer, même dans des classes très simple comme les graphes planaires, avec des ratios d'approximations en $\Omega(n)$. Pour contourner cette difficulté, plusieurs travaux autorisent l'utilisation de congestion: sous congestion $c$, on autorise $c$ chemins à utiliser la même arête. Ainsi, Chekuri et Shepherd ont pu trouver un algorithme avec ratio d'approximation constant et congestion 2, dans le cas des graphes planaires. Nous souhaitons généraliser ce résultat, et nous prouvons que pour les graphes à largeur d'arbre bornée, et pour les graphes plongeables dans une surface fixée, il existe des algorithmes avec ratio et congestion constants. Ces deux types de classes de graphes étant fermées par mineur, nous conjecturons que toute classe de graphes à mineur exclu admet de tels algorithmes.
Auteurs: Chandra Chekuri, Guyslain Naves, Bruce Shepherd.