Author name cluster

Arnaud Casteigts

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

5 papers

2 author rows

MFCS Conference 2024 Conference Paper

Distance to Transitivity: New Parameters for Taming Reachability in Temporal Graphs

Arnaud Casteigts
Nils Morawietz
Petra Wolf 0002

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 𝒢 is from being transitive, namely, vertex-deletion distance to transitivity and arc-modification distance to transitivity, both being applied to the reachability graph of 𝒢. 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.

Details

TCS Journal 2024 Journal Article

Simple, strict, proper, happy: A study of reachability in temporal graphs

Arnaud Casteigts
Timothée Corsini
Writika Sarkar

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.

Details DOI

FOCS Conference 2021 Conference Paper

Sharp Thresholds in Random Simple Temporal Graphs

Arnaud Casteigts
Michael Raskin
Malte Renken
Viktor Zamaraev

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.

Details

TCS Journal 2020 Journal Article

Robustness: A new form of heredity motivated by dynamic networks

Arnaud Casteigts
Swan Dubois
Franck Petit
John M. Robson

We investigate a special case of hereditary property in graphs, referred to as robustness. A property (or structure) is called robust in a graph G if it is inherited by all the connected spanning subgraphs of G. We motivate this definition using two different settings of dynamic networks. The first corresponds to networks of low dynamicity, where some links may be permanently removed so long as the network remains connected. The second corresponds to highly-dynamic networks, where communication links appear and disappear arbitrarily often, subject only to the requirement that the entities are temporally connected in a recurrent fashion (i. e. they can always reach each other through temporal paths). Each context induces a different interpretation of the notion of robustness. We start by motivating the definition and discussing the two interpretations, after what we consider the notion independently from its interpretation, taking as our focus the robustness of maximal independent sets (MIS). A graph may or may not admit a robust MIS. We characterize the set of graphs RMI S ∀ in which all MISs are robust. Then, we turn our attention to the graphs that admit a robust MIS ( RMI S ∃ ). This class has a more complex structure; we give a partial characterization in terms of elementary graph properties, then a complete characterization by means of a (polynomial time) decision algorithm that accepts if and only if a robust MIS exists. This algorithm can be adapted to construct such a solution if one exists.

Details DOI

TCS Journal 2015 Journal Article

On the expressivity of time-varying graphs

Arnaud Casteigts
Paola Flocchini
Emmanuel Godard
Nicola Santoro
Masafumi Yamashita

In highly dynamic systems (such as wireless mobile ad hoc networks, robotic swarms, vehicular networks, etc.) connectivity does not necessarily hold at a given time but temporal paths, or journeys, may still exist over time and space, rendering computing possible; some of these systems allow waiting (i. e. , pauses at intermediate nodes, also referred to as store-carry-forward strategies) while others do not. These systems are naturally modeled as time-varying graphs, where the presence of an edge and its latency vary as a function of time; in these graphs, the distinction between waiting and not waiting corresponds to the one between indirect and direct journeys. We consider the expressivity of time-varying graphs, in terms of the languages generated by the feasible journeys. We examine the impact of waiting by studying the difference in the type of language expressed by indirect journeys (i. e. , waiting is allowed) and by direct journeys (i. e. , waiting is unfeasible), under various assumptions on the functions that control the presence and latency of edges. We prove a general result which implies that, if waiting is not allowed, then the set of languages L nowait that can be generated contains all computable languages when the presence and latency functions are computable. On the other end, we prove that, if waiting is allowed, then the set of languages L wait contains all and only regular languages; this result, established using algebraic properties of quasi-orders, holds even if the presence and latency are unrestricted (e. g. , possibly non-computable) functions of time. In other words, we prove that, when waiting is allowed, the power of the accepting automaton can drop drastically from being at least as powerful as a Turing machine, to becoming that of a Finite-State Machine. This large gap provides an insight on the impact of waiting in time-varying graphs. We also study bounded waiting, in which waiting is allowed at a node for at most d time units, and prove that L wait [ d ] = L nowait; that is, the power of the accepting automaton decreases only if waiting time is unbounded.

Details DOI