Stage et Thèse : Etude du problème de voyageur de commerce sur un graphe temporel / Study of the tra

Nous proposons un stage de recherche sur les problèmes d'optimisation dans les graphes temporels.

Le candidat cherché, en master 2 ou dernière année d'école d'ingénieur,  a une bonne connaissance des graphes et est familier avec les notions de bases de l'algorithmique et de la recherche opérationnelle. Le stage peut démarrer en février ou mars 2023. Il pourra  se poursuivre par une thèse financée par le projet ANR Tempogral. Une description du sujet en Français et en Anglais est ci-dessous.

We propose a master research internship on optimization problems in temporal graphs. The candidate has good knowledge of graph theory, and is familiar with the basics of Algorithmic and Operations Research. The internship may start in february or march of 2023. It might be followed by a phd thesis, funded by the ANR Tempogral project. A description of the subject is available below.

Contexte : L’équipe RI2C du laboratoire LITIS au Havre travaille depuis des années sur les graphes
temporels dans une optique algorithmique et optimisation. Les graphes temporels (ou dynamiques) sont des
graphes qui évoluent dans le temps (en particulier, les arêtes peuvent apparaître ou disparaître au cours du
temps). L’équipe est partenaire d’un projet financé par l’ANR : Temporal Graph Algorithms (acronyme
TEMPOGRAL, site https://www.labri.fr/perso/acasteig/tempogral/).
Le projet finance en particulier une allocation de thèse et ce stage. Le stagiaire retenu sera donc un candidat
naturel à cette allocation.

Sujet du stage : Nous nous intéressons à l’adaptation de problèmes classiques dans les graphes au contexte
temporel. Le problème du voyageur de commerce (Traveling Salesman Problem, TSP) est l’un des plus
connus de ces problèmes. Dans le contexte temporel, on associe à chaque arête des dates de présence
(étiquettes). Le TSP temporel consiste à construire une suite d’arêtes permettant de passer par tous les
sommets du graphe. La suite d’arêtes forme un cycle, et de plus une solution réalisable associe à chaque
arête une de ses étiquettes, de sorte que la suite des étiquettes obtenues est strictement croissante. Dans une
version « faible » du problème, il est autorisé de passer plusieurs fois par un même sommet (on parle alors
d’exploration temporelle).
On sait que décider si un graphe statique admet un cycle Hamiltonien est déjà un problème NP-Complet. La
variante temporelle est également difficile même sous des hypothèses très restrictives.
Nous nous intéresserons durant le stage à la question suivante : quel est la durée minimale d’une exploration
temporelle (définie comme la valeur de sa plus grande étiquette) ? Plus précisément, on peut montrer avec
quelques hypothèses naturelles sur les étiquettes que cette durée est au maximum de l’ordre de n2. Mais peut-
on toujours trouver une solution dont la durée est au plus de l’ordre de m, nombre d’arêtes du graphe ?
Le stagiaire retenu devra se familiariser avec la notion de graphe temporel. Il étudiera ensuite le TSP
temporel, avant de chercher à répondre à la question ci-dessus. L’étude pourra être complétée par des
expérimentations qui permettront de guider l’analyse théorique.
Bibliographie
O. Michail. An introduction to temporal graphs: An algorithmic perspective. Internet Mathematics,
12(4):239–280, 2016. (état d’art succinct pour temporal exploration and TSP p 29)
O. Michail and P. G. Spirakis. Traveling salesman problems in temporal graphs. In 39th International
Symposium on Mathematical Foundations of Computer Science (MFCS), pages 553–564. Springer, 2014.
Erlebach, T., Hoffmann, M., Kammer, F. (2015). On Temporal Graph Exploration. In: Halldórsson, M.,
Iwama, K., Kobayashi, N., Speckmann, B. (eds) Automata, Languages, and Programming. ICALP 2015.
Lecture Notes in Computer Science(), vol 9134. Springer, Berlin, Heidelberg.
P. Flocchini, B. Mans, and N. Santoro. Exploration of periodically varying graphs. In Y. Dong, D.-Z. Du,
and O. Ibarra, editors, Algorithms and Computation, volume 5878 of Lecture Notes in Computer Science,
pages 534–543. Springer Berlin Heidelberg, 2009.
D. Ilcinkas and A.M. Wade(2018). Exploration of the t-interval-connected dynamic graphs: the case of the
ring. Theory of Computing Systems, 62(5), 1144-1160.

Prérequis : diplôme de Master ou d’Ingénieur en informatique ou mathématiques appliquées. Une bonne
connaissance des graphes est indispensable. Des acquis solides en Algorithmique et en Recherche
Opérationnelle sont un plus.
Encadrement, contact :
Stefan Balev, Yoann Pigné, Eric Sanlaville (prenom.nom@univ-lehavre.fr)

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Context: The RI2C team of the LITIS laboratory in Le Havre has been working for years on temporal graphs
in an algorithmic and optimization perspective. Temporal (or dynamic) graphs are graphs that evolve over
time (in particular, edges can appear or disappear over time). The team is partner of a project funded by the
ANR: Temporal Graph Algorithms (acronym TEMPOGRAL, site https://www.labri.fr/perso/acasteig/tempogral/).
In particular, the project funds a thesis allowance and this internship. The successful intern will therefore be a
natural candidate for this stipend.

Internship topic: We are interested in the adaptation of classical graph problems to the temporal context.
The Traveling Salesman Problem (TSP) is one of the best known of these problems. In the temporal context,
each edge is associated with presence times (labels). The temporal TSP consists in constructing a sequence of
edges allowing to pass through all the vertices of the graph. The sequence of edges forms a cycle, but
moreover a solution associates to each edge one of its labels, so that the sequence of labels obtained is
increasing. In a "weak" version of the problem, it is allowed to pass several times through the same vertex
(this is called temporal exploration).
It is known that deciding whether a static graph admits an Hamiltonian cycle is already an NP-complete
problem. The temporal variant is also difficult even under very restrictive assumptions.
During the internship, we will be interested in the following question: what is the minimal duration of a
temporal exploration (defined as the value of its largest label)? More precisely, we can show with some
natural assumptions on the labels that this duration is at most of the order of n2. But can we always find a
solution whose duration is at most of the order of m, number of edges of the graph?
The successful trainee will need to become familiar with the notion of temporal graphs. He will then study
the temporal TSP, before trying to answer the above question. The study can be completed by experiments
that will help guide the theoretical analysis.
Bibliography
O. Michail. An introduction to temporal graphs: An algorithmic perspective. Internet Mathematics,
12(4):239-280, 2016. (Brief state of the art for temporal exploration and TSP p 29)
O. Michail and P. G. Spirakis. Traveling salesman problems in temporal graphs. In 39th International
Symposium on Mathematical Foundations of Computer Science (MFCS), pages 553-564. Springer, 2014.
Erlebach, T., Hoffmann, M., Kammer, F. (2015). On Temporal Graph Exploration. In: Halldórsson, M.,
Iwama, K., Kobayashi, N., Speckmann, B. (eds) Automata, Languages, and Programming. ICALP 2015.
Lecture Notes in Computer Science(), vol 9134. Springer, Berlin, Heidelberg.
P. Flocchini, B. Mans, and N. Santoro. Exploration of periodically varying graphs. In Y. Dong, D.-Z. Du,
and O. Ibarra, editors, Algorithms and Computation, volume 5878 of Lecture Notes in Computer Science,
pages 534-543. Springer Berlin Heidelberg, 2009.
D. Ilcinkas and A.M. Wade(2018). Exploration of the t-interval-connected dynamic graphs: the case of the
ring. Theory of Computing Systems, 62(5), 1144-1160.
Prerequisites: Master's degree or Engineering degree in computer science or applied mathematics. A good
knowledge of graphs is essential. Strong background in Algorithms and Operations Research is a plus.
Contacts:
Stefan Balev, Yoann Pigné, Eric Sanlaville (prenom.nom@univ-lehavre.fr)