On the Size and the Approximability of Minimum Temporally Connected Subgraphs

DOI10.4230/LIPICS.ICALP.2016.149zbMATH Open1388.68299arXiv1602.06411OpenAlexW2962819912MaRDI QIDQ4598293FDOQ4598293

Dimitris Fotakis, Kyriakos Axiotis

Publication date: 19 December 2017

Abstract: 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^{lo{g}^{1-epsilon}n})$ and at most $O(min{n}^{1+epsilon},(DeltaM{)}^{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.

Full work available at URL: https://arxiv.org/abs/1602.06411

zbMATH Keywords

approximation algorithmstemporal graphstemporal connectivity

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Cited In (21)

• Temporal graph classes: a view through temporal separators
• Temporal reachability minimization: delaying vs. deleting
• Blackout-tolerant temporal spanners
• Temporal Cliques Admit Sparse Spanners
• Finding Temporal Paths Under Waiting Time Constraints.
• Computing maximum matchings in temporal graphs
• The complexity of computing optimum labelings for temporal connectivity
• Coloring temporal graphs
• Feedback edge sets in temporal graphs
• Edge exploration of temporal graphs
• Edge exploration of temporal graphs
• The Complexity of Finding Small Separators in Temporal Graphs
• As Time Goes By: Reflections on Treewidth for Temporal Graphs
• Blackout-tolerant temporal spanners
• On Temporally Connected Graphs of Small Cost
• Simple, strict, proper, happy: a study of reachability in temporal graphs
• Invited paper: Simple, strict, proper, happy: a study of reachability in temporal graphs
• Finding temporal paths under waiting time constraints
• The complexity of finding small separators in temporal graphs
• Temporal cliques admit sparse spanners
• Sharp Thresholds in Random Simple Temporal Graphs

This page was built for publication: On the Size and the Approximability of Minimum Temporally Connected Subgraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4598293)