Description
Date depot: 4 avril 2024
Titre: Routing and connectivity problems in temporal graphs
Directeur de thèse:
Bruno ESCOFFIER (LIP6)
Domaine scientifique: Sciences et technologies de l'information et de la communication
Thématique CNRS : Algorithmique, combinatoire
Resumé: Temporal graphs are a generalization of classical (static) graphs where the edge set evolves over time. Formally, in a temporal graph we are given a vertex set V , an edge set E, and a function λ : E → 2^N. λ(u, v) denotes the time steps where the edge (u, v) is present in the graph. Real-life examples of temporal graphs include public transport networks, where a train between two cities has a given departure and arrival time. Studying the spread of a rumor or a virus can also be seen as an exploration problem in temporal graphs where people meet each other over the course of a day. These concepts also apply in drone fleet management among many other fields.
Determining to what extend classical notions and algorithms in (static) graphs generalize to temporal graphs is a wide research topic that received an increasing interest in the recent years, see for instance the annual international conference SAND. The topic of the proposed PhD thesis focuses on questions related to connectivity and routing in temporal graphs. While this notion is well understood in static graphs, several questions re-
main unsolved in temporal graphs.
An interesting example is the notion of spanners in temporal graphs, which generalizes to temporal graphs the classical notion of spanning trees in static graphs. In static graphs, spanning trees (ie., inclusion-minimal connected subgraphs of a given graph) all have the same number of edges, and finding a minimum weight spanning tree is known to be easily solvable by classical algorithms such as Kruskal’s algorithm. In temporal graph, the same property does not hold: not all inclusion-minimal connected subgraphs (spanners) have the same number of edges, and finding one of minimum size is a challenging and very active problem. Contributing to this field is one of the goal of this thesis.
The problem of minimal spanners is to remove as many edges as possible to a connected graph without disconnecting it, but we are also interested in a complementary approach which is to start from a non-connected graph and to find a way to connect it while adding as few edges as possible. While spanners have been extensively studied, this second problem is yet unexplored and offers many interesting perspectives that will be explored in this thesis. Several variants of this problem can be studied: one can try to make the graph connected by adding new edges between vertices that were not connected before, or by only adding new labels to already existing edges, or by modifying their labels (for example, can we improve a transit network by changing the time of a train? where should we build a new line?)
Several other problems related to the aforementioned ones have also been studied, such as exploration or flows in temporal graphs. Other natural
extensions of connectivity would be to try to keep the distances in the graph as small as possible, which has already studied in spanning trees under the name “stretch”, to incorporate the notion of time windows, that strengthens connectivity conditions, or to study the robustness of the connectivity, which has also been extensively studied in the static case but appears to be very different in temporal graphs. Beyond
this, many routing and network design problems, extensively studied in static graphs, remain largely unexplored in temporal graphs. All these topics would greatly benefit from a better understanding of the connectivity of temporal graphs.
In this thesis, these problems will be studied mainly through the lens of computational complexity, fixed-parameter tractability and approximation algorithms, towards the goal of designing and analysing efficient algorithms to solve them.