Towards Classifying the Polynomial-Time Solvability of Temporal Betweenness Centrality
Maciej Rymar, Hendrik Molter, André Nichterlein, and Rolf Niedermeier
Vol. 27, no. 3, pp. 173-194, 2023. Regular paper.
Abstract In static graphs, the betweenness centrality of a graph vertex measures how many times this vertex is part of a shortest path between any two graph vertices. Betweenness centrality is efficiently computable and it is a fundamental tool in network science. Continuing and extending previous work, we study the efficient computability of betweenness centrality in temporal graphs (graphs with fixed vertex set but time-varying edge sets). Unlike in the static case, there are numerous natural notions of being a ''shortest'' temporal path (walk). Depending on which notion is used, it was already observed that the problem is #P-hard in some cases while polynomial-time solvable in others. In this conceptual work, we contribute towards classifying what a ''shortest path (walk) concept'' has to fulfill in order to gain polynomial-time computability of temporal betweenness centrality.

 This work is licensed under the terms of the CC-BY license.
Submitted: August 2021.
Reviewed: July 2022.
Revised: October 2022.
Accepted: February 2023.
Final: March 2023.
Published: May 2023.
Communicated by Ulrik Brandes
article (PDF)