Enright Jessica, Meeks Kitty, Molter Hendrik
School of Computing Science, University of Glasgow, Glasgow, UK.
Department of Computer Science and Department of Industrial Engineering and Management, Ben-Gurion University of the Negev, Be'er Sheva, Israel.
Algorithmica. 2025;87(5):736-782. doi: 10.1007/s00453-025-01301-3. Epub 2025 Feb 25.
This work investigates the parameterised complexity of counting temporal paths. The problem of counting temporal paths is mainly motivated by temporal betweenness computation. The betweenness centrality of a vertex is an important centrality measure that quantifies how many optimal paths between pairs of other vertices visit . 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. For several natural notions of optimality, including or temporal paths, this counting problem reduces to #Temporal Path, the problem of counting 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. Motivated by the many applications of this intractable problem, we initiate a systematic study of the parameterised and approximation complexity of #Temporal Path. We show that the problem presumably does not admit an FPT-algorithm for the feedback vertex number of the static underlying graph, and that it is hard to approximate in general. On the positive side, we prove several exact and approximate FPT-algorithms for special cases.
本文研究了计数时间路径的参数复杂性。计数时间路径问题主要由时间中间性计算所驱动。顶点的中间性中心性是一种重要的中心性度量，它量化了其他顶点对之间有多少最优路径经过该顶点。在时间图（其中边集可能在离散时间步长上发生变化）中计算中间性中心性，要求我们对相对于某种标准最优的时间路径进行计数。对于几种自然的最优性概念，包括或时间路径，这种计数问题可归结为#时间路径，即计算固定顶点对之间时间路径的问题；与计数首要和最快时间路径的问题一样，#时间路径一般来说是#P - 难的。受这个难处理问题的众多应用的启发，我们对#时间路径的参数复杂性和近似复杂性展开了系统研究。我们表明，对于静态基础图的反馈顶点数，该问题大概不允许有固定参数可解（FPT）算法，并且一般来说很难近似。从积极的方面来看，我们为特殊情况证明了几种精确和近似的FPT算法。
