Counting Temporal Paths

17^th May 2022, 10:00 Zoom
Dr. Kitty Meeks
School of Computing Science, University of Glasgow

Abstract

The betweenness centrality of a vertex v is an important centrality measure that quantifies how many optimal paths between pairs of other vertices visit v. Computing betweenness centrality in a temporal graph, in which the edge set may change over discrete timesteps, requires us to count temporal paths that are optimal with respect to some criterion. I will explain how, for several natural notions of optimality (including foremost or fastest temporal paths) this counting problem reduces to #Temporal Path, the problem of counting all temporal paths between a fixed pair of vertices; like the problems of counting foremost and fastest temporal paths, #Temporal Path is #P-hard in general. In this talk I will describe recent progress towards a systematic study of the parameterised and approximation complexity of #Temporal Path, including strong intractability results and some exact and approximate FPT algorithms for special cases.

This is joint work with Jessica Enright (Glasgow) and Hendrik Molter (Ben-Gurion University of the Negev).

Additional Materials

• https://arxiv.org/abs/2202.12055