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
Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués, CRISAM - Inria Sophia Antipolis - Méditerranée
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.
Complete list of metadatas

Cited literature [40 references]  Display  Hide  Download

https://hal.inria.fr/hal-00937935
Contributor : David Coudert <>
Submitted on : Tuesday, July 22, 2014 - 3:26:41 PM
Last modification on : Wednesday, October 16, 2019 - 2:48:40 PM
Long-term archiving on: Tuesday, April 11, 2017 - 4:15:41 PM

File

RR-8458v2.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00937935, version 2

Citation

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⟩

Share

Metrics

Record views

513

Files downloads

796