Let @math be a labeled graph on @math vertices with @math a locally injective mapping that assigns to every edge a single integer label. The label is seen as a discrete time when the edge is present. This graph is temporally connected if a path exists with increasing labels from every vertex to every other vertex. In a seminal paper, Kempe, Kleinberg, and Kumar (JCSS 2002) asked whether, given such a labeled graph, a sparse subset of edges can always be found that preserves temporal connectivity if the other edges are removed -- we call such subsets temporal spanners . Recently, Axiotis and Fotakis (ICALP 2016) answered negatively, exhibiting a family of minimally connected temporal graphs with @math edges. The natural question then becomes whether sparse spanners can be found in specific classes of dense graphs. In this article, we settle the question positively for complete graphs, showing that one can always remove all but @math edges, whatever the labels, while preserving temporal connectivity. The best approach so far led to removing only @math edges, leaving the asymptotic density of the graph unchanged (, ToCS 2017). We start by observing that the same argument can be generalized to removing @math edges (a sixth of the edges). Then, using a completely different approach, we establish a gradual set of results, showing that a quarter of the edges can be removed, then half of the edges, and eventually all but @math edges. This result is robust in the sense that it extends, under mild assumptions, to more general models of temporal cliques where the labels may not be locally unique and a same edge may have several labels. The main open question is now to understand where the separation occurs between graphs that admit sparse spanners and graphs that do not.
In this paper, we refer to subsets of edges that preserve temporal connectivity as temporal spanners , inspired by their analogues in standard graphs and geometry (see, for example, @cite_0 , @cite_3 , and @cite_15 ), and to the process of removing edges while preserving temporal connectivity as simplification (or sparsification). The model considered in @cite_17 assumes that every edge in @math is given a single presence time, which allows one to formulate the problem in terms of subsets of edges . In fact, it is immediately shown in @cite_17 that one may label an hypercube so that none of its edges can be removed, leading to an update of the question to finding a subset of density @math .
@cite_0 @cite_15 @cite_3 @cite_17
2461566632 2923258301 2884564598 2835349798
We study the design of small cost temporally connected graphs, under various constraints. We mainly consider undirected graphs of n vertices, where each edge has an associated set of discrete availability instances (labels). A journey from vertex u to vertex v is a path from u to v where successive path edges have strictly increasing labels. A graph is temporally connected iff there is a (u, v)-journey for any pair of vertices u, v, u ź v. We first give a simple polynomial-time algorithm to check whether a given temporal graph is temporally connected. We then consider the case in which a designer of temporal graphs can freely choose availability instances for all edges and aims for temporal connectivity with very small cost; the cost is the total number of availability instances used. We achieve this via a simple polynomial-time procedure which derives designs of cost linear in n. We also show that the above procedure is (almost) optimal when the underlying graph is a tree, by proving a lower bound on the cost for any tree. However, there are pragmatic cases where one is not free to design a temporally connected graph anew, but is instead given a temporal graph design with the claim that it is temporally connected, and wishes to make it more cost-efficient by removing labels without destroying temporal connectivity (redundant labels). Our main technical result is that computing the maximum number of redundant labels is APX-hard, i.e., there is no PTAS unless P = NP. On the positive side, we show that in dense graphs with random edge availabilities, there is asymptotically almost surely a very large number of redundant labels. A temporal design may, however, be minimal, i.e., no redundant labels exist. We show the existence of minimal temporal designs with at least nlogn labels. Abstract We investigate for temporal graphs the computational complexity of separating two distinct vertices s and z by vertex deletion. In a temporal graph, the vertex set is fixed but the edges have (discrete) time labels. Since the corresponding Temporal ( s , z ) -Separation problem is NP -complete, it is natural to investigate whether relevant special cases exist that are computationally tractable. To this end, we study restrictions of the underlying (static) graph—there we observe polynomial-time solvability in the case of bounded treewidth—as well as restrictions concerning the “temporal evolution” along the time steps. Systematically studying partially novel concepts in this direction, we identify sharp borders between tractable and intractable cases. Temporal graphs are graphs with time-stamped edges. We study the problem of finding a small vertex set (the separator) with respect to two designated terminal vertices such that the removal of the set eliminates all temporal paths connecting one terminal to the other. Herein, we consider two models of temporal paths: paths that pass through arbitrarily many edges per time step (non-strict) and paths that pass through at most one edge per time step (strict). Regarding the number of time steps of a temporal graph, we show a complexity dichotomy (NP-hardness versus polynomial-time solvability) for both problem variants. Moreover we prove both problem variants to be NP-complete even on temporal graphs whose underlying graph is planar. We further show that, on temporal graphs with planar underlying graph, if additionally the number of time steps is constant, then the problem variant for strict paths is solvable in quasi-linear time. Finally, we introduce and motivate the notion of a temporal core (vertices whose incident edges change over time). We prove that the non-strict variant is fixed-parameter tractable when parameterized by the size of the temporal core, while the strict variant remains NP-complete, even for constant-size temporal cores. In this work we consider temporal networks, i.e. networks defined by a labeling ( ) assigning to each edge of an underlying graphG a set of discrete time-labels. The labels of an edge, which are natural numbers, indicate the discrete time moments at which the edge is available. We focus on path problems of temporal networks. In particular, we consider time-respecting paths, i.e. paths whose edges are assigned by ( ) a strictly increasing sequence of labels. We begin by giving two efficient algorithms for computing shortest time-respecting paths on a temporal network. We then prove that there is a natural analogue of Menger’s theorem holding for arbitrary temporal networks. Finally, we propose two cost minimization parameters for temporal network design. One is the temporality of G, in which the goal is to minimize the maximum number of labels of an edge, and the other is the temporal cost of G, in which the goal is to minimize the total number of labels used. Optimization of these parameters is performed subject to some connectivity constraint. We prove several lower and upper bounds for the temporality and the temporal cost of some very basic graph families such as rings, directed acyclic graphs, and trees.