2026-07-24T11:29:27Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6293 2024-03-06T10:37:58Z ddc:004 open_access

On the Size and the Approximability of Minimum Temporally Connected Subgraphs Axiotis, Kyriakos Fotakis, Dimitris Temporal Graphs Temporal Connectivity Approximation Algorithms We consider temporal graphs with discrete time labels and investigate the size and the approximability of minimum temporally connected spanning subgraphs. We present a family of minimally connected temporal graphs with n vertices and Omega(n^2) edges, thus resolving an open question of (Kempe, Kleinberg, Kumar, JCSS 64, 2002) about the existence of sparse temporal connectivity certificates. Next, we consider the problem of computing a minimum weight subset of temporal edges that preserve connectivity of a given temporal graph either from a given vertex r (r-MTC problem) or among all vertex pairs (MTC problem). We show that the approximability of r-MTC is closely related to the approximability of Directed Steiner Tree and that r-MTC can be solved in polynomial time if the underlying graph has bounded treewidth. We also show that the best approximation ratio for MTC is at least O(2^{log^{1-epsilon}(n)} and at most O(min{n^{1+epsilon},(Delta*M)^{2/3+epsilon}), for any constant epsilon > 0, where M is the number of temporal edges and Delta is the maximum degree of the underlying graph. Furthermore, we prove that the unweighted version of MTC is APX-hard and that MTC is efficiently solvable in trees and 2-approximable in cycles. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Kyriakos Axiotis and Dimitris Fotakis 2016 Is Part Of LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2016.149 urn:nbn:de:0030-drops-62936 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.149 eng https://creativecommons.org/licenses/by/3.0/legalcode