Parameterized algorithms for multi-label periodic temporal graph realization
Thomas Erlebach, Nils Morawietz, Petra Wolf · Theoretical Computer Science · 2025
In the periodic temporal graph realization problem introduced by Klobas et al. [SAND '24] one is given a period Δ and an n × n matrix D of desired fastest travel times, and the task is to decide if there is a simple periodic temporal graph with period Δ such that the fastest travel time between any pair of vertices matches the one specified by D . We generalize the problem from simple temporal graphs to temporal graphs where each edge can appear up to ℓ times in each period, for some given integer ℓ . For the resulting problem Multi-Label Periodic TGR , we show that it is fixed-parameter tractable for parameter n and for parameter vc + Δ , where vc is the vertex cover number of the underlying graph. We also show the existence of a polynomial kernel for parameter nu + d max , where nu is the number of non-universal vertices of the underlying graph and d max is the largest entry of D . Furthermore, we show that the problem is NP -hard for each ℓ ≥ 5 , even if the underlying graph is a tree, a case that was known to be solvable in polynomial time if the task is to construct a simple periodic temporal graph, that is, if ℓ = 1 .