Algorithmes d'énumeration pour des éditions de graphes vers des classes structurées // Enumeration algorithms for graph editing problems towards structured classes

En algorithmique d'énumération, on prend en entrée une donnée I et on produit en sortie tous les objets O1, O2… satisfaisant une certaine condition par rapport à l'entrée. Prenons l'exemple du problème de l'énumération des triangulations minimales d'un graphe. L'entrée est un graphe quelconque G et on souhaite en sortie toutes ses triangulations minimales. Une triangulation minimale de H est un graphe triangulé (tout cycle d'au moins quatre sommets de H possède une corde, c-à-d une arête entre deux sommets non consécutifs du cycle), obtenu à partir de G en ajoutant un ensemble minimal F d'arêtes. Observons que le nombre de triangulations minimales d'un graphe G peut être exponentiel en la taille de ce graphe, comme l'illustre le cas où G est un cycle à n sommets.

Pour répondre à cela, l'algorithmique d'énumération propose plusieurs mesures d'efficacité, notamment en fonction de la taille de la sortie [JYP88]. On peut en dégager une notion de temps d'exécution « par solution », et on recherche alors - le graal - des algorithmes à délai polynomial. Ces algorithmes possèdent la propriété que le temps écoulé entre l'obtention de deux éléments de l'ensemble de sortie est borné polynomialement par rapport à la taille de l'entrée.

L'algorithmique d'énumération a connu un essor considérable ces dernières années, avec de nouveaux outils, cf. par exemple [Bro23] pour une introduction. Cela a permis par exemple d'obtenir un algorithme à délai polynomial pour l'énumération des triangulations minimales [BLM22].

Nous proposons de nous intéresser dans cette thèse à des algorithmes d'énumération efficaces pour une famille de problèmes plus générale : les éditions minimales de graphes, vers des classes structurées.
Considérons une classe de graphes CL et un graphe quelconque G La question informelle est : peut-on « légèrement » le graphe G afin de le faire appartenir à la classe CL ? Plus formellement, pour modifier le graphe G en un graphe H dans CL on peut considérer plusieurs opérations, notamment (1) l'ajout d'une arête manquante et (2) la suppression d'une arête. Si H est obtenu uniquement par l'opération d'ajout, on dit qu'il est une complétion de G. On parle de délétion si seule l'opération suppression d'arêtes est utilisée, et enfin d'édition si l'on autorise les deux. La complétion, délétion et respectivement édition est appelée \emph{minimale} si l'ensemble F+ d'arêtes manquantes ajoutées, l'ensemble F- d'arêtes supprimées, respectivement l'union de F+ et F- est minimal par inclusion.

Le problème de l'édition minimale a été étudié sous l'angle de l'optimisation (trouver efficacement une édition minimale) pour des classes de graphes CL telles que les graphes triangulés [BC21] ou les cographes [Cre21]. L'objectif de cette thèse est d'obtenir des algorithmes d'énumérations efficaces pour les éditions minimales vers certaines classes de graphes, notamment les cographes et les graphes triangulés, mais les éditions vers d'autres classes plus simples (split, cluster) sont déjà intéressantes.

Un deuxième objectif sera d'étudier l'énumération des éditions obtenues avec au plus k modifications, où k est un paramètre supposé petit. De nombreux résultats d'optimisation permettent d'obtenir de telles éditions vers diverses classes de graphes [DPT23,DPRT22,CM16], voir aussi [CDFG20] pour un article de synthèse. Le but est d'en obtenir les meilleurs algorithmes paramétrés d'énumération, par exemple des algorithmes avec un délai d'énumération FPT (fixed-parameter tractable), c'est à dire des délais de type f(k)*poly(n), pour les éditions avec au plus k modifications vers des classes telles que les cographes et les graphes triangulés.
------------------------------------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------------------------------------

In enumeration algorithms, we take an input I and produce as output all objects O1, O2, etc. that satisfy a certain condition in relation to the input.
Let's take the example of the problem of enumerating the minimum triangulations of a graph. The input is an arbitrary graph G and we want all its minimal triangulations as output. A minimal triangulation of H is a triangulated graph (every cycle of at least four vertices of H has a chord, i.e. an edge between two non-consecutive vertices of the cycle), obtained from G by adding a minimal set F of edges. Note that the number of minimal triangulations of a graph G can be exponential in the size of this graph, as illustrated by the case where G is a cycle with n vertices.
To address this, enumeration algorithms offer several efficiency measures, particularly in terms of the size of the output [JYP88]. From this, we can deduce a notion of execution time ‘per solution', and we then search for algorithms with a polynomial delay - the Holy Grail. These algorithms have the property that the time elapsed between obtaining two consecutive elements from the output set is bounded polynomially with respect to the size of the input. Enumeration algorithms have seen considerable growth in recent years, with new tools, see for example [Bro23] for an introduction. This has made it possible, for example, to obtain a polynomial delay algorithm for the enumeration of minimal triangulations [BLM22].

In this thesis, we propose to focus on efficient enumeration algorithms for a more general family of problems: minimal graph edits, towards structured classes.
Consider a class of graphs CL and any graph G The informal question is: can we ‘slightly' modify the graph G so that it belongs to the class CL? More formally, to modify the graph G into a graph H in CL, we can consider several operations, including (1) adding a missing edge and (2) deleting an edge. If H is obtained solely by the addition operation, it is said to be a completion of G. We speak of deletion if only the edge deletion operation is used, and finally of editing if both are allowed. Completion, deletion and editing, respectively, are called minimal if the set F+ of added missing edges, the set F- of deleted edges, respectively the union of F+ and F-, is minimal by inclusion.
The problem of minimal editing has been studied from the point of view of optimisation (finding a minimal editing efficiently) for classes of graphs CL such as triangulated graphs [BC21] or cographs [Cre21]. The aim of this thesis is to obtain efficient enumeration algorithms for minimal editings to certain classes of graphs, in particular cographs and triangulated graphs, but editings to other simpler classes (split, cluster) are already of interest.
A second objective will be to study the enumeration of the editions obtained with at most k modifications, where k is a parameter assumed to be small. Numerous optimisation results make it possible to obtain such editings for various classes of graphs [DPT23, DPRT22, CM16], see also [CDFG20] for a review article. The aim is to obtain the best parameterised enumeration algorithms, for example algorithms with an FPT (fixed-parameter tractable) enumeration delay, i.e. delays of type f(k)*poly(n), for editings with at most k modifications to classes such as cographs and triangulated graphs.
------------------------------------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Début de la thèse : 01/10/2025

Financement d'un établissement public Français

Université d'Orléans

551 Mathématiques, Informatique, Physique Théorique et Ingénierie des Systèmes - MIPTIS

La candidade ou le candidat doit avoir des connaissances solides en algorithmique et combinatoire des graphes, et une appétence pour l'informatique fondamentale. Un stage de recherche sur ces sujets serait apprécié.
Candidates must have a solid knowledge of graph algorithms and combinatorics, and an interest in fundamental computer science. A research internship or master thesis in these subjects would be appreciated.