The power of interval models for computing graph centralities

Guillaume DUCOFFE
National Institute for Research and Development in Informatics – ICI Bucharest

University of Bucharest, Faculty of Mathematics and Computer Science, Bucharest, Romania

Abstract: Food webs, some scheduling problems and DNA molecules all have in common a “linear structure” which can be captured through the idealized model of interval graphs (intersection graphs of intervals on a line). However, real data is prone to errors and noise, thus raising the question of whether the algorithmic results obtained for the interval graphs could be extended to more realistic models of “almost interval” graphs. This question is addressed in the context of computing the vertex eccentricities, one of the most studied centrality indices in order to determine the relative importance of nodes in a network. A positive answer is given for the interval + graphs and a negative one (assuming plausible complexity hypotheses) for the graphs of bounded interval number. In particular, an almost linear-time algorithm for computing all vertex eccentricities in an interval+ graph, for any fixed , is presented, thus improving on the recent quadratic-time algorithm of (Bentert & Nichterlein, 2022) for this problem.

Keywords: interval graphs, interval number, distance to triviality, diameter, eccentricities computation, SETH-hardness.

View full text

Guillaume DUCOFFE, The power of interval models for computing graph centralities, Romanian Journal of Information Technology and Automatic Control, ISSN 1220-1758, vol. 32(4), pp. 33-44, 2022.