Sujet : Graphe universel induit compact pour de petite famille de graphes

Responsable : Cyril Gavoille
Contact : gavoille@labri.fr
Département : Combinatoire et Algorithmique
Équipes : Algorithmique Distribuée / Graphes et Optimisation
Type : stage Master Informatique
Durée : 4 à 6 mois au printemps 2022
Lieu : LaBRI
Financement : oui, mais pas encore acquis
Mot-clés : structures de données distribués, schéma d'étiquetage, algorithmes de graphes, graphe universel

Présentation du sujet :

Un schéma d'étiquetage est une façon de mettre en œuvre de manière distribuée des requêtes portant sur les sommets d'un graphe. Par exemple, un schéma d'étiquetage d'adjacence consiste, dans un premier temps, à attribuer aux sommets d'un graphe une étiquette individuelle (encodage). Puis, dans un deuxième temps, de pouvoir déterminer à l'aide d'un algorithme (décodage) si deux sommets $u$ et $v$ arbitraires du graphe sont adjacents simplement à partir des étiquettes de $u$ et de $v$, et rien d'autre. En particulier l'algorithme de décodage n'a, à aucun moment, accès au graphe ou à une de ses parties, ce qui est un avantage déterminant pour des applications en calcul distribué.

Les schémas d'adjacence sont intimement liés à la notation de graphe universel induit, c'est-à-dire un graphe $U$ contenant comme sous-graphe induit chaque graphe d'une famille $F$ donnée. Il est bien connu [KNR92] que $F$ possède un schéma d'adjacence avec des étiquettes de $b$ bits si et seulement si $U$ possède au plus $2^b$ sommets. Minimiser la taille des étiquettes d'un schéma d'adjacence est donc équivalent à minimiser le nombre de sommets d'un graphe universel induit.

Dans ce stage, on s'intéresse aux familles de graphes $F$ composées d'un nombre limité de graphes, disons des familles $F = \{G_1,...,G_k\}$ avec $k=2,3,4$ par exemple. On se pose alors la question du nombre minimum de sommets d'un graphe universel induit pour $F$, mais aussi bien sûr la question de construire de tels graphes universels $U(F)$. Par exemple, quel est le nombre minimum de sommets d'un graphe universel induit pour trois graphes quelconques à $n$ sommets ? Est-ce beaucoup moins que $3n$ ?

Ces questions pourront être abordées également sous un aspect plus algorithmique, en considérant en particulier le cas $k = 2$, c'est-à-dire à la complexité de calcul d'un graphe universel induit $W(A,B)$ optimal pour une famille composée de deux graphes $A$ et $B$ quelconques, donc pas forcément de même taille. Résoudre un tel problème permettrait de construire des graphes universels $U(F)$ de petite taille pour une famille $F$ en itérant la construction triviale $A := W(A,G_i)$ pour chaque graphe $G_i \in F$. Inversement, trouver une sous-famille $F'\subseteq F$ de petite taille ($|F'| \ll |F|$) et qui maximiserait le nombre de sommets de $W(A,B)$ pour chaque paire de graphes $A,B \in F'$, pourrait contribuer à trouver de nouvelles bornes inférieures sur des graphes universels de familles bien connues, comme celles des arbres [Trimble21], des unions disjointes d'étoiles, de caterpillars, des graphes planaires extérieurs, des graphes planaires [DEGJx21], etc.

Ce sujet se rattache à un domaine de recherche très actif, ayant de nombreuses possibilités d'extensions (soit en terme de famille de graphes, soit en terme de liens avec d'autres domaines comme la complexité de communication [Harms19,KUV19]) et peut faire l'objet, selon la motivation et le travail du candidat, d'une poursuite en thèse.

Références :

[login: gavoille, pwd: bib0]

[KNR92] Sampath Kannan, Moni Naor, and Steven Rudich. Implicit representation of graphs. SIAM Journal on Discrete Mathematics, 5(4):596-603, 1992.

[AR14] David Adjiashvili and Noy Rotbart. Labeling schemes for bounded degree graphs. In 41st International Colloquium on Automata, Languages and Programming (ICALP), volume 8573 of Lecture Notes in Computer Science (ARCoSS), pages 375-386. Springer, July 2014.

[ADBTK17] Stephen Alstrup, Søren Dahlgaard, and Mathias Bæk Tejs Knudsen. Optimal induced universal graphs and adjacency labeling for trees. Journal of the ACM, 64(4):Article No. 27, August 2017.

[AAHBx19] Mikkel Abrahansen, Stephen Alstrup, Jacob Holm, Mathias Bæk Tejs Knudsen, and Morten Stöckel. Near-optimal induced universal graphs for cycles and paths. Discrete Applied Mathematics, November 2019.

[DEGJx21] Vida Dujmovic and Louis Esperet and Cyril Gavoille and and Gwenael Joret and Piotr Micek and Pat Morin. Adjacency Labelling for Planar Graphs (and Beyond). Journal of the ACM, 68(6):Article No. 42, September 2020.

[Trimble21] James Trimble. Induced universal graphs for families of small graphs. Technical Report 2109.00075v1 [math.CO], arXiv, August 2021.

[Harms19] Nathaniel Harms. Universal communication, universal graphs, and graph labeling. Technical Report 1911.03757v1 [cs.CC], arXiv, November 2019.