Abstract. A temporal graph is a graph whose edges appear only at certain points in time. Recently, the second and the last three authors proposed a natural temporal analog of the Erdős–Rényi random graph model. The proposed model is obtained by randomly permuting the edges of an Erdős–Rényi random graph and interpreting this permutation as an ordering of presence times. It was shown that the connectivity threshold in the Erdős–Rényi model fans out into multiple phase transitions for several distinct notions of reachability in the temporal setting. In the present paper, we identify a sharp threshold for the emergence of a giant temporally connected component. We show that at [Formula: see text] the size of the largest temporally connected component increases from [Formula: see text] to [Formula: see text]. This threshold holds for both open and closed connected components, i.e., components that allow (respectively, forbid) their connecting paths to use external nodes.

Given an undirected graph G, the problem of deciding whether G admits a simple and proper time-labeling that makes it temporally connected is known to be NP-hard (Göbel et al., 1991). In this article, we relax this problem and ask whether a given degree sequence can be realized as a temporally connected graph. Our main results are a complete characterization of the feasible cases, and a recognition algorithm that runs in 𝒪(n) time for graphical degree sequences (realized as simple temporal graphs) and in 𝒪(n+m) time for multigraphical degree sequences (realized as non-simple temporal graphs, where the number of time labels on an edge corresponds to the multiplicity of the edge in the multigraph). In fact, these algorithms can be made constructive at essentially no cost. Namely, we give a constructive 𝒪(n+m) time algorithm that outputs, for a given (multi)graphical degree sequence 𝐝, a temporally connected graph whose underlying (multi)graph is a realization of 𝐝, if one exists.

We study a new version of the Euclidean TSP called VectorTSP (VTSP for short) where a mobile entity is allowed to move according to a set of physical constraints inspired from the pen-and-pencil game Racetrack (also known as Vector Racer ). In contrast to other versions of TSP accounting for physical constraints, such as Dubins TSP, the spirit of this model is that (1) no speed limitations apply, and (2) inertia depends on the current velocity. As such, this model is closer to typical models considered in path planning problems, although applied here to the visit of n cities in a non-predetermined order. We motivate and introduce the VectorTSP problem, discussing fundamental differences with previous versions of TSP. In particular, an optimal visit order for ETSP may not be optimal for VTSP. We show that VectorTSP is NP-hard, and in the other direction, that VectorTSP reduces to GroupTSP in polynomial time (although with a significant blow-up in size). On the algorithmic side, we formulate the search for a solution as an interactive scheme between a high-level algorithm and a trajectory oracle, the former being responsible for computing the visit order and the latter for computing the cost (or the trajectory) for a given visit order. We present algorithms for both, and we demonstrate and quantify through experiments that this approach frequently finds a better solution than the optimal trajectory realizing an optimal ETSP tour, which legitimates the problem itself and (we hope) motivates further algorithmic developments.

A temporal graph is a graph whose edges only appear at certain points in time. Reachability in these graphs is defined in terms of paths that traverse the edges in chronological order (temporal paths). This form of reachability is neither symmetric nor transitive, the latter having important consequences on the computational complexity of even basic questions, such as computing temporal connected components. In this paper, we introduce several parameters that capture how far a temporal graph $\mathcal{G}$ is from being transitive, namely, \emph{vertex-deletion distance to transitivity} and \emph{arc-modification distance to transitivity}, both being applied to the reachability graph of $\mathcal{G}$. We illustrate the impact of these parameters on the temporal connected component problem, obtaining several tractability results in terms of fixed-parameter tractability and polynomial kernels. Significantly, these results are obtained without restrictions of the underlying graph, the snapshots, or the lifetime of the input graph. As such, our results isolate the impact of non-transitivity and confirm the key role that it plays in the hardness of temporal graph problems.

