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.
Restriction of the problem. If the labels are not required to be locally unique and the journeys are required to be strictly increasing, then Kempe @cite_17 show that any graph (even complete) could be made unsimplifiable by assigning to every edge the same label and thereby rendering multi-hop journeys unfeasible. This problem disappears if either non-decreasing journeys are allowed, or if @math is restricted to be (say) locally injective, which is what the various works in the literature have been doing since then. In this setting, the question of whether sparse spanners always exist remained open for more than a decade.
@cite_17
2086991377
Many network problems are based on fundamental relationships involving time. Consider, for example, the problems of modeling the flow of information through a distributed network, studying the spread of a disease through a population, or analyzing the reachability properties of an airline timetable. In such settings, a natural model is that of a graph in which each edge is annotated with a time label specifying the time at which its endpoints "communicated." We will call such a graph a temporal network. To model the notion that information in such a network "flows" only on paths whose labels respect the ordering of time, we call a path time-respecting if the time labels on its edges are non-decreasing. The central motivation for our work is the following question: how do the basic combinatorial and algorithmic properties of graphs change when we impose this additional temporal condition? The notion of a path is intrinsic to many of the most fundamental algorithmic problems on graphs; spanning trees, connectivity, flows, and cuts are some examples. When we focus on time-respecting paths in place of arbitrary paths, many of these problems acquire a character that is different from the traditional setting, but very rich in its own right. We provide results on two types of problems for temporal networks. First, we consider connectivity problems, in which we seek disjoint time-respecting paths between pairs of nodes. The natural analogue of Menger's Theorem for node-disjoint paths fails in general for time-respecting paths; we give a non-trivial characterization of those graphs for which the theorem does hold in terms of an excluded subdivision theorem, and provide a polynomial-time algorithm for connectivity on this class of graphs. (The problem on general graphs is NP-complete.) We then define and study the class of inference problems, in which we seek to reconstruct a partially specified time labeling of a network in a manner consistent with an observed history of information flow.