Graphes de recouvrement multichemins

Abstract

Cet article concerne des graphes de recouvrement (ci-après nommés {em spanneurs}) qui approximent des multichemins entre des paires de sommets de graphes non orientés de $n$ sommets. Habituellement un spanneur $H$ d'étirement $s$ pour un graphe $G$ est un sous-graphe couvrant tel que la distance dans $H$ entre deux sommets quelconques est au plus $s$ fois la distance dans $G$. Nous étudions ici des spanneurs qui approximent des cycles, et plus généralement $p$ chemins arêtes disjoints avec $p > 1$ pour toute paire de sommets. Pour un graphe $G$ non orienté nous construisons un $3$-spanneur $2$-multichemins avec $O(n^{3/2})$ arêtes. Autrement dit, pour toute paire de sommets $u, v$ la longeur du plus court cycle de $H$ la contenant est au plus le triple de celle dans $G$. On montre que cette construction est optimale en terme d'étirement et de nombre d'arêtes. Dans un second temps il est construit un $(2,8)$-spanneur $2$-multichemins contenant $O(n^{3/2})$ arêtes, ce qui revient à dire que pour toute paire de sommets $u, v$ la longueur du plus court cycle dans $H$ la contenant est au plus du double de celle dans $G$ plus une constante additive de $8$. Pour un $p$ quelconque on observe qu'il existe pour tous entiers $k$ et $p$ un $p(2k-1)$-spanneur $p$-multichemins possédant $O(p cdot n^{1+1/k})$ arêtes, en laissant ouverte la question de savoir s'il est possible à même taille de réduire l'étirement à $2k-1$ pour tout $p > 1$.