RECOGNITION OF C4-FREE AND 1/2-HYPERBOLIC GRAPHS

The shortest-path metric d of a connected graph G is 1/2-hyperbolic if and only if it satisfies d(u, v) + d(x, y) <= 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 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.