The complexity of computing optimum labelings for temporal connectivity

Klobas, Nina; Mertzios, George; Molter, Hendrik; Spirakis, Paul

Abstract

A graph is temporally connected if a strict temporal path exists from every vertex u to every other vertex v. This paper studies temporal design problems for undirected temporally connected graphs. Given a connected undirected graph G, the goal is to determine the smallest total number of time-labels |λ| needed to ensure temporal connectivity, where |λ| denotes the sum, over all edges, of the size of the set of labels associated to an edge. The basic problem, called Minimum Labeling (ML) can be solved optimally in polynomial time. We introduce the Min. Aged Labeling (MAL) problem, which involves connecting the graph with an upper-bound on the maximum label, the Min. Steiner Labeling (MSL) problem, focusing on connecting specific important vertices, and the age-restricted version of MSL, Min. Aged Steiner Labeling (MASL). We show that MAL is NP-complete, MASL is W[1]- hard, and while MSL remains NP-hard, it is FPT with respect to the number of terminals.

Citation

Klobas, N., Mertzios, G., Molter, H., & Spirakis, P. (2024). The complexity of computing optimum labelings for temporal connectivity. Journal of Computer and System Sciences, 146, Article 103564. https://doi.org/10.1016/j.jcss.2024.103564

• Journal Article Type: Article
• Acceptance Date: Jun 28, 2024
• Online Publication Date: Jul 9, 2024
• Publication Date: 2024-12
• Deposit Date: Jul 20, 2024
• Publicly Available Date: Jul 22, 2024
• Journal: Journal of Computer and System Sciences
• Print ISSN: 0022-0000
• Electronic ISSN: 1090-2724
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 146
• Article Number: 103564
• DOI: https://doi.org/10.1016/j.jcss.2024.103564
• Public URL: https://durham-repository.worktribe.com/output/2606625