The Freeze-Tag Problem, introduced in Arkin et al. (SODA'02) consists of waking up a swarm of n robots, starting from a single active robot. In the basic geometric version, every robot is given coordinates in the plane. As soon as a robot is awakened, it can move towards inactive robots to wake them up. The goal is to minimize the makespan of the last robot, the makespan. Despite significant progress on the computational complexity of this problem and on approximation algorithms, the characterization of exact bounds on the makespan remains one of the main open questions. In this paper, we settle this question for the 𝓁₁-norm, showing that a makespan of at most 5r can always be achieved, where r is the maximum distance between the initial active robot and any sleeping robot. Moreover, a schedule achieving a makespan of at most 5r can be computed in time O(n). Both bounds, the time and the makespan are optimal. Our results also imply for the 𝓁₂-norm a new upper bound of 5√2r ≈ 7.07r on the makespan, improving the best known bound of (5+2√2+√5)r ≈ 10.06r. Along the way, we introduce new linear time wake-up strategies, that apply to any norm and show that an optimal bound on the makespan can always be achieved by a schedule computable in linear time.

Abstract. A graph whose edges only appear at certain points in time is called a temporal graph (among other names). Such a graph is temporally connected if each ordered pair of vertices is connected by a path which traverses edges in chronological order (i.e., a temporal path). In this paper, we consider a simple model of random temporal graph, obtained from an Erdős–Rényi random graph, [Formula: see text], by considering a random permutation [Formula: see text] of the edges and interpreting the ranks in [Formula: see text] as presence times. We give a thorough study of the temporal connectivity of such graphs and derive implications for the existence of several kinds of sparse spanners. It turns out that temporal reachability in this model exhibits a surprisingly regular sequence of thresholds. In particular, we show that at [Formula: see text], any fixed pair of vertices can asymptotically almost surely (a.a.s.) reach each other; at [Formula: see text], at least one vertex (and, in fact, any fixed vertex) can a.a.s. reach all others; and at [Formula: see text], all the vertices can a.a.s. reach each other; i.e., the graph is temporally connected. Furthermore, the graph admits a temporal spanner of size [Formula: see text] as soon as it becomes temporally connected, which is nearly optimal, as [Formula: see text] is a lower bound. This result is quite significant because temporal graphs do not admit spanners of size [Formula: see text] in general [Kempe, Kleinberg, and Kumar, J. Comput. System Sci., 64 (2002), pp. 820–842]. In fact, they do not even always admit spanners of size [Formula: see text] [Axiotis and Fotakis, On the size and the approximability of minimum temporally connected subgraphs, 2016, pp. 149:1–149:14]. Thus, our result implies that the obstructions found in these works—and more generally any non-negligible obstruction—are statistically insignificant: nearly optimal spanners always exist in random temporal graphs. All the above thresholds are sharp. Carrying the study of temporal spanners a step further, we show that pivotal spanners—i.e., spanners of size [Formula: see text] composed of two spanning trees glued at a single vertex (one descending in time, the other ascending subsequently)—exist a.a.s. at [Formula: see text], this threshold being also sharp. Finally, we show that optimal spanners (of size [Formula: see text]) also exist a.a.s. at [Formula: see text]. Whether this value is a sharp threshold is open; we conjecture that it is. For completeness, we compare the above results to existing results in related areas, including edge-ordered graphs, gossip theory, and population protocols, showing that our results can be interpreted in these settings as well and that in some cases they improve known results therein. Finally, we discuss an intriguing connection between our results and Janson’s celebrated results on percolation in weighted graphs.

Dynamic networks are a complex subject. Not only do they inherit the complexity of static networks (as a particular case); they are also sensitive to definitional subtleties that are a frequent source of confusion and incomparability of results in the literature. In this paper, we take a step back and examine three such aspects in more details, exploring their impact in a systematic way; namely, whether the temporal paths are required to be strict (i.e., the times along a path must increasing, not just be non-decreasing), whether the time labeling is proper (two adjacent edges cannot be present at the same time) and whether the time labeling is simple (an edge can have only one presence time). In particular, we investigate how different combinations of these features impact the expressivity of the graph in terms of reachability. Our results imply a hierarchy of expressivity for the resulting settings, shedding light on the loss of generality that one is making when considering either combination. Some settings are more general than expected; in particular, proper temporal graphs turn out to be as expressive as general temporal graphs where non-strict paths are allowed. Also, we show that the simplest setting, that of happy temporal graphs (i.e., both proper and simple) remains expressive enough to emulate the reachability of general temporal graphs in a certain (restricted but useful) sense. Furthermore, this setting is advocated as a target of choice for proving negative results. We illustrate this by strengthening two known results to happy graphs (namely, the inexistence of sparse spanners, and the hardness of computing temporal components). Overall, we hope that this article can be seen as a guide for choosing between different settings of temporal graphs, while being aware of the way these choices affect generality.

A graph whose edges only appear at certain points in time is called a temporal graph (among other names). Such a graph is temporally connected if each ordered pair of vertices is connected by a path which traverses edges in chronological order (i.e., a temporal path). In this paper, we consider a simple model of random temporal graph, obtained from an Erdös-Rényi random graph G ~ Gn,p by considering a random permutation π of the edges and interpreting the ranks in π as presence times. We give a thorough study of the temporal connectivity of such graphs and derive implications for the existence of several kinds of sparse spanners. It turns out that temporal reachability in this model exhibits a surprisingly regular sequence of thresholds. In particular, we show that, at p = log$n$/n, any fixed pair of vertices can a.a.s. reach each other; at 2 log$n$/n, at least one vertex (and in fact, any fixed vertex) can a.a.s. reach all others; and at 3 log$n$/n, all the vertices can a.a.s. reach each other, i.e., the graph is temporally connected. Furthermore, the graph admits a temporal spanner of size 2n + o(n) as soon as it becomes temporally connected, which is nearly optimal as 2n - 4 is a lower bound. This result is quite significant because temporal graphs do not admit spanners of size O(n) in general (Kempe, Kleinberg, Kumar, STOC 2000). In fact, they do not even always admit spanners of size o($n$2) (Axiotis, Fotakis, ICALP 2016). Thus, our result implies that the obstructions found in these works, and more generally, any non-negligible obstruction is statistically insignificant: nearly optimal spanners always exist in random temporal graphs. All the above thresholds are sharp. Carrying the study of temporal spanners a step further, we show that pivotal spanners-i.e., spanners of size 2n - 2 made of two spanning trees glued at a single vertex (one descending in time, the other ascending subsequently)-exist a.a.s. at 4 log$n$/ n, this threshold being also sharp. Finally, we show that optimal spanners (of size 2n - 4) also exist a.a.s. at p = 4 log$n$/n, Whether this value is a sharp threshold is open, we conjecture that it is. For completeness, we compare the above results to existing results in related areas, including edge-ordered graphs, gossip theory, and population protocols, showing that our results can be interpreted in these settings as well, and that in some cases, they improve known results therein. Finally, we discuss an intriguing connection between our results and Janson's celebrated results on percolation in weighted graphs.

Abstract Computing a (short) path between two vertices is one of the most fundamental primitives in graph algorithmics. In recent years, the study of paths in temporal graphs, that is, graphs where the vertex set is fixed but the edge set changes over time, gained more and more attention. A path is time-respecting, or temporal , if it uses edges with non-decreasing time stamps. We investigate a basic constraint for temporal paths, where the time spent at each vertex must not exceed a given duration $$\varDelta $$ Δ , referred to as $$\varDelta $$ Δ - restless temporal paths . This constraint arises naturally in the modeling of real-world processes like packet routing in communication networks and infection transmission routes of diseases where recovery confers lasting resistance. While finding temporal paths without waiting time restrictions is known to be doable in polynomial time, we show that the “restless variant” of this problem becomes computationally hard even in very restrictive settings. For example, it is W[1]-hard when parameterized by the distance to disjoint path of the underlying graph, which implies W[1]-hardness for many other parameters like feedback vertex number and pathwidth. A natural question is thus whether the problem becomes tractable in some natural settings. We explore several natural parameterizations, presenting FPT algorithms for three kinds of parameters: (1) output-related parameters (here, the maximum length of the path), (2) classical parameters applied to the underlying graph (e.g., feedback edge number), and (3) a new parameter called timed feedback vertex number , which captures finer-grained temporal features of the input temporal graph, and which may be of interest beyond this work.

Let G=(V,E) be an undirected graph on n vertices and λ:E→2N a mapping that assigns to every edge a non-empty set of integer labels (discrete times when the edge is present). Such a labelled graph G=(G,λ) is temporally connected if a path exists with non-decreasing times from every vertex to every other vertex. In a seminal paper, Kempe, Kleinberg, and Kumar [17] asked whether, given such a temporally connected graph, a sparse subset of edges always exists whose labels suffice to preserve temporal connectivity – a temporal spanner. Axiotis and Fotakis [5] answered negatively by exhibiting a family of Θ(n2)-dense temporal graphs which admit no temporal spanner of density o(n2). In this paper, we give the first positive answer as to the existence of o(n2)-sparse spanners in a dense class of temporal graphs, by showing (constructively) that if G is a complete graph, then one can always find a temporal spanner with O(nlog⁡n) edges.

Computing a (short) path between two vertices is one of the most fundamental primitives in graph algorithmics. In recent years, the study of paths in temporal graphs, that is, graphs where the vertex set is fixed but the edge set changes over time, gained more and more attention. A path is time-respecting, or temporal, if it uses edges with non-decreasing time stamps. We investigate a basic constraint for temporal paths, where the time spent at each vertex must not exceed a given duration Δ, referred to as Δ-restless temporal paths. This constraint arises naturally in the modeling of real-world processes like packet routing in communication networks and infection transmission routes of diseases where recovery confers lasting resistance. While finding temporal paths without waiting time restrictions is known to be doable in polynomial time, we show that the "restless variant" of this problem becomes computationally hard even in very restrictive settings. For example, it is W[1]-hard when parameterized by the feedback vertex number or the pathwidth of the underlying graph. The main question thus is whether the problem becomes tractable in some natural settings. We explore several natural parameterizations, presenting FPT algorithms for three kinds of parameters: (1) output-related parameters (here, the maximum length of the path), (2) classical parameters applied to the underlying graph (e.g., feedback edge number), and (3) a new parameter called timed feedback vertex number, which captures finer-grained temporal features of the input temporal graph, and which may be of interest beyond this work.

Highly dynamic networks are characterized by frequent changes in the availability of communication links. These networks are often partitioned into several components, which split and merge unpredictably. We present a distributed algorithm that maintains a forest of (as few as possible) spanning trees in such a network, with no restriction on the rate of change. Our algorithm is inspired by high-level graph transformations, which we adapt here in a (synchronous) message passing model for dynamic networks. The resulting algorithm has the following properties. First, every decision is purely local—in each round, a node only considers its role and that of its neighbors in the tree, with no further information propagation (in particular, no wave mechanisms). Second, whatever the rate and scale of the changes, the algorithm guarantees that, by the end of every round, the network is covered by a forest of spanning trees in which (1) no cycle occur, (2) every node belongs to exactly one tree and (3) every tree contains exactly one root. We primarily focus on the correctness of this algorithm, which is established rigorously. While performance is not the main focus, we suggest new complexity metrics for such problems, and report on preliminary experimentation results validating our algorithm in a practical scenario.

We consider networks of processes which interact with beeps. In the basic model defined by Cornejo and Kuhn, which we refer to as the BL variant, processes can choose in each round either to beep or to listen. Those who beep are unable to detect simultaneous beeps. Those who listen can only distinguish between silence and the presence of at least one beep. Stronger variants exist where the nodes can also detect collision while they are beeping (B_{cd}L) or listening (BL_{cd}), or both (B_{cd}L_{cd}). Beeping models are weak in essence and even simple tasks are difficult or unfeasible with them. This paper starts with a discussion on generic building blocks (design patterns) which seem to occur frequently in the design of beeping algorithms. They include multi-slot phases: the fact of dividing the main loop into a number of specialised slots; exclusive beeps: having a single node beep at a time in a neighbourhood (within one or two hops); adaptive probability: increasing or decreasing the probability of beeping to produce more exclusive beeps; internal (resp. peripheral) collision detection: for detecting collision while beeping (resp. listening); and emulation of collision detection: for enabling this feature when it is not available as a primitive. We then provide algorithms for a number of basic problems, including colouring, 2-hop colouring, degree computation, 2-hop MIS, and collision detection (in BL). Using the patterns, we formulate these algorithms in a rather concise and elegant way. Their analyses (in the full version) are more technical, e.g. one of them relies on a Martingale technique with non-independent variables; another improves that of the MIS algorithm (P. Jeavons et al.) by getting rid of a gigantic constant (the asymptotic order was already optimal). Finally, we study the relative power of several variants of beeping models. In particular, we explain how every Las Vegas algorithm with collision detection can be converted, through emulation, into a Monte Carlo algorithm without, at the cost of a logarithmic slowdown. We prove that this slowdown is optimal up to a constant factor by giving a matching lower bound.

Delay-tolerant networks (DTNs) are characterized by a possible absence of end-to-end communication routes at any instant. Yet, connectivity can be achieved over time and space, leading to evaluate a given route both in terms of topological length or temporal length. The problem of measuring temporal distances in a social network was recently addressed through postprocessing contact traces like email data sets, in which all contacts are punctual in time (i.e., they have no duration). We focus on the distributed version of this problem and address the more general case that contacts can have arbitrary durations (i.e., be nonpunctual). Precisely, we ask whether each node in a network can track in real time how "out-of-dateâ it is with respect to every other. Although relatively straightforward with punctual contacts, this problem is substantially more complex with arbitrarily long contacts: consecutive hops of an optimal route may either be disconnected (intermittent connectedness of DTNs) or connected (i.e., the presence of links overlaps in time, implying a continuum of path opportunities). The problem is further complicated (and yet, more realistic) by the fact that we address continuous-time systems and nonnegligible message latencies (time to propagate a single message over a single link); however, this latency is assumed fixed and known. We demonstrate the problem is solvable in this general context by generalizing a time-measurement vector clock construct to the case of "nonpunctualâ causality, which results in a tool we call T-Clocks, of independent interest. The remainder of the paper shows how T-Clocks can be leveraged to solve concrete problems such as learning foremost broadcast trees (BTs), network backbones, or fastest broadcast trees in periodic DTNs.

We introduce a new time-efficient Bluetooth Scatternet Formation (BSF) algorithm, called BSF-UED (Unnecessary-Edges Deletion). BSF-UED forms connected scatternets deterministically. Heuristics are added to make these scatternets outdegree limited (that is, with no more than 7 slaves per piconet). The performance of the algorithm is evaluated through a range of simulation experiments. BSF-UED is compared against some of the most common BSF algorithms which are BlueStars, BlueMIS I, BlueMIS II, and BlueMesh. We show that BSF-UED provides a good balance between the usual scatternets performance metrics, while being time efficient (nearly 1/3 of the execution time of BlueMesh). BlueStars remains a faster algorithm, but with the major flaw of generating scatternets whose piconets have a large number of slaves.

We consider infrastructure-less highly dynamic networks, where connectivity does not necessarily hold, and the network may actually be disconnected at every time instant. These networks are naturally modeled as time-varying graphs. Clearly the task of designing protocols for these networks is less difficult if the environment allows waiting (i.e., it provides the nodes with store-carry-forward-like mechanisms such as local buffering) than if waiting is not feasible. We provide a quantitative corroboration of this fact in terms of the expressivity of the corresponding time-varying graph; that is in terms of the language generated by the feasible journeys in the graph. We prove that the set of languages Lnowait when no waiting is allowed contains all computable languages. On the other end, we prove that Lwait is just the family of regular languages. This gap is a measure of the computational power of waiting. We also study bounded waiting; that is when waiting is allowed at a node only for at most d time units. We prove the negative result that L wait[d] = Lnowait.

Delay-tolerant networks (DTNs) are characterized by a possible absence of end-to-end communication routes at any instant. In most cases, however, a form of connectivity can be established over time and space. This particularity leads to consider the relevance of a given route not only in terms of hops (topological length), but also in terms of time (temporal length). The problem of measuring temporal distances between individuals in a social network was recently addressed, based on a posteriori analysis of interaction traces. This paper focuses on the distributed version of this problem, asking whether every node in a network can know precisely and in real time how out-of-date it is with respect to every other. Answering affirmatively is simple when contacts between the nodes are punctual, using the temporal adaptation of vector clocks provided in (Kossinets et al., 2008). It becomes more difficult when contacts have a duration and can overlap in time with each other. We demonstrate that the problem remains solvable with arbitrarily long contacts and non-instantaneous (though invariant and known) propagation delays on edges. This is done constructively by extending the temporal adaptation of vector clocks to non-punctual causality. The second part of the paper discusses how the knowledge of temporal lags could be used as a building block to solve more concrete problems, such as the construction of foremost broadcast trees or network backbones in periodically-varying DTNs.

Research in population health consists in studying the impact of various factors (determinants) on health, with the longterm objective of yielding better policies, programs, and services. Researchers of Official Language Minority Communities (OLMCs) focus specifically on determinants related to speaking a minority language, such as English in Quebec, or French in the rest of Canada. Investigations of this type require the possibility of associating health data to linguistic information. Unfortunately, the largest health databases in Ontario, held at the Institute for Clinical Evaluative Sciences (ICES), do not contain usable linguistic variables to date. High-quality language variables however exist at Statistics Canada (2006 Census), and we are interested in enabling its linkage to ICES health data in a dynamic way. The linkage we consider is intrinsically transient and aggregated: it consists in allowing ICES to learn interactively how many Francophones are present in a given sample of individuals (sum queries). We suggest two possible privacy-preserving mechanisms to enable dynamic sum queries: 1) by constraining the dataflow itself; 2) by adapting recent results ([1]) to characterize what leakage is at play in our scenario and what parameters impact the tradeoff between leakage and utility. We rely on these results to argue that a safe exposition of linguistic data could indeed be envisioned, and beyond, that similar techniques could be used to enrich provincial health databases in general with a range of federal census data, making it possible to perform fine-grained community-based studies in Canada.

