Klobas, Nina ;
Mertzios, George B. ;
Molter, Hendrik ;
Spirakis, Paul G.
The Complexity of Computing Optimum Labelings for Temporal Connectivity
Abstract
A graph is temporally connected if there exists a strict temporal path, i.e., a path whose edges have strictly increasing labels, from every vertex u to every other vertex v. In this paper we study temporal design problems for undirected temporally connected graphs. The basic setting of these optimization problems is as follows: given a connected undirected graph G, what is the smallest number λ of timelabels that we need to add to the edges of G such that the resulting temporal graph (G,λ) is temporally connected? As it turns out, this basic problem, called Minimum Labeling (ML), can be optimally solved in polynomial time. However, exploiting the temporal dimension, the problem becomes more interesting and meaningful in its following variations, which we investigate in this paper. First we consider the problem Min. Aged Labeling (MAL) of temporally connecting the graph when we are given an upperbound on the allowed age (i.e., maximum label) of the obtained temporal graph (G,λ). Second we consider the problem Min. Steiner Labeling (MSL), where the aim is now to have a temporal path between any pair of "important" vertices which lie in a subset R ⊆ V, which we call the terminals. This relaxed problem resembles the problem Steiner Tree in static (i.e., nontemporal) graphs. However, due to the requirement of strictly increasing labels in a temporal path, Steiner Tree is not a special case of MSL. Finally we consider the agerestricted version of MSL, namely Min. Aged Steiner Labeling (MASL). Our main results are threefold: we prove that (i) MAL becomes NPcomplete on undirected graphs, while (ii) MASL becomes W[1]hard with respect to the number R of terminals. On the other hand we prove that (iii) although the ageunrestricted problem MSL remains NPhard, it is in FPT with respect to the number R of terminals. That is, adding the age restriction, makes the above problems strictly harder (unless P=NP or W[1]=FPT).
BibTeX  Entry
@InProceedings{klobas_et_al:LIPIcs.MFCS.2022.62,
author = {Klobas, Nina and Mertzios, George B. and Molter, Hendrik and Spirakis, Paul G.},
title = {{The Complexity of Computing Optimum Labelings for Temporal Connectivity}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {62:162:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772563},
ISSN = {18688969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16860},
URN = {urn:nbn:de:0030drops168603},
doi = {10.4230/LIPIcs.MFCS.2022.62},
annote = {Keywords: Temporal graph, graph labeling, foremost temporal path, temporal connectivity, Steiner Tree}
}
22.08.2022
Keywords: 

Temporal graph, graph labeling, foremost temporal path, temporal connectivity, Steiner Tree 
Seminar: 

47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)

Issue date: 

2022 
Date of publication: 

22.08.2022 