Sujet : Autour des Graphes Universels Isométriques

Responsables : Cyril Gavoille, François Dross
Contact : gavoille@labri.fr Département : Combinatoire et Algorithmique
Équipes : Algorithmique Distribuée / Graphes et Optimisation
Type : stage Master Informatique
Lieu : LaBRI
Mot-clés : graphe, schéma d'étiquetage

Présentation du sujet :

Un sous-graphe isométrique est un sous-graphe $H$ d'un graphe $G$ où les distances dans $G$ entre sommets de $H$ sont préservées. Cela généralise la notion de sous-graphe induit qui ne préserve que les adjacences. Par exemple, la grille carrée à $9$ sommets $G$ contient $C_4$ comme sous-graphe isométrique, où $C_n$ est le cycle à $n$ sommets. Mais $C_8$ n'est pas un sous-graphe isométrique de $G$. Il apparaît, par contre, comme sous-graphe induit. La question générale que l'on se pose est de déterminer un graphe "universel" contenant comme sous-graphes isométriques tous les graphes d'une famille donnée. Les structures universelles apparaissent naturellement dans divers domaines de l'informatique, allant de la combinatoire à la géométrie computationnelle en passant par la théorie des graphes. Mais la notion de graphe universel isométrique n'a été abordée que récemment dans [EGG21a].

Plus précisément, un graphe $U$ est un graphe universel isométrique pour une famille de graphes $\mathcal{F}$ si tout graphe de $\mathcal{F}$ est isomorphe à un sous-graphe isométrique de $U$. Bien entendu, on cherche le plus petit graphe universel isométrique pour $\mathcal{F}$, puisqu'on peut toujours considérer l'union disjointe des graphes de $\mathcal{F}$ comme graphe universel. Dans la suite, on notera $\ell(\mathcal{F})$ le nombre de sommets du plus petit graphe universel isométrique pour la famille $\mathcal{F}$.

Un des intérêts de considérer les graphes universels isométriques est qu'ils fournissent un étiquetage de distance (ou distance labeling) pour les graphes de $\mathcal{F}$. En deux mots, il s'agit d'associer une étiquette à chaque sommet de chaque graphe de $\mathcal{F}$ de sorte que la distance entre deux sommets pris d'un graphe de $\mathcal{F}$ puisse être déterminée seulement à partir de leurs étiquettes, et de rien d'autre (en particulier en ignorant de quel graphe les deux sommets sont issus). Il n'est pas difficile de voir que tout graphe de $\mathcal{F}$ possède toujours un étiquetage de distance avec des étiquettes de seulement $\log(\ell(\mathcal{F}))$ bits par sommets.

Dans ce stage, on pourra par exemple considérer le cas où $\mathcal{F} = T_n$, la famille des arbres à $n$ sommets. Il est clair qu'un "arbre universel" pour $T_n$, soit un graphe universel qui est lui-même un arbre, sera également un graphe universel isométrique pour $T_n$. La taille minimum d'un tel arbre universel est connue pour être en $2^{(\log^2{n})/2}$ [CGC81] ce qui en fait donc un majorant pour $\ell(T_n)$. Mais cela ne dit pas qu'il n'y a pas de graphe universel isométrique plus petit pour $T_n$ qui ne soit pas un lui-même un arbre. Cependant on peut établir le minorant $\ell(T_n) \ge 2^{(\log^2{n})/4}$ en considérant les minorants connus sur l'étiquetage de distance [FGNW17]. Dit autrement il y a un écart quadratique entre le minorant et le majorant sur $\ell(T_n)$, écart qu'il conviendrait de réduire.

Bien sûr, le cas de $T_n$ n'est qu'une famille de graphes parmi d'autres. Citons d'autres familles toutes aussi intéressantes comme par exemple, les caterpillars (un arbre dont les sommets non-feuilles forment un chemin), ou encore les graphes de permutation ou les graphe d'intervalles. Pour ces derniers, on sait qu'il existe des distance labeling optimaux de $c\log{n}$ bits avec $c \in [3,9]$, voir [GP03,BG09], laissant espérer une borne polynomiale pour le graphe universel isométrique. Les familles comme les graphes de path-width ou de tree-width bornée pourrait aussi être des familles de premier plan à étudier. Pour le cas des graphes généraux il existe aussi un écart quadratique entre minorant et majorant qu'il conviendrait de réduire [EGG21a]. Le cas des graphes planaires est quant à lui très ouvert.

À plus long terme, les questions comme les relations fines entre graphe universel isométrique et distance labeling pourrait être explorées. Par exemple, quelle la plus petite fonction $c = c(n)$ de sorte que $\ell(\mathcal{F}_n) \le c^{k(n)}$ où $k(n)$ est la complexité du distance labeling pour la famille $\mathcal{F}_n$? sachant qu'on a toujours $\ell(\mathcal{F}_n) \ge 2^{k(n)}$. Pour quelles familles $\mathcal{F}_n$ a-t-on $c = 2+o(1)$? On peut également imaginer relâcher la contrainte "isométrique" et explorer les graphes universels où tous les graphes d'une famille donnée apparaissent comme des sous-graphes approximant les distances à un facteur $s>1$ près (une sorte de $s$-spanner universel) ou encore préservant seulement les petites distances.

Références :

[login: gavoille, pwd: bib0]

[EGG21a]
Louis Esperet, Cyril Gavoille, and Carla Groenland. Isometric universal graphs. SIAM Journal on Discrete Mathematics, 5(2):1224-1237, 2021.

[CGC81]
Fan R.K. Chung, Ronald Lewis Graham, and Don Coppersmith. On trees which contain all small trees. The Theory of Applications of Graphs, pages 265-272, 1981.

[FGNW17]
Ofer Freedman, Paweł Gawrychowski, Patrick K. Nicholson, and Oren Weimann. Optimal distance labeling schemes for trees. In 6th Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 185-194. ACM Press, July 2017.

[GP08]
Cyril Gavoille and Christophe Paul. Optimal distance labeling for interval graphs and related graphs families. SIAM Journal on Discrete Mathematics, 22(3):1239-1258, July 2008.

[BG09]
Fabrice Bazzaro and Cyril Gavoille. Localized and compact data-structure for comparability graphs. Discrete Mathematics, 309(11):3465-3484, June 2009.