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 Ω(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−ε n ) and at most O(min{n 1+ε , (∆M ) 2/3+ε }), for any constant ε > 0, where M is the number of temporal edges and ∆ 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.  ACM Subject Classification Graphs and networks are ubiquitous in Computer Science, as they provide a natural and useful abstraction of many complex systems (e.g., transportation and communication networks) and processes (e.g., information spreading, epidemics, routing), and also of the interaction between individual entities or particles (e.g., social networks, chemical and biological networks). Traditional graph theoretic models assume that the structure of the network and the strength of interaction are time-invariant. However, as observed in e.g., [3, 19] , in many applications of graph theoretic models, the availability and the weights of the edges are actually time-dependent. For instance, one may think of information spreading and distributed computation in dynamic networks (see e.g., [6, 12, 19, 20] ), of mobile adhoc and sensor networks (see e.g., [22]), of transportation networks and route planning (see e.g., [3, 15] ), of epidemics, biological and ecological networks (see e.g., [17, 19] ), and of influence systems and coevolutionary opinion formation (see e.g., [5, 9] ). Several variants of time-dependent graphs have been suggested as abstractions of such settings and computational problems (see e.g., [6] and the references therein). No matter the particular variant, the main research questions are usually related either to optimizing or exploiting temporal connectivity or to computing short time-respecting paths (see e.g., [1, 2, © Kyriakos Axiotis and Dimitris Fotakis; licensed under Creative Commons License CC-BY Conference title on which this volume is based on.
The proof in REF exhibits an infinite family of temporally connected graphs with Θ(n 2 ) edges that do not admit o(n 2 )-sparse spanners.
On the Size and the Approximability of Minimum Temporally Connected Subgraphs
ArXiv
ArXiv
Computer Science Mathematics