The power of interval models for computing graph centralities

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