François Pitois

Intitulé : Recherche de régularités et représentations succinctes de graphes

Publications

Pattern detection in ordered graphs (2024+), En cours de soumission à SIDMA 2024, arxiv.org/abs/2302.11619, Ducoffe, G., Feuilloley, L., Habib, M. et Pitois, F.
Une façon courante de caractériser un graphe est par le biais de sous-graphes ou de mineurs interdits. Ces caractérisations jouent un rôle central en théorie des graphes, mais ne donnent pas lieu à des algorithmes de reconnaissance efficaces. À l'inverse, de nombreuses classes de graphes peuvent être reconnues efficacement grâce à une caractérisation d'un autre genre : il faut qu'il existe un ordre des sommets tel qu'un motif n'apparaissent pas, où un motif est un sous-graphe ordonné. Ce papier s'intéresse à la question suivante : étant donné un graphe ordonné de taille n, quelle est la meilleure complexité pour reconnaître un motif de taille k ? Nous avons prouvé que quasiment tous les motifs à 3 sommets peuvent être détectés en temps linéaire. Nous avons également trouvé une borne inférieure pour les motifs à 4 sommets, en montrant qu'il était peu probable qu'un algorithme sous-quadratique existe. Enfin, nous avons défini un paramètre, la merge-width et montré qu'un motif de merge-width t pouvait être détecté en temps O(n^ct) pour une certaine constante c. Par conséquent, en montrant que les motifs planaires extérieurs ainsi que d'autres classes de motifs avaient une merge-width bornée, nous avons conclu que ces motifs pouvaient être détectés en un temps indépendant de leur taille k.
Hypergraphs with Polynomial Representation: Introducing r-splits (2024), Discrete Mathematics & Theoretical Computer Science, 25:3 special issue ICGT'22, arxiv.org/abs/2212.13822, Pitois, F., Haddad, M., Seba, H. et Togni, O.
La décomposition de graphes représente un aspect majeur en théorie des graphes. L'une d'entre elles est la décomposition en splits, qui présente de nombreuses propriétés théoriques. Dans ce papier, nous avons généralisé la notion de split en introduisant les r-splits. Nous avons montré que l'ensemble des r-splits satisfait des propriétés qui généralisent celles des splits classiques. L'une de ces propriétés est le fait que l'ensemble des splits classiques d'un graphe est engendré par un sous-ensemble linéaire de ces splits. Nous l'avons généralisée en prouvant que l'ensemble des r-splits d'un graphe peut être engendré par un sous-ensemble de taille O(n^r+1). Enfin, nous avons montré que cette borne était presque atteinte, en exhibant un ensemble de r-splits qui ne peut être engendré que par des sous-ensembles de taille Ω(n^r).
A Fine-Grained Structural Partitioning Approach to Graph Compression (2023), DaWaK 2023: Big Data Analytics and Knowledge Discovery pp 392–397, link.springer.com/chapter/10.1007/978-3-031-39831-5_36, Pitois, F., Seba, H. et Haddad, M.
Un des enjeux actuels est la compression de graphes. En effet, un graphe permet de représenter des ensemble de données du monde réel, qui peuvent parfois être extrêmement grands et prendre beaucoup d'espace de stockage. La compression permet d'économiser cet espace. Il existe de nombreux algorithmes capables de compresser des graphes tels que Slash Burn, Metis, Big Clam ou Louvain. Notre approche a été d'unifier différents algorithmes de compression et de recherche de régularité pour pouvoir bénéficier du point de vue de chacun d'eux. Cela a mené à une compression prenant en considération plusieurs types de régularités. La difficulté a été de tenir compte des chevauchements que peuvent créer les différents algorithmes afin de ne pas dupliquer l'information et de ne pas perdre en efficacité de compression. Nous avons programmé ce nouvel algorithme et nous l'avons optimisé pour qu'il puisse être appliqué à des graphes ayant jusqu'à un million de sommets. Nous avons essayé notre algorithme sur différents graphes issus de données réelles et nous avons obtenu des résultats améliorant le taux de compression d'autres algorithmes. Notre algorithme est disponible à l'adresse https://gitlab.liris.cnrs.fr/fpitois/fgsp.git. Il reste encore à tester et optimiser un certain nombre de paramètres. Nous pouvons par exemple changer la liste des algorithmes utilisés pour obtenir notre algorithme unifié, changer les paramètres de ces algorithmes, ou encore modifier les paramètres utilisés pour unifier ces algorithmes.
Two lower bounds for p-centered colorings (2020), Discrete Mathematics & Theoretical Computer Science, 22, arxiv.org/abs/2006.04113, Dubois L., Joret G., Perarnau G., Pilipczuk M. et Pitois F.
Étant donné un graphe G et un entier p, une coloration f:V(G)→ℕ est p-centrée si pour tout sous-graphe connecté H de G, soit f utilise plus de p couleurs pour H, soit il y a une couleur qui apparaît une seule fois dans H. Cette notion joue un rôle important dans la théorie des graphes creux. Ce papier présente deux bornes inférieures quant aux nombres de couleurs nécessaires pour obtenir une coloration p-centrée. La première borne exhibe une classe de graphes d'expansion linéaire telle que pour chaque entier p, il y a un graphe dans cette classe tel que toute coloration p-centrée nécessite au moins exp(O(√
p
)) couleurs. La deuxième borne montre qu'il existe des graphes de degré maximal borné Δ qui nécessitent au moins Ω(Δ^2-1/p p ln^-1/pΔ) couleurs, ce qui correspond à la meilleure borne supérieure connue, au facteur logarithmique près.

François Pitois

Présentation

Thèse

Publications

Enseignement