Skip to Main content Skip to Navigation
New interface
Reports (Research report)

On the recognition of $C_4$-free and $1/2$-hyperbolic graphs

David Coudert 1, 2 Guillaume Ducoffe 1 
1 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : 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.26})$ time.
Document type :
Reports (Research report)
Complete list of metadata

Cited literature [40 references]  Display  Hide  Download
Contributor : David Coudert Connect in order to contact the contributor
Submitted on : Tuesday, July 22, 2014 - 3:26:41 PM
Last modification on : Wednesday, October 26, 2022 - 8:16:25 AM
Long-term archiving on: : Tuesday, April 11, 2017 - 4:15:41 PM


Files produced by the author(s)


  • HAL Id : hal-00937935, version 2


David Coudert, Guillaume Ducoffe. On the recognition of $C_4$-free and $1/2$-hyperbolic graphs. [Research Report] RR-8458, INRIA. 2014, pp.20. ⟨hal-00937935v2⟩



Record views


Files downloads