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. 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. Motivated by the many applications of this intractable problem, we initiate a systematic study of the prameterised 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 proved several exact and approximate FPT-algorithms for special cases.

翻译：顶点与顶点之间的中间点是一个重要的核心度量,它量化了在时间图中其他顶点访问的两对之间多少条最佳路径与计算中间点之间的中间点,在时间图中,边缘集可能会在离散的时段上发生变化,要求我们计算一些标准的最佳时间线。对于一些最佳性自然概念,包括最强或最快的时间线,这个计数问题下降到#时道,计算固定的顶点之间所有时间线路的问题;像计算最高和最快的时道的问题一样,#时道一般是 #P-硬的。我们受到这个棘手问题许多应用的驱动,开始系统研究#时道的拼度和近似复杂性。我们表明,对于静态底图的反馈顶点数,问题大概不会包含FPT-algorithm,而且一般而言很难估计。在正面方面,我们证明一些特殊案例的精确和近似FPT-algoithm。