Parameterized Algorithms for Multi-Label Periodic Temporal Graph Realization

Erlebach, Thomas; Morawietz, Nils; Wolf, Petra

Abstract

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.

Citation

Erlebach, T., Morawietz, N., & Wolf, P. (2024, June). Parameterized Algorithms for Multi-Label Periodic Temporal Graph Realization. Presented at 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024), Patras, Greece

• Presentation Conference Type: Conference Paper (published)
• Conference Name: 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)
• Start Date: Jun 5, 2024
• End Date: Jun 7, 2024
• Acceptance Date: Mar 21, 2024
• Online Publication Date: May 31, 2024
• Publication Date: May 31, 2024
• Deposit Date: Apr 2, 2024
• Publicly Available Date: May 31, 2024
• Publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
• Peer Reviewed: Peer Reviewed
• Volume: 292
• Pages: 12:1-12:16
• Series Title: Leibniz International Proceedings in Informatics
• Book Title: Proceedings of the 3rd Symposium on Algorithmic Foundations of Dynamic Networks
• DOI: https://doi.org/10.4230/LIPIcs.SAND.2024.12
• Public URL: https://durham-repository.worktribe.com/output/2368008