Parameterized algorithms for multi-label periodic temporal graph realization

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.

Authors

• Thomas Erlebach
• Nils Morawietz
• Petra Wolf

Keywords

• Fixed-parameter tractability
• Almost-clique
• Kernelization
• Dynamic network
• Temporal graph