标题： 首先，最快，最短：在各种路径度量下的时间图实现 显示英文标题

标题： Foremost, Fastest, Shortest: Temporal Graph Realization under Various Path Metrics

摘要： 在本工作中，我们遵循时间图实现的当前趋势，其中给定一个属性P，目标是确定是否存在具有属性P的时间图，即边集随时间变化的图。 我们考虑的问题中，属性P是给定一个关于成对时间路径的持续时间、长度或最早到达时间的预定矩阵。 也就是说，我们给定一个矩阵D，并询问是否存在一个时间图，使得对于任何顶点有序对(s, t)，Ds,t等于从s到t的最小化该特定时间路径度量的任何时间路径的持续时间（长度，或最早到达时间）。 据我们所知，我们是第一个考虑这些问题的。 我们分析了多种设置下的这些问题，例如：严格和非严格路径、周期性和非周期性时间图，以及每条边的标签数量有限（即每条边在时间上的出现次数有限）。 与所有其他路径度量不同，我们证明对于最早到达时间，可以在周期性和非周期性时间图以及严格和非严格路径中实现多项式时间算法。 然而，当矩阵不包含单个整数而是允许值的集合或范围时，这个问题变得NP难。 正如我们所展示的，在这种情况下，当具有多个值的条目数量较小时，问题仍然可以高效求解，即我们为这类条目的数量开发了一个FPT算法。 对于最快路径的情况，我们得出了新的难度结果，回答了Klobas、Mertzios、Molter和Spirakis [Theor. Comput. Sci. '25] 关于该问题相对于顶点覆盖数的参数化复杂性的开放问题，并显著改进了之前关于反馈顶点集数的难度结果。 在考虑最短路径时，我们证明周期性版本是多项式时间可解的，而非周期性版本则变得NP难。 显示英文摘要

摘要： In this work, we follow the current trend on temporal graph realization, where one is given a property P and the goal is to determine whether there is a temporal graph, that is, a graph where the edge set changes over time, with property P . We consider the problems where as property P , we are given a prescribed matrix for the duration, length, or earliest arrival time of pairwise temporal paths. That is, we are given a matrix D and ask whether there is a temporal graph such that for any ordered pair of vertices (s, t), Ds,t equals the duration (length, or earliest arrival time, respectively) of any temporal path from s to t minimizing that specific temporal path metric. For shortest and earliest arrival temporal paths, we are the first to consider these problems as far as we know. We analyze these problems for many settings like: strict and non-strict paths, periodic and non-periodic temporal graphs, and limited number of labels per edge (that is, limited occurrence number per edge over time). In contrast to all other path metrics, we show that for the earliest arrival times, we can achieve polynomial-time algorithms in periodic and non-periodic temporal graphs and for strict and and non-strict paths. However, the problem becomes NP-hard when the matrix does not contain a single integer but a set or range of possible allowed values. As we show, the problem can still be solved efficiently in this scenario, when the number of entries with more than one value is small, that is, we develop an FPT-algorithm for the number of such entries. For the setting of fastest paths, we achieve new hardness results that answers an open question by Klobas, Mertzios, Molter, and Spirakis [Theor. Comput. Sci. '25] about the parameterized complexity of the problem with respect to the vertex cover number and significantly improves over a previous hardness result for the feedback vertex set number. When considering shortest paths, we show that the periodic versions are polynomial-time solvable whereas the non-periodic versions become NP-hard.