$k$-Chordal Graphs: from Cops and Robber to Compact Routing via Treewidth

Abstract

Nous présentons un algorithme quadratique qui, étant donné un graphe $G$ et un entier $k\geq 3$, certifie que $G$ contient un cycle induit de longueur $>k$, ou calcule une décomposition arborescente de $G$ dont chaque ''sac" induit un $k$-caterpillar (graphe qui contient un chemin dominant, de longueur au plus $k-2$). Entre autre, ce résultat implique que les graphes $k$-cordaux (sans cycle induit de longueur $>k$) de maximum degree $\Delta$ ont une largeur arborescente $O(k \cdot \Delta)$, ce qui améliore la borne $\Delta(\Delta-1)^{k-3}$ de Bodlaender et Thilikos (1997). De plus, l'hyperbolicité d'un graphe admettant une telle décomposition est $\leq \lfloor \frac{3}{2}k \rfloor $. Pour tout graphe qui admet une telle décomposition, nous proposons un algorithme de routage compact utilisant des adresses, en-têtes et tables de routage de taille $O(k\log n)$ bits et de stretch $O(k\cdot \log \Delta)$. Au passage, nous montrons que $k-1$ policiers sont suffisants pour capturer un voleur dans un graphe $k$-cordal.