On the size and the approximability of minimum temporally connected subgraphs

DOI10.4230/LIPICS.ICALP.2016.149MaRDI QIDQ4598293zbMATH OpenOpenAlexFDO

Authors Kyriakos Axiotis, Dimitris Fotakis

Publication date 19 December 2017

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)

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.

Recommendations

• On Temporally Connected Graphs of Small Cost
• The complexity of optimal design of temporally connected graphs
• Temporal network optimization subject to connectivity constraints
• Temporal cliques admit sparse spanners
• Traveling salesman problems in temporal graphs

Cited in

(21)

• Coloring temporal graphs
• Temporal cliques admit sparse spanners
• Blackout-tolerant temporal spanners
• The complexity of computing optimum labelings for temporal connectivity
• Finding Temporal Paths Under Waiting Time Constraints.
• Temporal cliques admit sparse spanners
• Blackout-tolerant temporal spanners
• The complexity of optimal design of temporally connected graphs
• Invited paper: Simple, strict, proper, happy: a study of reachability in temporal graphs
• Edge exploration of temporal graphs
• On Temporally Connected Graphs of Small Cost
• Finding temporal paths under waiting time constraints
• As Time Goes By: Reflections on Treewidth for Temporal Graphs
• The complexity of finding small separators in temporal graphs
• Temporal reachability minimization: delaying vs. deleting
• Sharp Thresholds in Random Simple Temporal Graphs
• Feedback edge sets in temporal graphs
• The complexity of finding small separators in temporal graphs
• Simple, strict, proper, happy: a study of reachability in temporal graphs
• Edge exploration of temporal graphs
• Computing maximum matchings in 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)