PhD thesis on temporal graphs (additional information)

Hello
the LITIS Laboratory in Le Havre, Normandy, France, proposes a funded 
PhD thesis on exploring temporal graphs, with a co-supervision with 
Patras university (Greece).  More details below. Please broadcast this 
information to any interested student.

Best regards
Eric

*Project title: Exploration of temporal graphs. Application to logistics 
networks.*


Host institution: ULHN University of Le Havre Normandy, France

Laboratory : LITIS UR 4108

Starting date: september or october 2026


A temporal graph [1] is a graph with n vertices whose set of edges 
evolves over time. This evolution may be entirely known, or not. In the 
latter case, we refer to it as a dynamic graph. If this evolution can be 
represented using a probabilistic model, it is similar to random graphs 
(an edge is present with a certain probability). If we do not have such 
a model, we refer to it as an online problem. A temporal or dynamic 
graph can be represented as a sequence of static graphs with the same 
vertices; these graphs are called snapshots. Finally, the static graph 
containing all the edges present during the lifetime of the graph is 
called the underlying graph.

When modeling transportation networks, an edge is often associated with 
a travel time or transportation time. For example, an edge representing 
a shipping line will be associated with a duration measured in days at 
sea. The same applies to road transport, information transport, etc. It 
should be noted here that the most fundamental works on temporal graphs 
generally assume a unit travel time. Sometimes, on the contrary, travel 
time is neglected in relation to the dynamics of network evolution 
(transport, generally of information or energy, is much faster than the 
speed of network evolution). These different assumptions have 
consequences for the generalization of path in a temporal setting.Such a 
pathis referred to as a journey(or temporal path). It is a sequence of 
edges associated with increasing start dates for the crossing, which 
must comply with the presence of the edges and their travel times. If 
there are journeysbetween any pair of vertices during the lifetime of 
the graph, we say that it is temporally connected. If each snapshot is 
connected, we say that the graph is constantlyoralways-connected. Using 
these two concepts, one can defineconnected components, either temporal 
or instantaneous. We have studied these two types of components (and 
their many variants). Interestingly, determining temporally connected 
components is very often NP-hard even for unit traversal times [2], 
while determining instantaneously connected components is polynomial [3].

A related problem is that of exploring a temporal or dynamic graph. An 
exploration is a temporal path which visits each vertex of the graph at 
least once. For a fixed lifetime, the graph may be temporally connected 
without being explorable. The literature on this subject is fairly 
recent but is growing rapidly. The graphs generally studied in the 
literature are constantly connected, with unit traversal times. There 
are two fairly natural questions. The first is the existence of such a 
path for a given lifetime, and conversely, the minimum lifetime (number 
of time steps) required to find such a path. The second is what is the 
minimum number of edges that must be traversed by such a path. There are 
many results on the first question, see for example [4], but much less 
on the second, which is the subject of Antoine Toullalan's thesis, 
scheduled to be defended in 2026 [5]. We know that for any underlying 
graph, O(n²) time steps are sufficient (and sometimes necessary) to 
explore a temporal graph. The main result of Antoine Toullalan's thesis 
is that O(n^1.5 ) edge traversals are sufficient. However, we do not 
have any example with more than a linear number of edge traversals, 
whereas for several classes of graphs this number is linear in n. Our 
conjecture is that 2n-3 edge traversals are always sufficient, given 
O(n²) time steps.

Our objectives are to continue the work of A. Toullalan's thesis in 
three directions, in order to obtain results on models that are closer 
to the reality of actual logistics networks.

1) Still in the case of a single time unit for traversing edges and 
known evolution, study this conjecture by considering new classes of 
graphs.

2) Consider dynamic graphs, based on random graph models [6,7,8]. There 
are still few studies, and all focus on the existence of explorations 
depending on the lifetime of the graph, as in [4]. We wish to study the 
problem of the minimum number of edges to cross in this context.

3) Variable traversal times. There is still nothing in the literature on 
exploration in this context. It is certainly possible to use the 
well-known model of expended graphs, but this will lead to highly 
complex algorithms. Are other approaches possible?

