On the recognition of $C_4$-free and $1/2$-hyperbolic graphs
Résumé
The shortest-path metric $d$ of a connected graph $G$ is $\frac{1}{2}$-hyperbolic if, and only if, it satisfies $d(u,v) + d(x,y) \leq \max \{ d(u,x) + d(v,y), d(u,y) + d(v,x) \} + 1$, for every $4$-tuple $u,x,v,y$ of $G$. We show that the problem of deciding whether an unweighted graph is $\frac{1}{2}$-hyperbolic is subcubic equivalent to the problem of determining whether there is a chordless cycle of length $4$ in a graph. An improved algorithm is also given for both problems, taking advantage of fast rectangular matrix multiplication. In the worst case it runs in $O(n^{3.333953})$ time.
La métrique $d$ des plus courts chemins d'un graphe connexe $G$ est $\frac{1}{2}$-hyperbolique si et seulement si elle satisfait $d(u,v) + d(x,y) \leq \max \{ d(u,x) + d(v,y), d(u,y) + d(v,x) \} + 1$ pour tout quadruplet $u,x,v,y$ de $G$. Nous montrons que résoudre le problème de décider si un graphe est $1/2$-hyperbolique revient à résoudre le problème de décider si un graphe contient un cycle sans corde de longueur 4, et inversement, en proposant une transformation en temps sous-cubique d'un problème vers l'autre. De plus, nous proposons un algorithme en temps $O(n^{3.333953})$, basé sur la multiplication de matrices rectangulaires, pour résoudre chacun de ces problèmes. Nous améliorons ainsi l'état de l'art.
Origine : Fichiers produits par l'(les) auteur(s)