2020/10/30 by Guillaume Ducoffe, Ducoffe, Guillaume
Computer Science · Engineering · Mathematics · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Limits and Structures in Graph Theory #Sparse and Compressive Sensing Techniques
paper · doi:10.48550/arxiv.2011.00001
openalex publication_date 2020/10/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The ball hypergraph of a graph G is the family of balls of all possible centers and radii in G. It has Helly number at most k if every subfamily of k-wise intersecting balls has a nonempty common intersection. A graph is k-Helly (or Helly, if k=2) if its ball hypergraph has Helly number at most k. We prove that a central vertex and all the medians in an n-vertex m-edge Helly graph can be computed w.h.p. in \cal O(m√(n)) time. Both results extend to a broader setting where we define a non-negative cost function over the vertex-set. For any fixed k, we also present an \cal O(m√(kn))-time randomized algorithm for radius computation within k-Helly graphs. If we relax the definition of Helly number (for what is sometimes called an "almost Helly-type" property in the literature), then our approach leads to an approximation algorithm for computing the radius with an additive one-sided error of at most some constant.