4) It is of course possible to combine random graphs and arbitrary 
traversal times, and we would like to obtain results in this general 
framework.


*Bibliograph**y *

[1] Holme, P. (2015). Modern temporal network theory: a colloquium./The 
European Physical Journal B/88 (9), 234.

[2] *Balev, S.*, *Sanlaville, E.*, & Schoeters, J. (2024). Temporally 
connected components. /Theoretical Computer Science/, /1013/, 114757.

*[3] **_M. _**_Vernet,_****_Y. Pigné_**, ***E. Sanlaville***(2022) A 
study of connectivity on dynamic graphs: computing persistent connected 
components. 4OR-Q J Oper Res. *

[4] Erlebach, T., Hoffmann, M., and Kammer, F. "On temporal graph 
exploration." /Journal of Computer and System Sciences/119 (2021): 1-18.

[5] *Balev, S.*, *Sanlaville, É.*, & _Toullalan, A._(2025). Brief 
Announcement: The Shortest Temporal Exploration Problem. In /4th 
Symposium on Algorithmic Foundations of Dynamic Networks (SAND 
2025)/(pp. 18-1). Schloss Dagstuhl–Leibniz-Zentrum für Informatik.

[6] Casteigts, A., Raskin, M., Renken, M., & Zamaraev, V. (2024). Sharp 
thresholds in random simple temporal graphs. /SIAM Journal on 
Computing/, /53/(2), 346-388.

[7] *Nikoletseas, S.*, *Raptopoulos, C.*, & Spirakis, P. (2023). Max cut 
in weighted random intersection graphs and discrepancy of sparse random 
set systems. /Algorithmica/, /85/(9), 2817-2842.

[8] Mertzios, G. B., *Nikoletseas, S.*, *Raptopoulos, C.*, & Spirakis, 
P. G. (2024). Brief Announcement: On the existence of δ-temporal cliques 
in random simple temporal graphs. SAND2024. /Leibniz International 
Proceedings in Informatics, LIPIcs/, /292/.

[9] Akrida, E C, Mertzios, G B, Spirakis, P G,and *Raptopoulos, C. *"The 
temporal explorer who returns to the base." /Journal of Computer and 
System Sciences/120 (2021): 179-193.

[10] Baguley, S., Göbel, A., Klodt, N., Skretas, G., Sylvester, J., 
Zamaraev,V.,Temporal Exploration of Random Spanning Tree 
Models.Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete 
Algorithms (SODA).[11] Projet ANR TEMPOGRAL (Problèmes algorithmiques 
sur les graphes temporels), *Eric Sanlaville*porteur. 
labri.fr/perso/acasteig/tempogral/


Thesis supervision


The PhD student will be registered at Le Havre University. However, the 
recruited person will be co-supervised by Eric Sanlaville and Stefan 
Balev from Le Havre, and Sotiris Nikoletseas and Christoforos 
Raptopoulos from Patras University (Greece). He/she will do several 
sojourns to Patras.

Candidate profile : The candidates must have a master degree or 
equivalent in computer science or applied mathematics, with a strong 
background in algorithmics and graph theory. English langage proficiency 
is needed, French and Greek would be appreciated but are not mandatory.

To candidate, please provide a CV, short motivation letter and master 
marks to  the supervisors:

[email protected], [email protected], 
[email protected], [email protected]

(The complete application is due by April 29)



-- 
Eric Sanlaville
co-directeur LITIS
Professeur d'Informatique
Université Le Havre Normandie

**********************************************************
*
*   Contributions to be spread via DMANET are submitted to
*
*                   [email protected]
*
*   Replies to a  message carried  on DMANET should NOT be
*   addressed to DMANET  but to  the original sender.  The
*   original  sender,  however,  is invited  to prepare an
*   update  of the replies  received and to communicate it
*   via DMANET.
*
*    DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET)
*      http://www.zaik.uni-koeln.de/AFS/publications/dmanet/
*
**********************************************************