2026-09-16T09:46:13Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23255 2026-09-05T18:24:00Z ddc:004 open_access

Computing the Exact Radius of Large Graphs Funke, Stefan Proissl, Claudius Storandt, Sabine Radius Graph Center LP-type Combinatorial Dimension The radius of a graph is an important structural parameter which plays a key role in social network analysis and related applications. It measures the minimum shortest path distance that is required to reach all nodes in the graph from a single node. A node from which all other nodes are within a distance equal to the radius is called a center of the graph. In a graph with n nodes and m edges, the center and the radius can be determined in Õ(nm) by computing shortest path distances between all pairs of nodes. Fine-grained complexity results suggest that asymptotically faster algorithms are unlikely to exist. In this paper, we describe a novel randomized algorithm for exact radius computation in weighted digraphs with an expected running time in Õ(d³m) where d is the so-called combinatorial dimension. Our methodology is inspired by Clarkson’s algorithm for LP-type problems. The value of d denotes the size of a basis, which is a smallest subset of nodes which enforce the same radius as the whole node set. While we show that there exist graphs with d ∈ Θ(n), our empirical analysis reveals that even large real-world graphs have small combinatorial dimension. This allows us to compute the radius in near-linear time on such instances. The significantly improved scalability can be clearly observed in our experimental evaluation on a diverse set of benchmark graphs. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Stefan Funke and Claudius Proissl and Sabine Storandt 2025 Is Part Of LIPIcs, Volume 338, 23rd International Symposium on Experimental Algorithms (SEA 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SEA.2025.17 urn:nbn:de:0030-drops-232555 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2025.17 eng https://creativecommons.org/licenses/by/4.0/legalcode