Abstract Vehicular networks are envisioned for large scale deployment, and standardization bodies, car manufacturers, and academic researchers are solving a variety of related challenges. After a brief description of intelligent transportation system (ITS) architectures and the main already‐established low‐level standards, this tutorial elaborates on four particular aspects of vehicular networks, which are (i) the potential for a large set of innovative applications, (ii) a review of the main modeling approaches used for both roads and traffic, and finally two important communication primitives, that are (iii) data disseminationviabroadcasting/geocasting, and (iv) routing in both highway and urban environments. A particular emphasis is on recent protocols that realistically consider the inherently complex nature of vehicular mobility, such as intermittent connectivity, speed variability, and the impact of intersections. Copyright © 2009 John Wiley & Sons, Ltd.

This paper proposes a new solution to the problem of self-deploying a network of wireless mobile robots with simultaneous consideration to several criteria, that are, the fault-tolerance (biconnectivity) of the resulting network, its coverage, its diameter, and the quantity of movement required to complete the deployment. These criteria have already been addressed individually in previous works, but we propose here an elegant solution to address all of them at once. Our approach is based on combining two complementary sets of virtual forces: spring forces, whose properties are well known to provide optimal coverage at reasonable movement cost, and angular forces, a new type of force proposed here whose effect is to rotate two angularly consecutive neighbors toward one another when the corresponding angle is larger than 60° (even if these nodes are not direct neighbors). Angular forces have the global effect of biconnecting the network and reducing its diameter, while not affecting the benefits obtained by spring forces on coverage. In this paper we give a detailed description of the combination of both types of forces. We also provide an implementation relying only on position exchanges within two hops. Simulations results are finally presented to evaluate our solution with respect to the four considered criteria (coverage, biconnectivity, quantity of movements, and diameter), and compare it with prior approaches.