Je tiens à remercier sincèrement le personnel administratif et technique du LIMOS pour m'avoir fourni de bonnes conditions de travail, ainsi que Dominique Torrisani dont l'aide m'a été précieuse.

Qu'aurait été mon séjour au LIMOS s'il n'y avait eu toutes les personnes avec qui j'ai partagé mon bureau (ou presque) : Oscar, Simon, Alexey, Alexis, Élodie, Trang, Aurélien, Loan, Mari et les autres. Merci à vous pour la bonne humeur et pour les pauses café. Merci également au cerisier du LIMOS qui agrémente tant ombrageusement que gustativement le début de l'été.

Mais pendant ces trois quatre ans, il n'y a pas eu que la thèse ! J'aimerais donc remercier chaleureusement toutes les personnes (nombreuses !) qui ont contribué à la richesse de ma vie musicale pendant toutes ces années : par ordre d'apparition, Agnès Lacornerie et l'ensemble de flûtes du conservatoire de Clermont, l'atelier de danse trad, Maude et les Phonies Polies, le Département de Musique Ancienne de l'ENM de Villeurbanne tout entier, l'Académie d'été de l'ensemble Artifices, Iels en Voix, la Chapotée, Yufang, Ophélie Berbain, et j'en oublie sûrement.

Un IMMENSE merci à Frédérique Thouvenot ; merci à toi de m'avoir reprise dans ta classe de flûte à bec à Villeurbanne, merci pour ton enseignement et ta passion pour la flûte à bec (merci aussi pour le shakuhachi !). Merci à vous Élisa, Julie, Alexis, Juliette, Célia, et merci aussi aux flûtes de consort (je ne les oublie pas ♡). Sans cette année passée loin de mon bureau à l'ISIMA, je crois que cette thèse aurait été beaucoup moins bien

L

es graphes sont des structures combinatoires très simples. Ils peuvent être vus comme des représentations abstraites des interactions entre divers objets. En dépit de leur apparente simplicité, les graphes sont des outils puissants quand il s'agit de modéliser de nombreuses situations de la vie réelle. Leurs applications sont variées : recherche opérationnelle (allocation de ressources, ordonnancement), Internet mondial (liens entre les pages web), réseaux de communication, mais aussi réseaux routiers, transports et véhicules autonomes, entre autres. Ces structures combinatoires sont présentes dans de nombreux domaines scientifiques : on les rencontre par exemple en biologie (arbres phylogénétiques, génétique, interactions protéines-protéines), en chimie (structures des molécules), en sociologie (analyse des réseaux sociaux), en neurosciences (interactions entre les différentes zones du cerveau). . . q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q Figure 1 : Un graphe construit à partir de données d'IRMf au repos sur le cerveau d'un patient dans le coma. Données : Achard et al., 2012 [START_REF] Achard | Hubs of brain functional networks are radically reorganized in comatose patients[END_REF].

Pour illustrer une de ces applications, la Figure 1 représente un graphe construit à partir de données médicales sur le cerveau d'un patient dans le coma [START_REF] Achard | Hubs of brain functional networks are radically reorganized in comatose patients[END_REF]. Il modélise

| INTRODUCTION (FRENCH)

les 90 zones identifiées du cerveau et 400 connexions entre ces zones. Dans ce cas, la représentation des données sous forme de graphe est utilisée pour étudier comment l'organisation du cerveau change chez les patients dans le coma.

Peut-être parce que les graphes sont omniprésents en science, la théorie des graphes est un domaine de recherche très actif. Les problèmes étudiés sur les graphes concernent à la fois les aspects algorithmique et structurel. En théorie des graphes, les problèmes les plus généralement étudiés sont des problèmes d'optimisation : quel est le nombre minimal de couleurs dont on a besoin pour colorer un graphe donné ? Comment peut-on trouver le nombre minimum de noeuds à enlever pour qu'un graphe acquière une certaine propriété décidée à l'avance ? Peut-on calculer efficacement le plus court circuit passant par une liste de villes donnée avant de retourner à son point de départ ? En réalité, ces problèmes sont pour la plupart difficiles (NP-difficiles ou NP-complets), et sont de ce fait étudiés sous divers angles.

Parfois il est difficile de résoudre des problèmes d'optimisation, mais plus souvent encore, calculer seulement une solution d'un problème n'a en fait même pas de sens. Par exemple, lorsque l'on s'intéresse à une base de données, la requête la plus courante est la liste de toutes les entrées qui satisfont certaines conditions : la liste des personnes vivant dans une ville donnée, la liste des étudiants qui ont réussi un examen, la liste des itinéraires possibles pour atteindre une destination. . . Dans d'autres situations comme des applications en biologie ou en statistiques [START_REF] Córdoba | On generating random Gaussian graphical models[END_REF][START_REF] Calamoneri | On maximal chain subgraphs and covers of bipartite graphs[END_REF], la notion de « meilleure » solution peut être très difficile à modéliser en termes de graphes. Il est plus intéressant dans ce cas de pouvoir générer un échantillon de « bonnes » solutions (pour une définition appropriée de « bonne »), et laisser l'utilisateur•rice choisir celle qui convient le mieux selon ses critères.

C'est pourquoi on s'intéresse aux algorithmes d'énumération qui, à l'inverse des algorithmes d'optimisation, renvoient toutes les solutions d'un problème (ou au moins toutes les « bonnes » solutions). En général (mais pas toujours), pour trouver toutes les solutions du problème, on commence par en trouver une et par des modifications sur les solutions déjà trouvées, on en génère de nouvelles. Pour faire cela, on doit s'assurer que les règles de modifications locales permettent vraiment de visiter toutes les solutions possibles.

L'approche énumérative présente quelques autres spécificicités. En particulier, le nombre de solutions qu'un algorithme d'énumération doit renvoyer peut être vraiment énorme comparé à la taille de l'entrée. Dans une telle situation, qu'entend-on par efficace pour un algorithme d'énumération ? Le temps d'exécution de l'algorithme est-il encore borné en fonction de la taille de l'entrée, ou bien doit-on aussi prendre en compte le nombre de solutions ? Dans ce cas précis, la notion d'efficacité a été adaptée pour prendre en compte les spécificités des algorithmes d'énumération [START_REF] Johnson | On generating all maximal independent sets[END_REF].

En pratique, on cherche à générer toutes les solutions l'une après l'autre en garantissant un temps court entre deux solutions. Les algorithmes présentés dans cette Introduction G raphs are very simple combinatorial structures. They can be seen as abstract representations of objects and their interactions. Despite their apparent simplicity, graphs are powerful tools when it comes to modelling many real-life situations. Their applications are various: operations research (resources allocation, scheduling), the world wide web (links between webpages), communication networks, but also roads, transportation, and autonomous vehicles, among others. These combinatorial structures are found in many -if not all -scientific fields: they arise for example in biology (phylogenetic trees, genetics, protein-protein interactions), chemistry (structures of molecules), sociology (social network analysis), neurosciences (interactions between the different zones of the brain). . . As an illustration, Figure 1 represents a graph obtained from medical data on the brain of a comatose patient [START_REF] Achard | Hubs of brain functional networks are radically reorganized in comatose patients[END_REF]. It models the 90 identified zones of the brain and 400 connections between them. In this case, the representation of data in the form of a graph is used to study how the organisation of the brain changes for a person in a coma. q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q Figure 1: A graph obtained from fMRI data on the brain of a comatose patient. Data: Achard et al., 2012 [START_REF] Achard | Hubs of brain functional networks are radically reorganized in comatose patients[END_REF].

Perhaps due to the omnipresence of graphs in science, graph theory -the study of graphs -is nowadays a very active branch of research. The problems studied on graphs concern both the structural and the algorithmic aspects. In graph theory, the problems typically studied are optimisation problems: what is the minimum number of colours needed to colour a given graph? How can we find the minimum number of nodes one has to remove to acquire some desired property? Can we compute efficiently the shortest circuit going through a prescribed set of cities before going back home? In fact, these questions are usually hard (NP-hard or NP-complete), and are therefore studied from many angles. Sometimes, solving optimisation problems is hard, yet even more often it is just not meaningful to generate only one solution of a problem. For example, when dealing with databases, the typical request is the list of all entries satisfying some specified conditions: list of people living in a given city, list of students who have passed an exam, list of possible itineraries to reach a destination. . .

In some other situations such as applications in bioinformatics or statistics [START_REF] Córdoba | On generating random Gaussian graphical models[END_REF][START_REF] Calamoneri | On maximal chain subgraphs and covers of bipartite graphs[END_REF], the notion of "best" solution can be hard to model in terms of graphs. It is more interesting in this case to be able to generate a sample of "good" solutions (for an appropriate definition of "good"), and let the user choose themself the best suited solution for their purpose. This is why we are interested in enumeration algorithms which, unlike optimisation algorithms, return all the solutions of a given problem (or at least all the "good" ones). In general (but not always), to find all the solutions of a problem we begin with finding one, and then slightly modify the solutions already found to discover new ones. Doing this, we need to ensure the local modification rules really allow us to visit all the possible solutions.

The enumeration approach has other specific issues. In particular, the number of solutions that have to be computed by an enumeration algorithm can be really huge compared to the input size. In such a situation, what does it mean for an enumeration algorithm to be efficient? Is the running time of the algorithm still bounded in terms of the input size, or is it necessary to take the number of solutions into account? The notion of efficiency for enumeration algorithms has therefore been adapted to take these issues in consideration [START_REF] Johnson | On generating all maximal independent sets[END_REF] (see Chapter 2 for more details).

In practice, we seek to generate all the solutions one after the other while guaranteeing the shortest possible time between two solutions. The algorithms mentioned in the present manuscript run with polynomial delay, meaning the time spent between two solutions is polynomial in the input size. These algorithms are considered fast in theory.

In this thesis, we are interested in graph modification problems. Imagine a situation where some data have been acquired and transformed into a graph, and the structure | 13 of the data implies some specific structural property on the graph. The structural property is important because it permits to run the computations faster. Unfortunately, during the transfer or gathering, some of the data have been altered: the graph lost its interesting property. In this situation, a natural thing to do is try to repair the graph so that it gets the interesting property again. However, we do not know how the graph was before it was sent.

To "repair" the graph, we have three choices: removing some nodes, removing some links between nodes, or on the contrary adding some links. For each problem we consider, we choose one of these operations and only make this sort of changes. The associated optimisation problem asks for the minimum number of elements to remove (or add) in order to make the graph acquire the desired property. However, such an optimisation problem is usually hard [START_REF] Lewis | The node-deletion problem for hereditary properties is NP-complete[END_REF], and this is where enumeration becomes useful.

When trying to solve our problem with enumeration, we assume that the amount of alterations is "not too large". Then, the principle is to generate a bunch of potential reparations of the graph, and choose the most credible one, since the credibility of a solution is not always something easy to model mathematically.

The question we address in the present thesis is the following. Given a graph G and a graph property P, can we enumerate efficiently all "reparations" of G into the property P? There are several ways to approach the question.

First, one can fix the property P in advance and benefit from the known characterisations of P to enumerate all "reparations" of G in P. This can be very powerful and provide efficient algorithms, as those designed in Chapter 3. However, algorithms obtained this way cannot be adapted easily to other properties.

The other approach consists in looking for a general algorithm which, given a graph G and a property P (plus maybe some operation specific to P), returns all the "reparations" of G into the property P, without fixing P in advance. Recent progress has been made on the general approach [START_REF] Cohen | Generating all maximal induced subgraphs for hereditary and connected-hereditary graph properties[END_REF][START_REF] Conte | Proximity search for maximal subgraph enumeration[END_REF]. In Chapter 6 of the present thesis, we also study and improve an existing general method for this purpose.

We are interested here in four well known graph properties that are related to interesting parameters in graphs. These properties are detailed in Chapter 1.

The manuscript is organised as follows.

First, in Chapter 1, we give some necessary background about graphs: definitions of the basic objects and concepts used in the sequel, and we introduce minimal completions and deletions of a graph into a prescribed class. These objects will be at the centre of our attention, together with maximal induced subgraphs.

Then, Chapter 2 is devoted to the introduction of enumeration and its algorithmic aspects. Before linking formally enumeration with minimal graph completions and deletions, we present some of the most famous existing techniques that imply efficient enumeration algorithms under certain conditions. We will have a closer look on a particular class of graphs, split graphs, in Chapter 3. Two problems are considered on split graphs; both of them give different insights on subgraph enumeration problems. However, the algorithms we obtained for split graphs are very specific.

In order to look for a general technique, we investigate the famous Flashlight Search in Chapter 4. We prove the difficulty of a sub-problem, the extension problem, preventing the technique to be as general as we would like it to be. This is why in Chapter 5, we are interested in a recently introduced enumeration technique, Proximity Search, which seems to be in some sense more general than the previously known ones and achieves good time complexity. This technique is here successfully applied to several problems: enumeration of maximal sub-cographs and threshold subgraphs, and the challenging question of minimal chordal completions enumeration.

Generalising our approach leads us to extend the usual Proximity Search-based technique used in practice. Two extensions of it -in different directions -are exposed in Chapter 6, allowing us to enlarge the set of problems that can be solved, and to reduce the space usage in some cases.

In parallel to enumeration algorithms, other scientific projects about graphs have been joined during this thesis. The results we obtained refer to more structural aspects of graphs.

One of the projects is about connected greedy colourings of graphs. The question we addressed is the following: what are the graphs for which no connected greedy colouring algorithm uses the optimal number of colours? The other project was about locating-dominating sets. Given a directed graph D, what is the minimum size of a set of nodes that is both dominating (every node is linked to a node in the set) and locating (two different nodes have different neighbours in the set)? By restricting each time the graph to satisfy a specific property, we were able to partially answer those questions.

The two aforementioned problems will not be addressed in the present document, but a summary of these contributions can be found at the end of the manuscript.

Chapter 1 Graphs, completions and deletions

This chapter contains a brief introduction to the basic objects in which we are interested: graphs. More information on this topic can be found in several works including the reference books written by Diestel [START_REF] Diestel | Graph theory[END_REF] and Golumbic [START_REF] Charles | Algorithmic graph theory and perfect graphs[END_REF]. After giving some general information about graphs, we will detail the problems that are studied in all the remaining of this thesis.

A ll the problems mentioned in this work are problems on graphs. This is why in this chapter, we will give the necessary background and notations on graph theory that will be useful in the sequel. After that, we describe more formally the problems in which we are interested.

Graphs and properties 1.General definitions and notations

This section is intended to present in a unified way the notations that will be used in the rest of the thesis. Standard graph theory notations are adopted, such as those provided in Diestel's book [START_REF] Diestel | Graph theory[END_REF].

In the present work, graphs as "basic objects" -those on which the problems are defined -are always considered simple and undirected. Nevertheless, on a higher level, we will also be led to consider some oriented graphs.

Definition 1.1 (Graph).

A graph is a couple of sets G = (V, E) such that all elements of E are two-element-subsets of V . The elements of V are called the vertices of G, those of E are called its edges.

For the remainder of this section, let G = (V, E) be a graph. When the context is ambiguous, for example when several graphs are involved, we may use the notations V (G) and E(G) to precise which graph we are considering.

Edges and neighbourhoods. For an edge {u, v} ∈ E, we will often use the simpler notation uv. The vertices u and v are called adjacent if uv ∈ E, and the edge uv is said to be incident to its endpoints u and v.

The neighbourhood of a vertex v in G is denoted by N G (v) and defined as the set of vertices adjacent to v. These vertices are called the neighbours of v. More formally,

N G (v) := {w ∈ V (G) | vw ∈ E(G)}.
The number of neighbours of a vertex v is called its degree, denoted by d G (v). The closed neighbourhood of a vertex v in G is defined as

N G [v] := N G (v) ∪ {v}.
When it is clear from the context, the subscript G might be omitted.

Whenever two vertices x and y are such that N (x) \ {y} = N (y) \ {x}, they are called twins. If x and y are twins and xy ∈ E, that is, if N [x] = N [y], then x and y are called true twins. Otherwise, N (x) = N (y) and x and y are called false twins. These two situations are illustrated in Figure 1.1. A path in G between two vertices u and v, also called a u-v-path, is a sequence of distinct vertices v 0 = u, v 1 , . . . , v k = v such that for any 1 ⩽ i ⩽ k, v i-1 v i ∈ E. The graph G is connected if for any two vertices u and v ∈ V , there exists a u-v-path, that is, a path between u and v, in G.

A cycle is a sequence of distinct vertices v 0 , v 1 , . . . , v k = v 0 such that for any 1 ⩽ i ⩽ k, v i-1 v i ∈ E. A graph without any cycle is called a tree.

The complement of a graph G is the graph G on the vertex set V whose edge set is exactly the set of two-element-subsets of V that are not in E. More formally, G = (V, {{u, v} | u ̸ = v ∈ V and {u, v} / ∈ E}). Therefore, two adjacent vertices in G are non-adjacent in G, and conversely two non-adjacent vertices in G are adjacent in G.

Finally, given X, Y two subsets of vertices of G, the symmetric difference between X and Y , denoted by X△Y , is defined as (X ∪ Y ) \ (X ∩ Y ).

GRAPHS AND PROPERTIES | 17

Subgraphs and supergraphs. Let X ⊆ V be a subset of vertices of G. We denote by G[X] the subgraph of G induced by X, defined as G[X] = (X, E(G) ∩ X

2 ), where the notation X 2 stands for the set of all two-element subsets of X. Alternatively, G[X] is obtained from G by removing all the vertices which do not belong to X, and all the edges incident to at least one deleted vertex. For simpler notations, for a set Y ⊆ V we might sometimes write

G \ Y instead of G[V \ Y ].
A graph H is called an induced subgraph of G if there exists

X ⊆ V such that G[X] is isomorphic to H 1 .
For a graph H, if G does not contain a copy of H as an induced subgraph, the graph G is called H-free.

A graph H is a subgraph of G if H can be obtained from G by removing some vertices and some edges of G, including those which were incident to at least one deleted vertex, that is to say if V (H) ⊆ V (G) and E(H) ⊆ (E(G) ∩ V (H)

2

). Of course, induced subgraphs are particular subgraphs where the last inclusion is an equality, i.e. E(H)

= (E(G) ∩ V (H) 2 ). If in addition V (H) = V (G), then H is called an edge-subgraph of G. A graph H is called an edge-supergraph of G, if V (H) = V (G)

and E(G) ⊆ E(H).

Remark that H is an edge-supergraph of G if and only if its complement H is an edge-subgraph of G.

Graph properties. Since we are interested in graphs that satisfy a certain graph property, let us have a look on the different kinds of graph properties.

By abuse of language, we will often identify a graph property with the set of graphs satisfying it, and write "the class P" to denote the set of all graphs that fulfil the property P.

Let us denote by P = {G | G ∈ P} the complementary class of P, that is, the class of all graphs whose complement fulfils the property P. Then, if P = P, we will say that the class P is self-complementary.

A graph property P is called hereditary when it is closed under vertex removal. In other words, if the property is fulfilled by the graph we consider, then it is also fulfilled by all its induced subgraphs. A property P is said to be connected-hereditary if, when a graph satisfies P, all its connected induced subgraphs also satisfy P. All the properties considered in this thesis are hereditary. Typically, being H-free (for a given graph H) is a hereditary property. In this case, H is called a forbidden induced subgraph for the property. When a graph property P is defined by a family F of forbidden induced subgraphs -equivalently, P corresponds to being F-free, or H-free for any H ∈ F -, the elements of F are called obstructions for P.

A graph property is called monotone when it is closed under both edge removal and vertex removal. That is to say, if the property is satisfied by G, then it is also satisfied by all subgraphs of G.

A property P is called sandwich-monotone [START_REF] Heggernes | Single-edge monotonic sequences of graphs and linear-time algorithms for minimal completions and deletions[END_REF] if, for any two graphs G and H on the same vertex set V , that both fulfil the property P, and such that H is an edge-subgraph of G, there exists a sequence of edges e 1 , e 2 , . . . , e k of E(G) \ E(H) such that for any 1 ⩽ i ⩽ k, the graph (V, E(H) ∪ S i ) verifies property P, where S i = {e 1 , . . . , e i }. In other words, there exists a sequence of single-edge removals that allows us to go from G to H. In the general framework of set systems, being sandwich-monotone is equivalent to being a strongly accessible set system [START_REF] Conte | Listing maximal subgraphs satisfying strongly accessible properties[END_REF].

Directed graphs. Some graphs that will be considered here are directed graphs, meaning that their edges have a direction. They will not be encountered as the "basic objects" on which the problems are defined, but rather as "meta-structures" in which the directed edges represent ways to transform an object into another.

Definition 1.2 (Directed graph).

A directed graph is a couple of sets D = (V, A) such that all elements of A are couples of elements of V , that is, A ⊆ V × V . The elements of A are called the arcs of D and the elements of V are its vertices.

With this definition, the neighbours of a vertex u are split into two categories: these for which (u, v) ∈ A, called its out-neighbours, and those such that (v, u) ∈ A, called its in-neighbours.

If there exists an oriented path -a sequence of vertices v 0 , v 1 , . . . , v k such that for any 1 ⩽ i ⩽ k, (v i-1 , v i ) ∈ A -between any two vertices of D, then D is called strongly connected.

Now that all the necessary notions are defined, let us have a closer look on the objects that will be of interest in the remaining of the present manuscript.

Some remarkable graph classes

In this thesis, we are particularly interested in some well-known graph classes, namely chordal graphs, split graphs, and cographs. These have been well studied and characterised in the literature. In this section, we give the definitions of those graph classes.

Chordal graphs. Chordal graphs, also called triangulated graphs or sometimes rigid circuit graphs have been studied since the 1960s [START_REF] Dirac | On rigid circuit graphs[END_REF]. They constitute a well-studied class of graphs since they arise in many practical applications [START_REF] Carmeli | Efficiently enumerating minimal triangulations[END_REF][START_REF] Córdoba | On generating random Gaussian graphical models[END_REF][START_REF] Charles | Algorithmic graph theory and perfect graphs[END_REF][START_REF] Parra | Characterizations and algorithmic applications of chordal graph embeddings[END_REF].

Definition 1.3 (Chordal graphs).

A graph is chordal if it does not contain any induced cycle of length 4 or more.

GRAPHS AND PROPERTIES | 19

In other words, every cycle of length more than 3 of a chordal graph has at least one chord (i.e. an edge that connects non-consecutive vertices of the cycle). Equivalently, any induced cycle of a chordal graph has length 3. These are simply reformulations of the definition of chordal graphs.

Note that, since removing vertices cannot create long induced cycles, chordal graphs form a hereditary graph class.

A chordal graph is represented in Figure 1.2. The obstructions of chordal graphs are the long induced cycles, as shown on the right. Chordal graphs benefit from characterisations of various types. For example, and perhaps most importantly, it has been shown by Dirac in 1961 that any chordal graph has at least two simplicial vertices, that is, vertices whose neighbourhoods induce a clique [START_REF] Dirac | On rigid circuit graphs[END_REF]. The simplicial vertices are identified on the graph of Figure 1.2. Since the class of chordal graphs is hereditary, this implies that simplicial vertices can be recursively removed from a chordal graph until there is no vertex left. This gives an ordering on the vertices of the graph, called a perfect elimination ordering. In fact, chordal graphs are exactly the graphs in which such an ordering exists. Because of the existence of a perfect elimination ordering, it has been shown that chordal graphs can be recognised in linear time [START_REF] Tarjan | Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs[END_REF].

Several other characterisations are known for chordal graphs. To cite a few of them, chordal graphs can be seen as intersection graphs of paths in a tree [START_REF] Gavril | The intersection graphs of subtrees in trees are exactly the chordal graphs[END_REF], or characterised in terms of minimal clique separators [START_REF] Dirac | On rigid circuit graphs[END_REF].

Chordal graphs possess some very interesting properties. Indeed, several problems that are usually hard on general graphs (e.g. graph colouring) become polynomial on chordal graphs [START_REF] Charles | Algorithmic graph theory and perfect graphs[END_REF]. On top of that, chordal graphs are closely connected to an important graph parameter called treewidth and its associated tree-decomposition introduced independently by Halin [START_REF] Halin | S-functions for graphs[END_REF] and Robertson & Seymour [START_REF] Robertson | Graph minors. iii. planar tree-width[END_REF].

A tree-decomposition of a graph G is a tree whose vertices are sets of vertices of G, called the bags of the decomposition. Moreover, it is required that each vertex appears

| GRAPHS, COMPLETIONS AND DELETIONS

in at least one bag, for each edge there exists a bag containing its two endpoints, and for any vertex v of G, the subgraph induced by the bags containing v is a tree. Chordal graphs have been characterised as the graphs for which there exists a tree-decomposition whose bags all induce cliques in the original graph [START_REF] Gavril | The intersection graphs of subtrees in trees are exactly the chordal graphs[END_REF][START_REF] Robertson | Graph minors. iii. planar tree-width[END_REF]. For chordal graphs, such a decomposition is called clique tree. The clique tree associated with the graph of Figure 1.2 is shown in the middle.

Split graphs. The class of split graphs was introduced in the 1970s by Foldes & Hammer [START_REF] Foldes | Split graphs[END_REF]. It is a well-studied subclass of chordal graphs [START_REF] Foldes | Split graphs having dilworth number two[END_REF][START_REF] Charles | Algorithmic graph theory and perfect graphs[END_REF][START_REF] Peter | The splittance of a graph[END_REF][START_REF] Merris | Split graphs[END_REF]. Its definition is the following.

Definition 1.4 (Split graphs). A graph G is split if its vertex set can be partitioned in

K + S where K is a clique of G and S is a stable set of G. The partition K + S is called a split partition of G.
As a direct consequence of the definition, the class of split graphs is self-complementary, meaning that for any split graph G, its complement G is also split. Moreover, split graphs form a hereditary graph class.

Note that the split partition of a split graph is not necessarily unique. Indeed, a vertex belonging to the clique but with no neighbour in the stable set could as well be placed in the stable set. Conversely, a vertex in the stable set that is adjacent to every vertex of the clique can be transferred to the clique without any consequence. Such a situation is illustrated in Figure 1.3, where the coloured vertex can be placed in any set of the split partition. The class of split graphs benefits from various characterisations [START_REF] Foldes | Split graphs[END_REF]. Among other ones, split graphs correspond exactly to chordal graphs whose complement is also chordal. Moreover, they have been characterised by forbidden induced subgraphs, namely as (C 4 , 2K 2 , C 5 )-free graphs. These obstructions are shown on the right of Figure 1.3. Finally, split graphs can be recognised in polynomial time by looking only at the degrees of their vertices [START_REF] Peter | The splittance of a graph[END_REF].

GRAPHS AND PROPERTIES | 21

Cographs. The class of cographs was introduced in the 1970s by several authors under various names such as hereditary Dacey graphs or D * -graphs [START_REF] Heinz | On a class of posets and the corresponding comparability graphs[END_REF][START_REF] Sumner | Dacey graphs[END_REF]; since then, this class has been widely studied and characterised [START_REF] Corneil | Complement reducible graphs[END_REF][START_REF] Corneil | A linear recognition algorithm for cographs[END_REF][START_REF] Crespelle | Faster and enhanced inclusion-minimal cograph completion[END_REF][START_REF] Habib | A simple linear time algorithm for cograph recognition[END_REF]. In particular, Corneil, Lerchs & Stewart [START_REF] Corneil | Complement reducible graphs[END_REF] provided some very useful characterisations of cographs. One of the many equivalent definitions of cographs is the following.

Definition 1.5 (Cographs). The class of cographs is defined recursively:

• a single-node graph is a cograph;

• if G 1 and G 2 are cographs, then their disjoint union G 1 ∪ G 2 is also a cograph; • if G is a cograph, then its complement G is also a cograph.
First, remark that the class of cographs is hereditary. By definition, this class is also self-complementary.

Cographs have been characterised as the graphs that do not contain any P 4 -that is, a path on four vertices -as an induced subgraph. Moreover, graphs in this class benefit from a unique tree representation, the cotree [START_REF] Corneil | Complement reducible graphs[END_REF]. The cotree associated with a cograph is a rooted tree whose leaves are exactly the vertices of the cograph, and whose internal nodes are labelled either 0 or 1. Then, two vertices are connected in the cograph if and only if the least common ancestor2 of the corresponding leaves in the cotree is labelled 1. Thanks to this representation, it has been proved that cographs can be recognised in linear time [START_REF] Corneil | A linear recognition algorithm for cographs[END_REF]. A cograph with its associated cotree is illustrated in Figure 1.4, where two pairs of twin vertices are identified. It has also been proved that in a cograph, there always exist two (true or false) twin vertices [START_REF] Corneil | Complement reducible graphs[END_REF]. Even more, all cographs can be constructed by beginning with a single vertex and recursively adding a true or false twin to an already existing vertex. This provides what we call a twin construction ordering on the vertices of a cograph.

We call induced sub-cograph of G an induced subgraph that is also a cograph; it is moreover maximal if it is inclusion-wise maximal among all induced sub-cographs of G.

Threshold graphs. Threshold graphs were introduced in 1977 by Chvátal & Hammer [21] as the set of graphs such that there exists a real number b and a weight function w : V → R such that for any subset X of vertices, X is a stable set if and only if v∈X w(v) ⩽ b. This rather complicated definition was motivated by applications to integer programming, and gave its name to the corresponding class of graphs: the number b can be seen as a threshold value for the existence of edges.

In the same paper [START_REF] Chvátal | Aggregations of inequalities. Studies in Integer Programming[END_REF]Theorem 1], this class of graphs has been characterised by a recursive construction involving isolated vertices -vertices that have no neighbour in the graph -and universal vertices, whose closed neighbourhood is the entire graph. We give here this characterisation as a simpler definition for the class of threshold graphs.

Definition 1.6 (Threshold graphs). A graph is threshold if it can be constructed from the empty graph by recursively adding isolated or universal vertices.

Threshold graphs are at the intersection between split graphs and cographs. Therefore, they are characterised by forbidden induced subgraphs as the class of (P 4 , C 4 , 2K 2 )free graphs. A threshold graph is can be seen in Figure 1.5, and the obstructions are also represented. The class of threshold graphs is quite common in the literature; see for example the chapter dedicated to it in Golumbic's book [START_REF] Charles | Algorithmic graph theory and perfect graphs[END_REF]. Like the split and cograph properties, the threshold property is hereditary and closed under complement. Moreover, like split graphs, threshold graphs can be recognised in linear time through their degree sequences [START_REF] Peter | The splittance of a graph[END_REF]. Finally, note that the construction of a threshold graph by adding isolated and universal vertices naturally implies an ordering on its vertex set, that is called the threshold construction ordering.

MINIMAL COMPLETIONS AND DELETIONS | 23

A recap of the inclusions between the four graph classes presented in this section is given in Figure 1.6. A graph class is above another if it is larger, and the arcs are directed towards the smallest class. For the sake of completeness, the class of Trivially Perfect graphs, corresponding to the intersection between cographs and chordal graphs, is also represented on the picture. All the graph classes considered here are hereditary, and the coloured ones are self-complementary in addition.

Minimal completions and deletions

Given an arbitrary graph G, there is no reason for it to fulfil a given property P. Then, one of the questions we address is about computing induced subgraphs of G which satisfy P. When the property is hereditary, finding such an induced subgraph is very easy: for example, the single-node graph is a trivial solution. However, finding such trivial solutions is not really satisfactory: we want to preserve somehow the structure of G, and find an induced subgraph that satisfies P and is "as close as possible" to G.

In other words, we want to remove as few vertices as possible from G in order to make the graph fulfil property P.

Unfortunately, finding the minimum number of vertices that have to be removed from G is in general a hard problem. This problem, known as the node-deletion problem has been shown to be NP-complete for most hereditary properties [START_REF] Lewis | The node-deletion problem for hereditary properties is NP-complete[END_REF].

The other problem in which we are interested here is that of computing edgesubgraphs (resp. supergraphs) of G that satisfy P and are "close" to G. Like the previous one, this problem corresponds to removing (resp. adding) as few edges as possible from G to make the graph satisfy P. Less general complexity results are known for the computation of the minimum number of edges that must be removed from (resp. added to) G in order to obtain a graph fulfilling P, but some have been proved in special cases. In fact, there are several properties for which this problem is also NP-complete [START_REF] Yannakakis | Computing the minimum fill-in is NP-complete[END_REF][START_REF] Charles Golumbic | Graph sandwich problems[END_REF], for example when the property under consideration is being chordal, as studied in Chapters 5 and 6.

Since the problem of finding the minimum number of elements (vertices or edges) that must be removed to make a graph satisfy a given property is hard in general, let us focus on the easier task of finding such a set of elements that is minimal for inclusion. If such a set is of minimum cardinality, it is necessarily also minimal for inclusion. This is why all over this thesis, minimal (resp. maximal) will always refer to inclusion-wise minimal (resp. maximal), and never to minimum (resp. maximum) cardinality.

We introduce here the objects studied in all the sequel: minimal P-completions and deletions, and maximal induced P-subgraphs of a graph G = (V, E).

Let P be a graph property. An induced subgraph G[X] of G, on the vertex set X, that verifies P is called an induced P-subgraph of G. It is maximal if for any subset of vertices Y ⊆ V , if X ⊊ Y then G[Y ] does not fulfil the property P. By abuse of language, we will often identify an induced P-subgraph G[X] with its set of vertices X.

A graph H is a P-edge-subgraph of G, also called a P-deletion of G, if it is an edge-subgraph of G and it fulfils property P. It is called a maximal P-edge-subgraph, or a minimal P-deletion, if it is inclusion-wise maximal, that is to say there is no

P-edge-subgraph H ′ of G such that E(H) ⊊ E(H ′ ) ⊆ E(G). If E is a subset of edges of G,
we might by abuse of language call E ′ a deletion of G, referring to the graph (V (G), E ′ ), thus identifying a deletion of G with its edge set.

Similarly, a graph H is a P-edge-supergraph of G, also called a P-completion of G, if it is an edge-supergraph and G and it fulfils property P. It is called a minimal P-edge-supergraph of G, or a minimal P-completion, if it is inclusion-wise minimal: there is no

P-supergraph H ′ of G such that E(G) ⊆ E(H ′ ) ⊊ E(H). The edges uv belonging to H but not to G, that is, uv ∈ E(H) \ E(G)
, are called the fill edges of the completion. Similarly as for deletions, completions will often be identified with the set of fill edges they induce.

When P refers to being in some known class of graphs, say being a split graph, we will omit the hyphen and simply say: a split edge-subgraph, a split deletion, a minimal split completion, and so on.

In general, when P is satisfied by all stable sets -as it is the case for the property of being chordal, split, cograph, or threshold -, we are ensured that a P-deletion exists

MINIMAL COMPLETIONS AND DELETIONS | 25

for any input graph. It makes sense in this case to look for an algorithm computing the minimal P-deletions of G without any restriction on G. Conversely, if P is verified by all cliques, then a P-completion exists for any graph G, in which case we look for an algorithm computing the minimal P-completions of G without any restriction on G.

Let us illustrate these notions in the particular case when P denotes the class of split graphs. In Figure 1.7, a graph is represented with a minimal split completion, a (non-minimal) split deletion, and a maximal induced split subgraph. Many classical problems on graphs are hard in general, but can be solved by polynomial algorithms as long as the input graph belongs to an appropriate graph class. This is for example the case for the maximum clique problem, asking for the size of the biggest clique in the graph, or for the colouring problem: both are proved to be NP-hard (see the excellent book by Garey & Johnson [START_REF] Garey | Computers and intractability: a guide to the theory of np-completeness[END_REF] for more NP-hardness and NP-complete information), but become polynomial on chordal graphs and all their subclasses [START_REF] Charles | Algorithmic graph theory and perfect graphs[END_REF]. In this kind of situation, completions and deletions turn out to be a useful tool.

Consider a problem that is hard in general but can be solved in polynomial time on a certain graph class P. For a graph G, if it does not already fulfil the property P, the idea is to compute a minimal P-completion (or a minimal P-deletion, depending on what is considered) of G and solve the problem in polynomial time on this new graph. Of course, the solution obtained this way is maybe not the real solution of the problem on input G, but it can be seen as an "approximation" -without any guarantees, though -of the real solution, that can be found in polynomial time.

When it comes to more structural aspects of graph theory, some questions about graph decompositions can be addressed. In fact, some well-known graph decompositions are defined from the graph classes themselves. The most well-known example of this is certainly the tree-decomposition. Since this decomposition is closely related to a very important graph parameter called treewidth, it permits to solve a large number of problems in polynomial time on chordal graphs, provided that the "width" is bounded. Some other graph parameters are strongly linked to graph properties: let us cite the treedepth and the class of Trivially Perfect graphs -which correspond to chordal cographs -or the twin-width, closely related to cographs.

Because it is usually hard to know exactly how many fill edges are required in order to give the appropriate property to an input graph, being able to compute minimal completions into the appropriate class would be very useful. Indeed, it is easier to compute a decomposition for a completed graph, and consider it as a decomposition, maybe not optimal, of the input graph.

Another motivation of the study of completions and deletions in a given graph class is the structure present in many real-world datasets. Some of them have a structure that is very close to an existing and well-studied graph class such as cographs [START_REF] Crespelle | Faster and enhanced inclusion-minimal cograph completion[END_REF]. It is of interest to know how far these graphs acquired through real data are from the considered graph class: once again, this is a difficult problem that can be "approximated" by completions and deletions. Graph completions into a property could also be used to repair a graph that was known to have this specific property, but has been transferred via a communication network in which some information has been lost.

Graph completions and deletions are in fact particular cases of the more general framework of graph modification problems. Another problem that is often studied in this framework is the graph edition problem. Computing an edition of a graph G into a class P consists in finding a set of two-element subsets of its vertex set V , that can be edges or not, that have to be modified in order to make G obtain the property P. The considered modification is a very simple one: for u, v ∈ V , if uv is an edge in G, then it is removed, else it is added to E. Like completions and deletions, the graph editions that are studied in practice are often the ones that are minimal for inclusion, that is to say, for which the set of modifications is minimal with respect to inclusion [START_REF] Natanzon | Complexity classification of some edge modification problems[END_REF].

Although convinced of the interest of graph edition problems [START_REF] Crespelle | Linear-time minimal cograph editing[END_REF][START_REF] Eiben | A polynomial kernel for paw-free editing[END_REF], we will not investigate them further in this thesis. Their nature is slightly different from that of the two other graph modification problems, and very little is known about graph editions in the world of enumeration. Anyway, we will focus here on the graph completions and deletions problems.

Chapter 2 Enumeration problems on graphs

This chapter is intended as an introduction to enumeration problems and the measure of their complexities. Other sources of interest on this topic include (but are not limited to) the works of Defrain [START_REF] Defrain | On the dualization problem in graphs, hypergraphs, and lattices[END_REF], Mary [START_REF] Mary | Énumération des dominants minimaux d'un graphe[END_REF], and Strozecki [START_REF] Strozecki | Enumeration complexity and matroid decomposition[END_REF][START_REF] Strozecki | Enumeration complexity[END_REF]. We give here some elements to state our problems in the context of enumeration.

T he graph problems in which we are interested are part of the more general family of enumeration problems. Therefore, let us first have a closer look on this special kind of problems, their definition, and the ways to measure the complexity of the corresponding algorithms. Then, we will have an overview of the existing efficient enumeration techniques. In the last section of the present chapter, we state more precisely which type of problems will be studied.

Definitions and models

In this section, we present more formally the general concepts and the specificities of enumeration.

Enumeration problems: definition

Let X be a set and R be a binary relation on X. For one x ∈ X, called the input or instance, let us denote by R(x) := {y ∈ X | (x, y) ∈ R} the set of all y such that (x, y) ∈ R. The elements of R(x) are called solutions, or outputs.

Definition 2.1 (Enumeration problem).

The enumeration problem associated with the binary relation R on X takes in input an x ∈ X, and outputs the set R(x).

An algorithm which solves an enumeration problem is called an enumeration algorithm. More precisely, an enumeration algorithm called on an input x outputs an ordered sequence y 1 , . . . , y N such that {y 1 , . . . , y N } = R(x). In particular, enumeration algorithms generate each solution of the problem exactly once.

It is worth noticing that enumeration generalises recognition: we must be able to certify that all outputs are indeed solutions. This is why we will focus on problems for which recognition is possible in polynomial time.

Computational model. The computational model we use is the Random Access Machine (RAM) model, equipped with the four basic operations (comparison, addition, subtraction, multiplication), and a special instruction output(i,j) -different from the classical return instruction -which displays the content of registers R i , R i+1 , . . . , R j in constant time without stopping the computation. This is the model commonly used for enumeration problems [START_REF] Bagan | Algorithms and complexity of enumeration problems for the evaluation of logical queries[END_REF][START_REF] Defrain | On the dualization problem in graphs, hypergraphs, and lattices[END_REF][START_REF] Strozecki | Enumeration complexity and matroid decomposition[END_REF][START_REF] Strozecki | Enumeration complexity[END_REF]. In particular, it permits to access an exponential amount of memory in polynomial time, using the appropriate dictionary data structures.

Complexity of enumeration algorithms

Given an enumeration problem, the number of solutions that have to be outputted can be very large. Indeed, it is not rare for such a problem to admit an exponential number of solutions. To cite a simple example, it has been shown that a graph on n vertices can have as many as 3 n/3 inclusion-wise maximal stable sets [START_REF] Moon | On cliques in graphs[END_REF]. In such a case, we still want to generate all solutions in a reasonable time, but there is obviously no hope for outputting an exponential number of objects in polynomial time, since we need at least the time of writing them. It is therefore no longer relevant to measure the running time of an enumeration algorithm with the classical complexity classes such as P or NP. Knowing this, how can we adapt the notion of efficiency to an algorithm which outputs a potentially exponential number of solutions?

To answer this question, two main approaches have been proposed in the literature. One of them, called input-sensitive, consists in finding the fastest possible exact exponential algorithms, since the considered problems are exponential in the input size. The other one, output-sensitive, assumes that, since all solutions have to be generated anyway, a good measure of efficiency for enumeration algorithms should take this into account. The two approaches give results of different types, and in that sense they are complementary.

In this thesis, we will always measure the complexity in an output-sensitive way. However, for the sake of completeness, both approaches are mentioned here.

Input-sensitive approach. This approach consists in measuring the running time of enumeration algorithms in terms of the input size only. In this case, algorithms usually

DEFINITIONS AND MODELS | 29

run in exponential time, and research typically focuses on lowering the exponent.

Since the running time of an enumeration algorithm is necessarily lower-bounded by the number of solutions, expressing its complexity in terms of the input size can give useful insights for the number of solutions that have to be outputted. In fact, many known input-sensitive enumeration algorithms were obtained by bounding tightly the number of objects to enumerate [START_REF] Moon | On cliques in graphs[END_REF][START_REF] Couturier | Minimal dominating sets in graph classes: combinatorial bounds and enumeration[END_REF]. Another advantage of measuring the complexity of enumeration algorithms in terms of the input size only is to give guarantees on the total running time.

However, if the number of solutions to output is exponentially larger than the input size, an enumeration algorithm will not be considered "efficient" in the usual sense, even if it needs a constant time per solution. Indeed, knowing that there exists an exponential enumeration algorithm gives in fact no insight on the real efficiency of the algorithm: is it exponential in the input size because there is an exponential number of solutions, or is it exponential in the number of solutions?

In this sense, the input sensitive-approach seems therefore not the most satisfactory to capture the notion of efficiency for enumeration algorithms.

Output-sensitive approach. The output-sensitive approach is based on the idea that complexity measures for enumeration problems need to take into account the potentially large number of solutions they can have. To measure its efficiency, the running time of an algorithm is then bounded by a function of the input size n and the number N of solutions. Since the output-sensitive complexity measures take into account the large number of solutions, they allow us to capture a notion of running time per solution and to compare the complexities of two problems that do not possess the same number of solutions. This is the point of view adopted in all the remaining of this thesis: all algorithms presented here have their complexities measured in terms of the input size and the output size.

When dealing with enumeration, as for many other domains, our aim is to design efficient algorithms. In classical complexity theory, the algorithms that are regarded as "efficient" are polynomial algorithms. This raises a question: since polynomial algorithms have no sense in general for enumeration, how can we capture the essence of efficiency in this case? To answer this question, three complexity measures have been proposed by Johnson, Yannakakis & Papadimitriou in the 1980s [START_REF] Johnson | On generating all maximal independent sets[END_REF].

Output-polynomial. An algorithm is said to be output-polynomial if its total running time is bounded by a polynomial both in the input size n and the number of solutions N that have to be outputted. This ensures every solution will eventually be generated in a reasonable amount of time. This complexity measure is also called "Polynomial total time". It is the natural translation of polynomial time complexity into the field of enumeration problems. An illustration of the running time of an output-polynomial algorithm is presented in The issue with output-polynomial algorithms is mostly that there is no guarantee on the time needed to generate the first solution. A large amount of time (polynomial in N but still exponential in the input size n) could be necessary before outputting just one solution, which may not be satisfactory for many practical cases. We try to highlight this phenomenon on Figure 2.1.

Incremental-polynomial.

To guarantee a fast access to the first generated solutions, the time needed by an incremental-polynomial algorithm to output a solution is polynomial in the input size n and the number of solutions already found. In other words, for each i ⩽ N , the time needed between the ith solution and the next one is bounded by a polynomial in n and i. To help the reader visualise the behaviour of an incremental-polynomial algorithm in terms of running time, it is schematised in Figure 2.2.

start end first solution last solution

i i + 1
poly(n, i) Incremental-polynomial algorithms are obviously output-polynomial. However, an incremental-polynomial algorithm ensures in addition that solutions will be outputted all along the execution, and not only at the end, as it could be the case for output-polynomial algorithms. Moreover, with such an algorithm the first solutions are outputted quickly, even if the computation of the following ones Necessarily, polynomial delay algorithms are incremental-polynomial, and therefore output-polynomial, linear in the number of solutions. The main advantage of polynomial delay algorithms is to completely remove the dependence on the number of solutions already found. This way, solutions are outputted quickly all along the algorithm's execution.

The inclusions between the three historical complexity classes that have just been presented are schematised in Figure 2.4. But these complexity measures are not the only ones that are considered in practice. In fact, polynomial delay is not the best complexity we could hope for in all cases. For some problems, polynomial delay could even be lowered to constant delay, meaning that the time needed between two consecutive outputs is bounded by a constant. This complexity cannot be achieved for all problems [START_REF] Strozecki | Enumeration complexity[END_REF], but sometimes the problem's structure allows to use a particularly well-suited enumeration technique, such as Gray codes.

When the solutions can be represented as words on a finite alphabet, it is possible to enumerate them via Gray codes. The idea of enumeration with Gray codes is to generate all the solutions in such a way that the number of different characters between two consecutive solutions is exactly one. Therefore, in such a case it is not even necessary to output the whole new solution when one is found, because outputting the difference with the previous one suffices, thus achieving constant delay for problems that have solutions of polynomial size. Moreover, it is only necessary to keep in memory the last generated solution, hence using only polynomial space.

Gray codes have been introduced for the first time in 1941 as reflected binary codes in order to enumerate binary integers on n bits [START_REF] Stibitz | Binary counter[END_REF], but they can also be used to enumerate such various objects as subsets of a given set, permutations of a set [START_REF] Selmer | Generation of permutations by adjacent transposition[END_REF], or configurations of Hanoi Towers. Many more applications of Gray codes can be found in Ruskey's (unpublished) book [START_REF] Ruskey | Combinatorial generation[END_REF].

Gray codes are not the only mean to achieve constant delay for a given problem. Let us mention briefly the Fisher-Yates shuffle [START_REF] Durstenfeld | Algorithm 235: random permutation[END_REF], with its constant-delay variant, for the generation element by element of a random permutation. This technique is especially used for generating a permutation α of a large set [START_REF] Carmeli | Answering (unions of) conjunctive queries using random access and random-order enumeration[END_REF]. With this method, for any i, the time needed between the output of α(i) and α(i + 1) is constant.

We have surveyed some of the most classical output-sensitive complexity measures. In fact, many more notions exist for output-sensitive algorithms [START_REF] Creignou | A complexity theory for hard enumeration problems[END_REF][START_REF] Strozecki | Enumeration complexity[END_REF], but they will not be encountered here. Yet, we do not know output-polynomial algorithms for all enumeration problems. It is even proven that, unless P = NP, there are enumeration problems for which no such efficient algorithm can be found [START_REF] Capelli | Incremental delay enumeration: Space and time[END_REF][START_REF] Lawler | Generating all maximal independent sets: NP-hardness and polynomial-time algorithms[END_REF]. In some cases, what happens is that there exists a polynomial number of "trivial" solutions, which can be found in polynomial time, but the time necessary to find another solution is exponential in the input size. This is for example the case with the so-called minimal rainbow induced subgraphs problem, taking in input a graph whose edges are assigned one or more colours and asking for the list of all minimal induced subgraphs containing at least an edge of each colour [START_REF] Durand | Workshop on graphs and databases, oral communication[END_REF]. In some instances, finding a non-trivial solution is equivalent to finding a truth assignment of a SAT formula, therefore impossible in polynomial time if P ̸ = NP.

An enumeration algorithm is said to be output-quasi-polynomial if it runs in total time O(2 polylog(n+N ) ), where n denotes the input size, and N the number of solutions.

DEFINITIONS AND MODELS | 33

When an output-polynomial algorithm cannot be found, it is often desirable to provide an output-quasi-polynomial algorithm that solves the problem [START_REF] Mary | Énumération des dominants minimaux d'un graphe[END_REF][START_REF] Defrain | On the dualization problem in graphs, hypergraphs, and lattices[END_REF].

Space complexity. The space complexity of enumeration algorithms is also a challenge: many enumeration techniques require to store the generated solutions in memory, in order to check if the newly discovered solution is really new, or if it has already been found in the past. In general, when the number of solutions is exponential, this naturally leads to exponential-space algorithms. However, in some cases it is possible to avoid storing all solutions in memory, therefore reducing the space complexity of the algorithm to make it polynomial in the input size.

Classical enumeration problems

Among all enumeration problems, some are widely known and studied, mostly because they are very general. These have been surveyed in previous work [START_REF] Mary | Énumération des dominants minimaux d'un graphe[END_REF]. We give here a brief overview of some of the most classical enumeration problems, without aiming at being exhaustive.

Independent set systems and dependent set systems. A set family I on a ground set E is called an independent set system if ∅ ∈ I and for any two I 1 , I 2 ⊆ E, if I 1 ∈ I and I 2 ⊆ I 1 , then I 2 ∈ I. In other words, an independent set system is a family of sets closed under inclusion.

Independent set systems are far from being rare in enumeration problems. In particular, many set families naturally have this property: in graphs, some very classical objects such as stable sets, cliques, or matchings define independent set systems. Due to their omnipresence, these set families are interesting objects to enumerate.

In fact, when dealing with independent set systems, it often suffices to generate all the independent sets that are inclusion-wise maximal, since all sets included in any of them are by definition elements of the family. It was shown by Lawler, Lenstra & Rinnooy Kan [START_REF] Lawler | Generating all maximal independent sets: NP-hardness and polynomial-time algorithms[END_REF] that in general, if the set system is given by a constant-time membership oracle, there does unfortunately not exist an output-polynomial algorithm enumerating all the maximal elements of an independent set system, unless P = NP. However, they also proved that such an algorithm exists for many practical particular cases, as it will be shown in the next section.

Independent set systems are closely related to dependent set systems, that are set families closed under taking supersets. In the case of dependent set systems, the interesting elements to enumerate are the inclusion-wise minimal sets belonging to the family. Some dependent set systems are very famous: dominating sets, Vertex Covers, transversals of an hypergraph. . . Enumeration of minimal transversals of an hypergraph. Hypergraphs are a generalisation of graphs with edges of arbitrary size. An hypergraph can be seen as a family of sets E, the hyperedges, on a set of vertices V . A transversal of an hypergraph H = (V, E) is a set of vertices T intersecting every hyperedge of H, that is to say, for any E ∈ E, T ∩ E ̸ = ∅. The transversals of an hypergraph are also referred to as hitting sets.

The associated enumeration problem is the following: given a hypergraph H, generate all minimal transversals of it. Equivalently, it is sometimes asked to return a hypergraph whose hyperedges are the minimal transversals of H. The minimal transversals enumeration problem is so general that numerous enumeration problems (corresponding to dependent set systems) can be seen as particular cases of it.

For example, the dominating sets of a graph G -the sets of vertices D such that every vertex belongs to D or has a neighbour in D -can be seen as the transversals of an hypergraph whose hyperedges are the closed neighbourhoods of all the vertices of G. Then, enumerating the minimal dominating sets of a graph [START_REF] Mamadou | On the enumeration of minimal dominating sets and related notions[END_REF] is a particular case of the minimal transversals enumeration. In another direction, we can look at the Feedback Vertex Set problem, which asks for the minimal sets of vertices whose removal makes the input graph acyclic. Then, enumerating all feedback vertex sets of G [START_REF] Schwikowski | On enumerating all minimal solutions of feedback problems[END_REF] is equivalent to enumerating all minimal transversal of the hypergraph on the vertex set V whose hyperedges are the sets of vertices inducing cycles in G.

The current best algorithm for the enumeration of minimal transversals of an hypergraph dates back to the 1990s. It is due to Fredman & Khachiyan [START_REF] Michael | On the complexity of dualization of monotone disjunctive normal forms[END_REF] and runs in output-quasi-polynomial time. Knowing if all minimal transversals of an hypergraph can be enumerated in output-polynomial time is a famous, long-lasting open question [START_REF] Eiter | Identifying the minimal transversals of a hypergraph and related problems[END_REF]. This question is in fact not restricted to hypergraphs: several formalisms capture the same problem [START_REF] Bioch | Complexity of identification and dualization of positive boolean functions[END_REF].

Algorithmic methods for enumeration

To generate all solutions of a problem, the principle is often to give a structure to the space of solutions, and then explore it. Each time a new solution is found, it is outputted. Sometimes, the structure is given to the space of solutions via ad-hoc methods. This is for example the case with the ingenious algorithm proposed by Carmeli et al. [START_REF] Carmeli | Efficiently enumerating minimal triangulations[END_REF] to generate all minimal chordal completions of a graph. In Chapter 3, we will give another, simpler example of such an ad-hoc algorithm when enumerating minimal split completions. However, there also exist generic methods that can apply to a wide range of problems. Some of these general frameworks are known to give good complexity results, but they are not always applicable. Among the most popular techniques used to devise enumeration algorithms, let us cite Flashlight Search, maximal independent set generation, the Input Restricted Problem approach, Reverse Search, and Proximity

ALGORITHMIC METHODS FOR ENUMERATION | 35

Search.

In the whole section, we state a general enumeration problem as follows: given a ground set E, with n = |E|, and a property P, generate all (inclusion-wise maximal) subsets of E which satisfy property P.

Flashlight Search

When dealing with (maximal) subset enumeration, a classical technique sometimes called Backtrack [START_REF] Read | Bounds on backtrack algorithms for listing cycles, paths, and spanning trees[END_REF], Binary Partition [START_REF] Conte | Enumeration of Maximal Common Subsequences Between Two Strings[END_REF][START_REF] Mamadou | On the enumeration of minimal dominating sets and related notions[END_REF], or Flashlight Search [START_REF] Capelli | Enumerating models of DNF faster: breaking the dependency on the formula size[END_REF][START_REF] Capelli | Geometric amortization of enumeration algorithms[END_REF] naturally arises. Let us insist here on the fact that the property P under consideration -as it will always be the case in the present work -is hereditary.

The Flashlight algorithm consists in choosing an arbitrary ordering e 1 , . . . , e n on the elements of E, and considering them in order. To begin, we have to decide whether there exists a solution containing e 1 , and if there exists a solution excluding e 1 . Then, each time a solution S exists up to elements e 1 , . . . , e i , we have to decide if there exists a solution compatible with S and containing e i+1 , and a solution compatible with S and excluding e i+1 . If not, the branch is no longer explored. This way, we build a binary tree rooted at ∅ such that each internal node at level i represents a subset of {e 1 , . . . , e i } satisfying P, and the leaves correspond exactly to the maximal solutions. An example of the tree explored by Flashlight Search is presented in Figure 2.5. The tree is searched while being constructed, outputting a solution each time a new one is found. The decision problem solved at each step of the computation is called an extension problem. Flashlight Search is a powerful technique: if the extension problem is solvable in polynomial time, it yields a polynomial delay algorithm for the enumeration of all (maximal) subsets of E satisfying P [START_REF] Read | Bounds on backtrack algorithms for listing cycles, paths, and spanning trees[END_REF]. Unfortunately, the extension problems associated with enumeration problems are not polynomial in general: they will be addressed in detail for maximal subgraphs in Chapter 4.

When this technique was introduced by Read & Tarjan [START_REF] Read | Bounds on backtrack algorithms for listing cycles, paths, and spanning trees[END_REF], it was used for example to enumerate all spanning trees of a connected graph. Indeed, knowing if a set of edges can be extended into a spanning tree is rather easy. In fact, it suffices to check if this set of edges induces an acyclic graph: if not, it cannot be extended into a spanning tree. Forbidding some edges to belong to a solution does not make the problem much harder, as we will see in Chapter 4. Consequently, Flashlight Search yields a polynomial delay polynomial space algorithm for the enumeration of spanning trees of a connected graph.

Maximal subgraphs are not the only application of Flashlight Search: due to its generality, this technique can be applied to many different problems. For example, it is used to enumerate efficiently the truth assignments of a logic formula under certain conditions [START_REF] Capelli | Enumerating models of DNF faster: breaking the dependency on the formula size[END_REF].

Maximal independent set generation

The goal here is to generate all inclusion-wise maximal elements of an independent set system. If P is a hereditary property, that is, closed under inclusion, then the family of all subsets of E satisfying P is an independent set system I. Generating all maximal subsets of E satisfying P is thus the same as generating the maximal elements of I.

Let us take a look on a technique designed by Lawler, Lenstra & Rinnooy Kan [START_REF] Lawler | Generating all maximal independent sets: NP-hardness and polynomial-time algorithms[END_REF] to enumerate all maximal elements of an independent set system, generalising the work of Paull & Unger [START_REF] Paull | Minimizing the number of states in incompletely specified sequential switching functions[END_REF]. They assume that the set family under consideration is given by a membership oracle -a function answering true on a set if it belongs to the independent set system, false otherwise -whose running time is denoted by c. Then, if the ground set is arbitrarily ordered E = {e 1 , e 2 , . . . , e n }, the algorithm proceeds incrementally, following the ordering. For any i ⩽ n, denote by I i the family of all independent sets included in {e 1 , . . . , e i }. They prove the following theorem.

Theorem 2.2 ([62], Theorem 4).

It is possible to enumerate the maximal elements of an independent set system I in total time polynomial in n, N and c, provided that for any j ⩽ n, and for any I ∈ I j-1 , the maximal independent sets of I ∪ {e j } can be found in polynomial time.

The general algorithm they give for maximal independent set generation is presented here as Algorithm 2.1. If it is possible to generate all maximal independent sets of I ∪ {e i } in polynomial time (line 12), then this Algorithm runs in polynomial total time O(ncN +n 2 cN 2 +n 2 N 3 ) [START_REF] Lawler | Generating all maximal independent sets: NP-hardness and polynomial-time algorithms[END_REF]. However, this classical algorithm needs a time polynomial in N to output a first solution. Therefore, its time complexity is output-polynomial but not incremental-polynomial.

Due to the large presence of independent set systems among optimisation problems, the method introduced by Lawler, Lenstra & Rinnooy Kan can be used in various contexts. For example, it permits to generate all maximal feasible solutions to a

ALGORITHMIC METHODS FOR ENUMERATION | 37

Reverse Search

In 1992, Avis & Fukuda [START_REF] Avis | Reverse search for enumeration[END_REF] designed a general framework for enumeration problems, called Reverse Search. At the time, several works on enumeration were using similar techniques. For example, the well-known algorithm of Tsukiyama et al. for the enumeration of maximal cliques of a graph [START_REF] Tsukiyama | A new algorithm for generating all the maximal independent sets[END_REF] and the algorithm of Johnson et al. for the enumeration of maximal elements of an independent set system with polynomial delay [START_REF] Johnson | On generating all maximal independent sets[END_REF] used similar methods. Those techniques were designed to improve the existing ones such as the maximal independent set generation of Lawler et al. [START_REF] Lawler | Generating all maximal independent sets: NP-hardness and polynomial-time algorithms[END_REF]. When Reverse Search was made explicit, it unified these frameworks.

Reverse Search is designed explicitly for polynomial delay and polynomial space. It is the "reverse" approach of local search, a technique often used in optimisation which consists in navigating the space of solutions, transforming a solution into a better one with local changes, until a local optimum is found. The principle of Reverse Search is the following: build a rooted spanning arborescence on the solution space by defining for each solution S its parent Parent(S), and explore the arborescence in a DFS manner, keeping in memory the parent of the current solution. The function Parent is therefore defined on the solution space, apart from the root(s). To illustrate the idea, let us take a look at Figure 2.6. More precisely, the arborescence is defined by the following information:

S 0 S 1 S 3 S 2 S 4 S 5 S 0 , S 1 , S 4 , S 2 , S 5 , S 3
• a root solution S 0 (or a set of root solutions if the arborescence is a forest rather than a tree);

• a function neighbours for generating in polynomial time all neighbouring solutions of the current one in the solution space: in Avis & Fukuda's original paper [START_REF] Avis | Reverse search for enumeration[END_REF], the neighbours of a solution are computed by the LocalSearch procedure;

• a function Parent to decide for each solution which one is its parent, with the property that following the parent relation, one will eventually reach S 0 (or any root solution). This Parent function allows us to define for each solution S the set of its children, that is,

Children(S) = {S ′ ∈ neighbours(S) | Parent(S ′ ) = S}.
Note that the children of a solution form a subset of its neighbours. Since each solution (except the root) has one parent, the previous requirements ensure that each solution is generated at most once.

ALGORITHMIC METHODS FOR ENUMERATION | 39

The general Reverse Search algorithm is quite simple: it is presented here as Algorithm 2.2. Delay. If the set of children of a solution can be computed in polynomial time (in particular, if any solution has a polynomial number of neighbours), then Algorithm 2.2 has polynomial delay. But to guarantee this delay, we need to be careful about outputting the solutions at the right time.

When exploring the solution space with the Parent relation, one may have to explore a path whose length is exponential in the input size. Therefore, if each new solution is outputted at the time it is found, then it might be necessary to backtrack during an exponential time when the whole branch has been explored. This leads to an exponential delay between two solutions, which is not very efficient. However, a classical trick, sometimes called the Alternative Output Method [START_REF] Uno | Two general methods to reduce delay and change of enumeration algorithms[END_REF] is to output the new solutions at the beginning of the recursion step if the recursion depth is even (line 3), and at the end if the depth is odd. This way, the time spent between two consecutive solutions can be lengthened, but solutions are also outputted when backtracking the DFS, preventing the algorithm to run during an exponential time without producing any new solution.

Because the structure given to the solution space is an arborescence, it is no longer necessary to keep in memory all solutions that have already been found. Being able to compute the parent of each solution in polynomial time guarantees the knowledge of the current state. Since each solution (apart from the root solutions) has one parent, there is exactly one way to reach this solution by following the arborescence. Therefore, there is no need to check: whenever a new solution is generated, we know for sure it has never been outputted before. Hence, no memory is required to store an exponential number of solutions: Algorithm 2.2 runs in polynomial space.

The Reverse Search technique has proved efficient on a wide variety of problems. In their original article [START_REF] Avis | Reverse search for enumeration[END_REF], Avis & Fukuda already applied it in many situations, to enumerate such various objects as cells in an arrangement, topological orderings, or connected induced subgraphs. In fact, it is the reference technique when designing polynomial delay polynomial space enumeration algorithms [START_REF] Brosse | Polynomial delay algorithm for minimal chordal completions[END_REF][START_REF] Conte | Listing maximal subgraphs satisfying strongly accessible properties[END_REF].

For example, this method allows us to generate in polynomial delay and polynomial space all spanning trees of a connected graph [START_REF] Avis | Reverse search for enumeration[END_REF]. In this case, the root solution is the lexicographically smallest spanning tree, according to an arbitrary order on the edges. To generate a neighbour of a solution, it suffices to add an edge and break the cycle that has been created by removing another edge. Finally, the parent of a solution is defined as its lexicographically smallest neighbour.

In the same article, Reverse Search has also been used to enumerate efficiently all triangulations of a set of points in the plane: the neighbours of a solution are obtained by "flipping" an edge, that is, exchanging diagonals in a quadrilateral.

Input Restricted Problem

The problem considered here is the enumeration of maximal induced subgraphs of a graph G = (V, E), with n = |V |, that verify a hereditary property P. For this problem, Cohen, Kimelfeld & Sagiv [START_REF] Cohen | Generating all maximal induced subgraphs for hereditary and connected-hereditary graph properties[END_REF] devised an interesting framework. They manage to link the complexity of enumerating maximal induced subgraphs that verifies a hereditary property P to the complexity of a so-called Input Restricted Problem.

Given an induced subgraph H of G that satisfies P and an additional vertex v ∈ V not in H, the Input Restricted Problem consists in asking for the list of all maximal induced subgraphs of H + v fulfilling property P.

The idea behind this technique is a very classical one: starting from any solution of the problem, new solutions are found from the already generated ones. This way, an oriented supergraph of solutions is built, whose vertices are all the maximal induced subgraphs we want to enumerate, and an arc is put from a solution S to a solution S ′ if there exists a vertex v such that S ′ is obtained via a maximal induced P-subgraph of S + v. Since the property is hereditary, it is easy to find a maximal induced P-subgraph: it suffices to build it greedily, starting from the empty set and adding vertices in any order. One can then explore the supergraph of solutions while constructing it and output each new generated solution.

Suppose the Input Restricted Problem can be solved by a property-specific procedure genRestrHered(H, v), that outputs all the maximal induced P-subgraphs of H + v for any maximal induced P-subgraph H of G and any vertex v ∈ V not in H. Then, Algorithm 2.3 can be used to enumerate all the maximal induced P-subgraphs. Note that a maximal induced P-subgraph of H + v is not necessarily maximal in G: that is why it needs to be maximised (line 7) in order to find a solution. Since the property under consideration is supposed to be hereditary, a greedy maximisation is well-suited for this purpose. Function recursiveGen (G, H, S):

5 foreach v ∈ V (G) \ V (H) do 6 foreach H ′ ∈ genRestrHered (H, v) do 7
Maximise H ′ greedily within G;

8 if H ′ / ∈ S then 9
Output H ′ if recursion depth is even;

10 S := S ∪ H ′ ; 11 Call recursiveGen (G, H ′ , S); 12 Output H ′ if recursion depth is odd;
The Input Restricted Problem technique is different from the maximal independent set generation framework. For maximal independent set generation, the technique discussed above generates partial solutions all along the execution, and finds all the maximal independent sets at the same time at step n. On the other hand, in the algorithm proposed by Cohen et al. (here presented as Algorithm 2.3), when a new partial solution is found, it is immediately maximised with a greedy maximisation function, and outputted. This way, maximal induced subgraphs are produced all along the execution of the algorithm.

When guarantees are known on the complexity of genRestrHered, other complexity guarantees can be deduced for the whole enumeration algorithm. Based on this technique, the authors proved the following result.

Theorem 2.3 ([22]

). For all hereditary or connected-hereditary properties P, the maximal P-subgraphs can be enumerated:

• in output-polynomial time if and only if the input restricted problem can be solved in output-polynomial time;

• in incremental-polynomial time if and only if the input restricted problem can be solved in incremental-polynomial time;

• with polynomial delay if the input restricted problem can be solved in polynomial time.

The authors also prove results on space usage. In particular, for a hereditary property P, if the input restricted problem can be solved in polynomial space, then Algorithm 2.3 can be improved to run in polynomial space.

There are several "natural" problems for which the input restricted problem is polynomial. Let us cite for example the maximal clique enumeration problem. Given a maximal clique K of a graph G and a vertex v that does not belong to K, there are only two maximal cliques in the graph induced by K ∪ {v}. These are K and N K (v) ∪ {v} (which is a clique since all vertices are connected in K). Therefore, the input restricted problem has only two solutions and can be solved in time polynomial in the size of G: Theorem 2.3 ensures that all maximal cliques of G can be enumerated with polynomial delay. In this case, polynomial space is achieved as well.

The approach proposed by Cohen et al. is very efficient when it can be applied. However, it is not always the case that the input restricted problem is solvable in polynomial time (an example will be given in Chapter 5).

Proximity Search

Proximity Search has been recently introduced by Conte & Uno [START_REF] Conte | New polynomial delay bounds for maximal subgraph enumeration by proximity search[END_REF]. The main advantage of this technique is its generality. Proximity Search was designed explicitly for maximal subset enumeration, producing polynomial delay algorithms for a wide range of problems [START_REF] Conte | Proximity search for maximal subgraph enumeration[END_REF]. It overcomes some limitations of the Input Restricted Problem approach without giving such strong guarantees, in particular for space usage.

As several other enumeration paradigms [START_REF] Avis | Reverse search for enumeration[END_REF][START_REF] Cohen | Generating all maximal induced subgraphs for hereditary and connected-hereditary graph properties[END_REF], Proximity Search relies on an organised walk on the space of solutions. The general idea is very similar to the one used with the Input Restricted Problem, or with Reverse Search: build an oriented supergraph of solutions, whose vertices are the desired solutions of the problem, and arcs are put between them according to a problem-specific operation that permits us to transform a solution into some others in polynomial time. This transition function cannot be reversed in general.

The novelty of Proximity Search is the introduction of a proximity measure between two solutions, to provide the solution space with a metric, and be able to measure "how close" two solutions are. In order to define the proximity measure, solutions are considered here as ordered subsets of E. This allows us to consider the prefixes of a solution: if S = e 1 , . . . , e k is an ordered maximal subset of E satisfying property P, the prefixes of S are all the e 1 , . . . , e i for all i ⩽ k. Note that each solution has its own ordering, and two different solutions can have completely unrelated orderings a priori.

Definition 2.4 (Proximity).

The proximity S ∩ T between two solutions S and T is the longest prefix of T that is contained in S.

ALGORITHMIC METHODS FOR ENUMERATION | 43

This notion of proximity does not need to induce a distance in the mathematical sense1 because it is not symmetric in general, but it must satisfy the crucial property

|S ∩ S ′ | = |S ′ | ⇒ S = S ′ .
There are three major requirements to apply Proximity Search.

• An ordering scheme, that is, a function π which associates to each P-subset of E a total ordering of its elements. For a subset S ⊆ E, π(S) is called the canonical ordering of S.

• A function neighbours, computing all (out-)neighbours of a given solution in time polynomial in n. In particular, every solution must have a polynomial number of neighbours. This neighbouring function relies on a transition operation that, given a solution S, can produce other, different maximal P-subsets of E. In any case, the transition operation is highly specific to the considered problem.

• A maximisation function complete, taking in input a partial solution -a Psubset of E -and completing it into a maximal one. The use of that function is mostly hidden in the computation of neighbours. Therefore, the function complete needs to be computable in polynomial time.

The goal is then to show that the super-graph of solutions is strongly connected. To see this, it suffices to prove that for any given solution, the proximity to a target solution can be increased at each step. More precisely, given a solution S and a target solution S * , we want to prove that there exists another solution among the neighbours of S that has a higher proximity with S * . This way, the search is ensured to visit every solution at least once.

Definition 2.5 (Proximity searchable). Let us consider an enumeration problem, together with an ordering scheme π and a polynomial-time computable neighbouring function neighbours. The problem is called proximity searchable if one solution can be found in polynomial time and, given any two solutions S and S

* such that S ̸ = S * , there exists T ∈ neighbours(S) such that |T ∩ S * | > |S ∩ S * |.
Conte & Uno [START_REF] Conte | New polynomial delay bounds for maximal subgraph enumeration by proximity search[END_REF] proved that, if the problem of enumerating all maximal P-subsets of E is proximity searchable, then Algorithm 2.4 generates each solution exactly once and runs with polynomial delay using exponential space.

Note that being able to find one first solution in polynomial time is necessary to get a polynomial delay algorithm. One also needs to be able to check if a subset is a solution in polynomial time. Moreover, if exponential space is allowed, it is possible to test in time linear in |E| if a solution S ′ has already been found, using a dictionary in which insertion and verification can be done in time polynomial in the size of S ′ . Output S if recursion depth is even;

6 foreach S ′ ∈ neighbours(S) do 7 if S ′ / ∈ S, then enum(S ′ , S); 8
Output S if recursion depth is odd;

Proximity Search has been proved efficient for many maximal subgraphs enumeration problems. For example, it can be used to enumerate all maximal (induced or not) bipartite subgraphs, chordal subgraphs, k-degenerate subgraphs, maximal connected obstacle-free convex hulls, with polynomial delay [START_REF] Conte | New polynomial delay bounds for maximal subgraph enumeration by proximity search[END_REF]. We will show in detail several more applications of the Proximity Search framework in Chapter 5.

The Proximity Search framework is well-suited for enumerating maximal subgraphs, coping with some of the limitations of the Input Restricted Problem approach, but it usually requires exponential space. Refinements have been proposed [START_REF] Conte | Listing maximal subgraphs satisfying strongly accessible properties[END_REF][START_REF] Conte | Proximity search for maximal subgraph enumeration[END_REF], under certain conditions on the set system, in particular to make Algorithm 2.4 run in polynomial space. In Chapter 6, we will propose a new refinement of Proximity Search with weaker assumptions that achieves polynomial space as well.

Cao's retaliation-free paths

Recently, in a preprint of 2020 [START_REF] Cao | Enumerating maximal induced subgraphs[END_REF], Cao came up with a new technique for the enumeration of maximal induced subgraphs. This technique, called retaliation-free paths, appears to make the enumeration of maximal induced subgraphs possible for several more classes of graphs. It is namely used to enumerate the maximal induced trivially perfect subgraphs of a given graph.

The idea behind this technique is the same as in Proximity Search: it consists in showing the strong connectivity of a supergraph of solutions. First, one has to define a suitable, problem-specific neighbouring function, as in Proximity Search. However, Cao manages to build paths in which the usual proximity measure is not increasing. Indeed, the important property of retaliation-free paths is that any time an element belonging to the target solution is removed, it is possible to make sure it will be re-introduced

MAXIMAL SUBGRAPHS AND MINIMAL SUPERGRAPHS | 45

at a later step. This way, he asserts that, if the problem satisfies certain conditions and the neighbouring function is correctly defined, there always exists a retaliation-free path from one solution to another in the supergraph of solutions. Then, a depth-first search on the space of solutions allows to enumerate all of them with polynomial delay.

Enumeration of maximal subgraphs and minimal supergraphs

The problems on which we focus here are the enumeration of maximal induced Psubgraphs, minimal P-deletions and minimal P-completions of an arbitrary graph G, for an hereditary graph property P. These problems are defined in Chapter 1.

In some cases it is not possible, let alone meaningful, to find the optimal solution to such a problem. Indeed, the notion of "best" solution can be hard to model in terms of graphs, and in particular obtaining the minimum or maximum cardinality solution can be irrelevant to the problem. It is for example the case when dealing with databases [START_REF] Carmeli | Efficiently enumerating minimal triangulations[END_REF], bioinformatics [START_REF] Calamoneri | On maximal chain subgraphs and covers of bipartite graphs[END_REF], or statistical models [START_REF] Córdoba | On generating random Gaussian graphical models[END_REF]. Therefore, it is of better use to be able to enumerate all the maximal, or minimal, solutions: after that, the user can choose themself which solution is the best according to their specific criteria.

When the corresponding optimisation problem is hard, enumeration can also be used for sampling purposes. Since the computation can be stopped at any time, one can choose the best solution among those generated up to a certain time.

All the properties we consider here must be recognisable in polynomial time. Indeed, it can happen that the input graph G already satisfies property P. In this case, the minimal P-completions (resp. minimal P-deletions, maximal induced P-subgraphs) enumeration problem has only one solution, that is G itself: in other words, enumeration generalises recognition. Thus, an output-polynomial algorithm solving our enumeration problem must run in polynomial time when called on input G. This implies that one must be able to determine if G fulfils P in polynomial time, as stated in the following theorem. That is why in the present work, we are only interested in polynomial time recognisable graph properties. Theorem 2.6 (Folklore). If all maximal induced P-subgraphs (resp. minimal Pcompletions, minimal P-deletions) can be enumerated in output-polynomial time, then the property P can be recognised in polynomial time.

From an algorithmic point of view, the problems of enumerating maximal induced subgraphs, minimal deletions or minimal completions are closely linked to the classical enumeration problems presented in Section 2.1.3. In the present section, we will see how those problems are related.

Since the property under consideration is hereditary, the set of all induced Psubgraphs of G is an independent set system. Therefore, we know that in some cases it is possible to enumerate all maximal induced P-subgraphs of G with the outputpolynomial algorithm designed by Lawler et al. [START_REF] Lawler | Generating all maximal independent sets: NP-hardness and polynomial-time algorithms[END_REF] (see Section 2.2.2). But better output-sensitive complexity can be achieved.

Given a graph G and a hereditary property P, one can build an hypergraph on V (G) whose hyperedges are the sets of vertices inducing forbidden induced subgraphs for P in G. Then, enumerating all maximal induced P-subgraphs of G is equivalent to enumerating all minimal transversals of this hypergraph. Indeed, a minimal transversal of the hypergraph formed by the forbidden induced subgraphs corresponds to a minimal set of vertices of which the removal from the original graph yields a maximal induced subgraph satisfying the property P. Such an hypergraph is represented in Figure 2.7, when the considered property P refers to "belonging to the class of cographs", that is, avoiding the four-vertex path P 4 as an induced subgraph. Figure 2.7: From this graph that is not a cograph, one can build an hypergraph whose hyperedges are exactly the sets of vertices inducing a P 4 in the graph.

It is worth noticing that some hereditary graph properties (not all of them) admit a finite number of forbidden induced subgraphs: this is for example the case with split graphs, cographs, and threshold graphs, but not with chordal graphs. When considering such a property, our problem falls into a special case of the general transversals enumeration problem, where the size of the hyperedges is bounded by a constant.

In the 1990s, Eiter & Gottlob worked on this variant of the general problem and exhibited an incremental-polynomial algorithm for the enumeration of minimal transversals of hypergraphs of bounded edge size [START_REF] Eiter | Identifying the minimal transversals of a hypergraph and related problems[END_REF]. Thanks to their result, it is now straightforward to obtain an incremental-polynomial algorithm for the maximal induced P-subgraphs enumeration problem.

If in addition the considered property is monotone, i.e. closed under edge removal, then the maximal (non-induced) P-subgraphs, or minimal P-deletions, of G can also be enumerated with Eiter & Gottlob's incremental-polynomial algorithm [START_REF] Eiter | Identifying the minimal transversals of a hypergraph and related problems[END_REF], by considering an hypergraph whose vertices are the edges of G.

As for minimal P-completions of G, provided that P is a monotone property, they form a dependent set system of which we aim to enumerate the inclusion-wise minimal elements. Plus, they correspond to minimal deletions of G in the complement class

MAXIMAL SUBGRAPHS AND MINIMAL SUPERGRAPHS | 47

of P. In other words, if P denotes the graph property "the complement graph fulfils property P", then up to taking the complement, minimal P-completions of G are exactly minimal P-deletions of G. This allows us to use the same technique as for minimal P-deletions to obtain an incremental-polynomial enumeration algorithm.

At the moment, we know nothing about a general algorithm that could enumerate maximal (induced) P-subgraphs or minimal P-completions of a graph G with polynomial delay for any hereditary graph property P. On the other hand, neither do we know a hereditary graph property P for which the enumeration of maximal (induced) P-subgraphs or minimal P-completions of a graph G cannot be enumerated with polynomial delay. This raises some interesting questions which, although motivating our research, remain open at the end of this thesis. Question 1. Is there a (hereditary) graph property P such that minimal P-completions, or minimal P-deletions, cannot be enumerated with polynomial delay? Question 2. More generally, is there a (hereditary) graph property P such that minimal P-completions, or minimal P-deletions, cannot be enumerated in output-polynomial time?

Chapter 3

Split graphs

We provide in the present chapter efficient algorithms for the enumeration of minimal split completions, deletions, and maximal induced split subgraphs. A part of these results (minimal split completions and deletions) appears as a joint work with Aurélie Lagoutte, Vincent Limouzy, Arnaud Mary and Lucas Pastor in the 2020 preprint Efficient enumeration of maximal split subgraphs and sub-cographs and related classes [START_REF] Brosse | Efficient enumeration of maximal split subgraphs and induced sub-cographs and related classes[END_REF], submitted.

I

n this chapter, we will see an example of how, for a given graph property, the structure can be used to reduce an enumeration problem to another. In particular, the property considered here corresponds to "belonging to the class of split graphs".

More precisely, we show how to link the minimal split completions to the maximal stable sets of an auxiliary graph that can easily be found from the input graph. Split graphs have been studied in detail in order to find one single minimal split completion of a given graph [START_REF] Heggernes | Minimal split completions[END_REF].

As for maximal induced subgraphs, this class is a good example where the Input Restricted Problem can be used to achieve polynomial delay and polynomial space.

Minimal split completions

In this section, our aim is to enumerate all minimal split completions of G into a split graph, using a polynomial delay polynomial space algorithm. To do so, we establish a link between the minimal split completions of a graph and its maximal stable sets. However, we will see that different maximal stables sets may lead to the same completion. To overcome this issue, we first perform a pre-processing step that removes some unnecessary or undesired vertices from the input graph. Once the process is completed, the bijection between both objects is established.

Recall that a minimal split completion of a graph G is an inclusion-wise minimal split supergraph of G on the same vertex set; that is to say a split graph H such that

V (H) = V (G), E(G) ⊆ E(H)
, and there exists no split graph

H ′ = (V (G), E(H ′ )) such that E(G) ⊆ E(H ′ ) ⊊ E(H). The edges in E(H) \ E(G)
are the fill edges of the split completion. A graph can be seen in Figure 3.1. It is not split, but the addition of three red edges turns it into a split graph: it is a split completion of the input graph. Let us begin with a simple observation. Since the class of split graphs is selfcomplementary, we can list all maximal split deletions of G simply by computing all minimal split completions of the complement graph G, and then complementing the solutions. Therefore, the same complexity results will be obtained for minimal split deletions as well.

First, note that a split completion of G can always be obtained from a stable set. Indeed, if S is a stable set of G, adding all possible edges between pairs of vertices of V \ S makes V \ S into a clique, and the resulting graph is a split completion H of G. We will say that H is the split completion induced by S. In the example of Figure 3.1, the split completion is induced by the stable set {1, 6}. In the sequel we will see how to characterise the stable sets producing minimal split completions. Lemma 3.1. Let G = (V, E) be a graph. For any minimal split completion H of G, there exists a split partition V = K + S of H such that S is a maximal stable set of G.

Proof. Let H be a minimal split completion of G. The graph H is split so there exists a split partition, and H = (S + K, E + F ) (where F is the set of fill edges). If S is not a maximal stable set of H, there exists x ∈ V such that S ∪ {x} is a stable set of H, and of course K \ {x} is still a clique of H. Consequently, suppose that S is a maximal stable set of H.

MINIMAL SPLIT COMPLETIONS | 51

For contradiction, suppose that S is not a maximal stable set of G. There exists y such that S ∪ {y} is a stable set of G. As S ⊆ S ∪ {y}, the split completion induced by S ∪ {y} is a split sub-completion of H, supposed to be minimal. Therefore S ∪ {y} is a stable set of H, that is, S is not a maximal stable set of H: contradiction.

Hence it is only necessary to consider (inclusion-wise) maximal stable sets when looking for minimal split completions. But this condition is not sufficient. Indeed, in the example of Figure 3.1, the edge {3, 5} can be removed and the resulting graph is still a split completion (with split partition {2, 4, 5, 6} + {1, 3}), visible in Figure 3.2. It shows that the split completion induced by the maximal stable set {1, 6} is not minimal. Therefore, there exist maximal stable sets that do not induce minimal split completions. This is why we need to push our investigation further and find out which conditions make a maximal stable set induce a minimal split completion. In the following, we identify two kinds of vertices which can cause a solution to be non-minimal or produced twice. They are true twins and redundant vertices, the definition of which relies on nested neighbourhoods.

Definition 3.2 (Redundant vertices). Let

G = (V, E) be a graph. A vertex v ∈ V is redundant if there exists u ∈ V such that N [u] ⊊ N [v].
Remark that, because of the strict inclusion between the closed neighbourhoods, for every redundant vertex v there exists a vertex u which is not redundant such that

N [u] ⊊ N [v]. The set N [u] is inclusion-wise minimal.
The interest of identifying redundant vertices is given by the following observation (a stronger version of this will be proved in Lemma 3.3): if S is a maximal stable set of G not inducing a minimal split completion, then S contains a redundant vertex. By the way, the stable set identified in Figure 3.1 is a good example of this: it contains the vertex 6, which is redundant since

N [3] ⊊ N [6].
However, the converse is not necessarily true, as shown on Figure 3.3: in this graph, 2, 4, and 5 are redundant vertices. But there is in this graph a maximal stable set S = {2, 5} containing redundant vertices and still inducing a minimal split completion.

Hence, we need to dig deeper into the subject to identify which redundant vertices should be avoided in a stable set S in order for the induced completion to be minimal. We will show that the right characterisation of minimal split completions is in fact the following.

Lemma 3.3. Let G be a graph, let I be a maximal stable set of G. The split completion of G induced by I is minimal if and only if I does not contain any redundant vertex

x such that V \ N (x) is a stable set of G.
In order to prove Lemma 3.3, we need the following result which establishes a link between the split partitions of a graph and those of its subgraphs. In particular it can be used to compare two different split partitions of a split graph. This lemma will be invoked when characterising non-minimal split completions.

Lemma 3.4 ([55, Observation 4] & Corollary

). Let G = (V, E) and G ′ = (V, E ′ ) be two split graphs such that E ⊆ E ′ , and let V = I + K and V = I ′ + K ′ be split partitions of G and G ′ respectively. Then the following two inequalities hold:

• |K ′ ∩ K| ⩾ |K| -1; • |I ′ ∪ I| ⩽ |I| + 1.
First, we will try to determine which maximal stable sets are "bad" in the sense that they fail to produce minimal split completions. To this effect, let us find a necessary condition for a maximal stable set to induce a non-minimal split completion. This condition is obtained by looking carefully at the redundant vertices belonging to the considered maximal stable set. We state it as the following lemma. Lemma 3.5. Let G = (V, E) be a graph. Let I be a maximal stable set of G. If the split completion of G induced by I is not minimal, there exists a redundant vertex w ∈ I such that N (w) = V \ I.

MINIMAL SPLIT COMPLETIONS | 53

Proof. Let I be a maximal stable set of G, let H = (I + C, E + F ) be the split completion of G induced by I. Assume that the completion H is not minimal. Then there exists a non-empty set of edges A ⊆ F such that H -A is a minimal split completion of G. By Lemma 3.1 there exists a maximal stable set S of G such that

H -A = (S + K, E + F -A) is the split completion of G induced by S.
We All fill edges of H -A are also fill edges of H. Because w is in I, there is no fill edge incident to w in H, so there is also no fill edge incident to w in

H -A. As w ∈ K in H -A, this implies K ∩ C ⊆ N (w) ⊆ (K ∩ C) ∪ U = C. Let x ∈ U . As I is a maximal stable set of G, the vertex x has a neighbour in I. This neighbour is not in S because x ∈ S. Therefore, it is in I \ S = {w}, that is, xw ∈ E. Besides, N [x] ⊆ K ∩ C ⊆ N [w]
. This being true for all x ∈ U , we have

N (w) = C = V \ I.
Moreover, the completion H is not minimal, so there exists y ∈ U incident to a fill edge of H. Hence there exists z

∈ C such that yz / ∈ E. Then z ∈ N [w] \ N [y], so N [y] ⊊ N [w] and w is redundant.
Could it be that the necessary condition of Lemma 3.5 is in fact sufficient? The answer to this question turns out to be positive. We will see that Lemma 3.5 admits a converse, which can be stated as follows.

Lemma 3.6. Let G = (V, E) be a graph. Suppose that there exist a redundant vertex x such that V \ N (x) is a stable set of G. If I is a maximal stable set of G containing x, then the split completion induced by I is not minimal.

Proof. Let I be a maximal stable set of G containing x.

Necessarily I = V \ N (x) because V \ N (x) is a stable set.
Let H := (I + V \ I, E + F ) be the split completion induced by I. Since x is redundant, there exists

y ∈ V such that N [y] ⊊ N [x]. The vertex y is a neighbour of x so y ∈ V \ I. Therefore y is made adjacent to every vertex of V \ I in H. But N [y] ⊊ N [x]
, so there exists z ∈ V \ I such that yz is a fill edge in H, as illustrated in The idea is then to move x to the stable set, and y to the clique by considering the graph H ′ = H -{yz ∈ F | z ∈ N (x)}. We observe that H ′ is a proper sub-split completion of H. Hence H is not minimal.

From the last two lemmas, it is now straightforward to deduce the exact characterisation announced in Lemma 3.3.

Proof of Lemma 3.3. Lemma 3.5 gives one direction of implication, and Lemma 3.6 gives the other (by noticing that N (w) = V \ I rewrites to I = V \ N (w)).

In the light of Lemma 3.3, the idea is now to remove from G the identified "bad" redundant vertices, therefore building an auxiliary graph containing only the vertices that for sure will not take part in inducing non-minimal split completions. Then, we will only enumerate split partitions induced by maximal stable sets of this auxiliary graph. But in order to do so, we need to ensure that maximal stable sets in this auxiliary graph are also maximal stable sets in G. This is the purpose of the following lemma. Lemma 3.7. Let G = (V, E) be a graph and let R be the set of its redundant vertices. For all R ′ ⊆ R, the maximal stable sets of G \ R ′ are maximal stable sets of G.

Proof. Let R ′ ⊆ R. Recall that R = {v ∈ V | ∃u ∈ V, N [u] ⊊ N [v]}.
Observe that all maximal stable sets of G \ R ′ are necessarily stable sets of G. We will see that they are maximal.

MINIMAL SPLIT COMPLETIONS | 55

Let S be a maximal stable set of G \ R ′ . For contradiction, assume that S is not a maximal stable set of G. Hence there exists v ∈ V such that S ∪ {v} is a stable set of G, and v ∈ R ′ because otherwise S would not be maximal in G \ R ′ . The vertex v is redundant so there exists

u ∈ V \ R such that N [u] ⊊ N [v]
. This way, S ∪ {u} is a stable set of G and a stable set of G \ R ′ : contradiction. Nevertheless, we are not yet finished. Given a graph G, we know that removing some identified redundant vertices from G provides a graph in which every maximal stable set gives a minimal split completion of G, and doing so we guarantee to actually get every minimal spit completion of G. However, nothing prevents us from finding the same solution several times. This phenomenon is illustrated in Figure 3.6, where the stable sets are the sets of circled vertices, and the completion consists only in adding the middle horizontal edge. To solve this issue, we will characterise stable sets which give the same minimal completion, among the ones satisfying conditions of Lemma 3.3. This time, the vertices at which we are looking are true twins. Remark that in the graph of Figure 3.6, the top vertex and the bottom vertex have the same closed neighbourhood. This leads us to the following result: two distinct maximal stable sets induce the same split completion if and only if their symmetric difference is a pair of true twins. Lemma 3.8. Let G be a graph, let S 1 and S 2 be two distinct maximal stable sets of G. Denote by H 1 and H 2 the split completions of G induced by S 1 and S 2 respectively. Define S := S 1 ∩ S 2 . Then S 1 and S 2 induce the same split completion (that is to say, E(H 1 ) = E(H 2 )) if and only if there exists a pair of true twins

x 1 , x 2 ∈ V such that S 1 = S ∪ {x 1 } and S 2 = S ∪ {x 2 }, with N G [x 1 ] = N G [x 2 ] = V \ S. Proof. Let K 1 := V \ S 1 and K 2 := V \ S 2 be cliques in H 1 and H 2 , respectively.
Assume S 1 and S 2 induce the same split completion, that is to say E(H 1 ) = E(H 2 ). By Lemma 3.4, we have

|S 1 ∪S 2 | = |S 1 |+1 and |S 1 ∪S 2 | = |S 2 |+1. Then |S 1 | = |S 2 | and there exists x 1 ∈ S 1 \ S 2 and x 2 ∈ S 2 \ S 1 such that S 1 = S ∪ {x 1 } and S 2 = S ∪ {x 2 }.
There is no fill edge incident to

x 1 in H 1 . But because x 1 ∈ K 2 , we have K 1 ∩ K 2 ⊆ N G (x 1 ) ⊆ (K 1 ∩ K 2 ) ∪ {x 2 }. Moreover x 1 x 2 ∈ E(G), otherwise S 1 ∪ S 2
would be a stable set of G containing S 1 , assumed to be maximal. This implies that N [x 1 ] = V \ S. By symmetry of the roles of x 1 and x 2 , it gives N [x 1 ] = N [x 2 ] = V \ S, and in particular x 1 and x 2 are true twins.

Conversely, if

N [x 1 ] = N [x 2 ] = V \ S,
there is no fill edge incident to x 1 in H 2 , and there is no fill edge incident to x 2 in H 1 . Consequently, the only fill edges in H 2 and in H 1 are between vertices of V \ S = K 1 ∩ K 2 . Since H 1 and H 2 are both split, they have the same set of fill edges, so E(H 1 ) = E(H 2 ).

Inspired by Lemmas 3.3 and 3.8, we can then construct from every graph G an aux-

iliary graph f (G). Let B = {x ∈ V (G) | x is redundant and V \ N (x) is a stable set}. First remove B from G, and observe that G[V \ B] has no extra pair of true twins compared to G itself. Then from G[V \ B]
, remove all but one vertex from each set of pairwise true twins, resulting in the graph f (G) having no pair of true twins. The auxiliary graph f (G) is not unique because of the choice between each set of true twins, but is does not matter for the following.

Theorem 3.9. Let G be a graph. There exists a bijection between the set of all minimal split completions of G and the set of all maximal stable sets of any auxiliary graph f (G).

Proof. Let B as in the definition of f (G). Observe that G[V \ B] cannot contain a redundant vertex x of which the non-neighbourhood in G[V \ B] is a stable set, and the same applies to f (G). Moreover, a set I ⊆ V (f (G)) is a maximal stable set of f (G) if and only if it is a maximal stable set of G[V \ B] included in V (f (G)) (because adding a true twin to an existing vertex in f (G) preserves the maximality of I). So, by combining Lemmas 3.7 and 3.3, a set I ⊆ V (f (G)) is a maximal stable set of f (G) if and only if the split completion induced by I is a minimal split completion of G. This, combined with the non-existence of true twins in f (G) and Lemma 3.8, ensures the bijection. Procedure 3.1 produces the auxiliary graph f (G) mentioned in Theorem 3.9, containing no redundant or true twin vertex v such that V \ N (v) is a stable set. During

Step 5, every redundant vertex will be marked, as well as all but one vertex of each set of pairwise true twin vertices. Theorem 3.9 ensures that we can enumerate exactly once every minimal split completion of an input graph G by running Procedure 3.1 followed by an algorithm that enumerates all maximal stable sets of f (G). Since Procedure 3.1 is polynomial in time and space, the complexity of this algorithm only depends on the complexity of the algorithm used for the enumeration of maximal stable sets. We are thus looking for such an algorithm running in polynomial delay and polynomial space. For example, the algorithm proposed by Tsukiyama et al. in 1977 [84] fulfils these complexity requirements and allows us to state the following. According to Lemma 3.1, the number of minimal split completions of a graph G is at most the number of its maximal stable sets. It has been proven by Moon & Moser in 1965 [66] that this number can be as large as 3 n/3 , reached for a graph composed of n/3 disjoint triangles as in Figure 3 Lemma 3.3 states that there is a bijection between the minimal split completions and the maximal stable sets of a graph G with no redundant vertex u such that V (G) \ N (u) is a stable set. The graph presented in Figure 3.7 verifies this property. In particular, it has 3 n/3 minimal split completions. From these observations we deduce the following theorem.

Theorem 3.11. The upper bound 3 n/3 on the number of minimal split completions is tight.

By adding a universal vertex to the graph of Figure 3.7, we obtain a graph with one redundant vertex (the universal vertex). The number of its minimal split completions is therefore equal to the number of maximal stable sets of the graph shown in Figure 3.7, that is, 3 (|V (G)|-1)/3 . Therefore, we can even consider our graph to be connected and still have O(3 n/3 ) minimal split completions.

Using a polynomial delay algorithm for the enumeration of the maximal stable sets of a graph, our algorithm for the enumeration of all minimal split completions runs in total time O(N poly(n)), where N is the number of maximal stable sets. Therefore, its total execution time is bounded in an input-sensitive manner by O(3 n/3 poly(n)), almost matching the bound of Theorem 3.10. Corollary 3.12. There exists a polynomial delay algorithm for the enumeration of all minimal split completions of a graph running in total time O(3 n/3 poly(n)).

Maximal induced split subgraphs

As it was proved in the previous section, we are able to enumerate efficiently all minimal split completions and deletions of an input graph G. Now, can similar complexity results be achieved for the enumeration of maximal induced subgraphs? We addressed this question in 2019, that was independently solved by Cao in a preprint of 2020 [START_REF] Cao | Enumerating maximal induced subgraphs[END_REF] with a similar technique: the input restricted problem is polynomial, therefore it can be used to compute all maximal induced split subgraphs of G with polynomial delay and polynomial space. For the sake of completeness, our results, left unpublished, are presented in this section.

Let us begin with an observation. For G = (V, E) a graph, an induced split subgraph of G can be constructed by considering a clique K of G and a stable set S of G \ K. The graph G[K ∪ S] is then a split subgraph of G with split partition K + S. The next theorem is here to specify which cliques and stable sets have to be considered when looking for maximal induced split subgraphs.

Theorem 3.13. Let G be a graph, and let H be a maximal induced split subgraph of G.

There exists K a maximal clique of G and S a maximal stable set of

G \ K such that H = G[K ∪ S].
Proof. Since H is split, it admits a split partition C + I where C is a clique and I is a stable set. Assume that C is not a maximal clique in G. By definition there exists an

x ∈ V \ C such that C ∪ {x} is a clique in G. If x / ∈ I, then G[C ∪ I ∪ {x}
] is an induced split subgraph of G that strictly contains H. This cannot happen since we assumed H maximal. Therefore x ∈ I. In this case, we can set K = C ∪ {x} and S = I \ {x}. Now, any y ∈ S is non-adjacent to x, thus K is a maximal clique of G.

Moreover, S is a stable set of G \ K. If S were not maximal, there would exist S 0 a stable set of G \ K such that S ⊊ S 0 , and H would be an induced split subgraph of the split graph G[K ∪ S 0 ], which is excluded by maximality of H.

MAXIMAL INDUCED SPLIT SUBGRAPHS | 59

Hence H = G[K ∪ S] with K a maximal clique of G and S a maximal stable set of G \ K.

A maximal split subgraph can therefore be obtained by choosing a maximal clique, and a maximal stable set of the rest of the graph. This construction is illustrated in Figure 3.8. The idea now is to prove that the input restricted problem for maximal induced split subgraphs is polynomial. To this effect, consider a maximal induced split subgraph H of the input graph G, and a vertex v ∈ V (G) \ V (H). Then, we upper-bound the number of couples (K, S) such that K is a maximal clique of H + v and S is a maximal stable set of (H + v) \ K, and show that their number is at most quadratic. Finally, it suffices to enumerate all such couples (K, S) with an output-polynomial algorithm: since the number of solutions is polynomial in the size of H + v, all of them will be generated in polynomial time.

Let us have a look on what happens when we add a vertex to a maximal induced split subgraph H of G. The following lemma links the neighbourhood of the new vertex to the split partitions of H.

Lemma 3.14. Let H be a maximal induced split subgraph of G, and let

v be a vertex in V (G) \ V (H). Denote by (K, S) a split partition of H. Then K \ N (v) ̸ = ∅, and S ∩ N (v) ̸ = ∅. Proof. Assume for contradiction that K \ N (v) = ∅, that is, K ⊆ N (v). Then K ∪ {v} is a clique in H + v.
Since S is a stable set in H, then the vertices of H + v can be partitioned in two sets K ∪ {v} and S, where K ∪ {v} is a clique and S is a stable set. Therefore, H + v is an induced split subgraph of G, contradicting the maximality of H.

Now, if S ∩ N (v) = ∅, then S ∪ {v} is a stable set in H + v.
As before, we deduce that H + v has a split partition (K, S ∪ {v}), and H + v is an induced split subgraph of G, contradicting the maximality of H.

The situation described in Lemma 3.14 can be represented as in Figure 3.9, where v is the added vertex. As stated previously, v has at least one neighbour in the stable set and one non-neighbour in the clique. Proof. The graph H is split: let (K, S) be any split partition of the vertices of H. By Lemma 3.14, there are exactly two maximal cliques of H + v which do not contain vertices of S: these are K and (K ∩ N (v)) ∪ {v}. Then, for any vertex u ∈ S, the only maximal cliques of H +v that contain u are (N (u)\{v})∪{u}, and (N (u)∩N (v))∪{u, v} if uv ∈ E. Therefore, there are at most 2n maximal cliques in H + v. Lemma 3.15 directly implies the following corollary, upper-bounding the number of couples (K, S) where K is a maximal clique of H + v and S is a maximal stable set of (H + v) \ K. Corollary 3.16. Let H be a maximal induced split subgraph of G, and let v be a vertex in V (G) \ V (H). There exists at most a quadratic number of couples (K, S) such that K is a maximal clique of H + v and S is a maximal stable set of (H + v) \ K.

K S v N (v)
Proof. By Lemma 3.15, there are at most a linear number of maximal cliques in H + v. Let K be any maximal clique of H + v.

If v ∈ K, then (H + v) \ K is split (as an induced subgraph of H). Consequently, it contains a linear number of stable sets.

Otherwise, (H + v) \ K can be written as H ′ + v with H ′ an induced subgraph of H. Since H is split, so is H ′ . Therefore, the complement of H ′ + v meets the requirements of Lemma 3.15: it contains a linear number of maximal cliques.

In other words, (H + v) \ K contains a linear number of maximal stable sets for any maximal clique K of H + v. This concludes the proof.

MAXIMAL INDUCED SPLIT SUBGRAPHS | 61

Now, it remains to generate all such couples (K, S) in polynomial time. It can be achieved with two nested calls to the algorithm of Tsukiyama et al. [START_REF] Tsukiyama | A new algorithm for generating all the maximal independent sets[END_REF], that was already used for minimal split completions. This algorithm even runs in polynomial space. This is why in our case, the function genRestrHered used in Algorithm 2.3 can be computed in polynomial time and polynomial space.

Therefore, it is possible to use Algorithm 2.3 to enumerate all maximal induced split subgraphs of a graph G with polynomial delay. Due to the space complexity of the algorithm used to solve the input restricted problem, polynomial space can also be achieved. The result is summarised here as Theorem 3.17.

Theorem 3.17. The maximal induced split subgraphs of an arbitrary input graph can be enumerated with polynomial delay in polynomial space.

Chapter 4 Extension problems

In this chapter we investigate the Flashlight Search technique, presented in Chapter 2, and prove some hardness results on the so-called extension problem, which prevent from finding a general enumeration algorithm based on Flashlight Search. These results appear as a joint work with Aurélie Lagoutte, Vincent Limouzy, Arnaud Mary and Lucas Pastor in the 2020 preprint Efficient enumeration of maximal split subgraphs and sub-cographs and related classes [START_REF] Brosse | Efficient enumeration of maximal split subgraphs and induced sub-cographs and related classes[END_REF].

A n interesting result would be to find a general method that, given a (hereditary) graph property P and an input graph G, returns all maximal induced P-subgraphs of G. Such a general method would also be of great interest for the minimal P-completion and P-deletion problems. Because of its generality, Flashlight Search (see Section 2.2.1 for an introduction) could seem appropriate for this purpose. Moreover, this method has been successfully used on several special cases [START_REF] Conte | Enumeration of Maximal Common Subsequences Between Two Strings[END_REF][START_REF] Mamadou | On the enumeration of minimal dominating sets and related notions[END_REF], when the property P is restricted, or if the graph G is constrained to a particular graph class.

We will show in this chapter that unfortunately, Flashlight Search needs some restrictions on the input: it cannot in general return all maximal induced P-subgraphs of G for any P and any G with polynomial delay and polynomial space. Moreover, even if it can provide a polynomial delay and polynomial space algorithm for the enumeration of minimal P-deletions for some hereditary properties, we show that there are other graph properties for which Flashlight Search is not the best tool.

More precisely, we define the extension problem (for induced subgraphs and for deletions) as the problem that must be solved in polynomial time in order to use Flashlight Search, and we show that this problem is NP-complete in many cases.

Maximal induced subgraphs

Extension problem. For a hereditary graph property P, the extension problem for maximal induced P-subgraphs is defined as follows. Given a graph G (not satisfying P in general) and two disjoint subsets A and B of its vertex set V , decide if there exists a maximal induced subgraph H of G satisfying P, containing A and avoiding B.

In other words, we want that A ⊆ V (H) and B ∩ V (H) = ∅. Note that we cannot remove B from the vertex set before looking for a maximal induced P-subgraph: this operation could lead us to a non-maximal induced P-subgraph of G, which is not what we are looking for.

If it were possible to solve the extension problem for P in polynomial time, then we would be able to enumerate all maximal induced P-subgraphs of a given graph G using Flashlight Search. Being able to decide in polynomial time if there exists a maximal induced P-subgraph of G containing a set of prescribed vertices and avoiding another is exactly what is needed at each step of the algorithm. Indeed, at step i of the binary partition, the two sets of vertices are included in {e 1 , . . . , e i }, and we have to decide whether or not there exists a compatible solution.

Recall that a graph property P is hereditary if for all G satisfying P, all induced subgraphs of G also satisfy P. The hereditary property P is called non-trivial if it is verified by infinitely many graphs and has at least one obstruction, which is a graph J P not satisfying P. In other words, a hereditary graph property is non-trivial if infinitely many graphs satisfy it, and infinitely many do not.

The node-deletion problem consists in determining the minimum number of nodes which must be deleted from a graph such that the resulting subgraph satisfies the property P. It has been shown by Lewis & Yannakakis in 1980 [63] that for any non-trivial hereditary property P, the node-deletion problem is NP-complete, provided that testing for P can be performed in polynomial time. We will show here that the same can be said about the extension problem. Theorem 4.1. For any non-trivial hereditary graph property P, the extension problem for maximal induced P-subgraphs is NP-hard.

Moreover, if P can be tested in polynomial time, then the extension problem is NP-complete.

Let us recall that "the class P" denotes in fact the class of all graphs satisfying property P. First of all, let us observe that the class P contains all the stable sets or all the cliques. Indeed, because P is non-trivial there exist graphs in P that have arbitrarily many vertices. Let k ∈ N. Then by Ramsey's theorem, every graph in P that is large enough (at least the so-called Ramsey number R(k, k)) contains either a clique or a stable set of size k. Since P is a hereditary property, it implies that this clique or stable set of size k belongs to P. Up to considering the complement class

MAXIMAL INDUCED SUBGRAPHS | 65

P (which remains non-trivial and hereditary), we can assume that P contains all the stable sets.

The first step is to define a preorder (a binary relation that is symmetric and transitive) on the set of all graphs, essentially the same as the one given by Lewis & Yannakakis [START_REF] Lewis | The node-deletion problem for hereditary properties is NP-complete[END_REF]. This preorder will be useful in the proof of Theorem 4.1, to ensure that the considered graph satisfies property P.

For any connected graph G and any vertex c ∈ V (G), let λ c (G) be the non-increasing sequence of the sizes of the connected components of G -c. If V (G) = {c}, then λ c (G) = (0). Then, let λ(G) be the minimum for the lexicographic order of the

λ c (G), that is, λ(G) = min lex {λ c (G) | c ∈ V (G)}. Let c(G) ∈ V (G) be the vertex minimising λ c (G).
If the minimum is reached for several vertices, take any of them (for example the lexicographically smallest) as c(G). By definition, λ(G) = λ c(G) (G).

For any graph G with connected components G 1 , . . . , G l , let µ(G) be the nonincreasing sequence of the λ(G i ) according to the lexicographic order. For convenience, the connected components G 1 , . . . , G l of G will now be ordered to have µ(G) = (λ(G 1 ), . . . , λ(G l )). The function µ defines a prewellordering (all elements are pairwise comparable, there is no infinite decreasing sequence for µ) on the set of all graphs.

Figure 4.1 illustrates this preorder on four connected graphs G 1 , G 2 , G 3 and G 4 . The vertex c minimising λ is identified in G 1 and G 3 , whereas for G 2 and G 4 , any vertex can be taken. Remark that in the induced preorder, µ can take the same value on several graphs: in this example, µ(G 2 ) = µ(G 4 ) = ((4)).

G 1 c G 2 G 3 c G 4 Figure 4.1: In this example, we have µ(G 1 ) = ((2, 2, 1)) whereas µ(G 2 ) = µ(G 4 ) = ((4)), and µ(G 3 ) = ((2, 1, 1)). Therefore, µ(G 3 ) ⩽ µ(G 1 ) ⩽ µ(G 2 )
, and G 3 is the smallest of the four graphs for µ.

Equipped with this prewellordering on the set of all graphs, we are now ready to prove Theorem 4.1.

Proof of Theorem 4.1. First, if P can be tested in polynomial time, the extension problem is in NP. Indeed, given a subset S of vertices of the input graph G, one can easily check in polynomial time whether G[S] satisfies P, and whether S contains A and avoids B. Moreover, the maximality of G[S] can be tested in polynomial time because P is assumed to be hereditary.

As stated in the previous discussion, it is always possible to assume that the class P contains all the stable sets.

The preorder defined by µ is well-founded, so every non-empty set of graphs has a smallest element for µ. In particular, the set of all graphs that do not satisfy P has a smallest element for µ. Hence there exists a graph J P / ∈ P which is minimum for µ, that is to say µ(J P ) = min lex {µ(H) | H / ∈ P}. Since P contains all the stable sets, the graph J P has at least one edge, thus at least two vertices.

Denote by J 1 , . . . , J l the connected components of J P . Therefore µ(J P ) is the sequence µ(J P ) = (λ(J 1 ), . . . , λ(J l )). Let J * 0 be the largest connected component of J 1 -c(J 1 ). We define J 0 as the subgraph of J P induced by V (J * 0 )∪{c(J 1 )}. Consider also the induced subgraph

J ′ 1 := J P [V (J 1 ) \ V (J * 0 )].
Both graphs J 0 and J ′ 1 are connected, and J 0 has at least one edge. Let then d be any vertex of J 0 different from c(J 1 ).

Before starting the reduction, let us have a look at what happens to the obstruction J P , and how J 0 and J ′ 1 are built. An illustration of the process applied to a graph J P is given in Figure 4.2. This graph satisfies µ(J P ) = ((4, 2), ( 3)). Let G be a graph, and let B be a subset of its vertices. We build a graph G ′ , using a technique similar to the one used for showing that the node-deletion problem is NP-complete [START_REF] Lewis | The node-deletion problem for hereditary properties is NP-complete[END_REF], as follows.

J ′ 1 J 0 c d J 1 J 2 J P λ(J 2 ) = (3) λ(J 1 ) = (4, 2) = λ c (J 1 )
For each vertex u of G, attach a copy of J ′ 1 to u by identifying c(J 1 ) with u. Replace every edge of G by a copy of J 0 , identifying c(J 1 ) with one endpoint and d with the other, in any order. Finally, add J 2 , . . . , J l as new connected components. The graph G ′ is the graph obtained this way. Figure 4.3 illustrates the transformation of a graph G into G ′ , using the obstruction J P of Figure 4.2. By construction, the graph G ′ contains many copies of J P , therefore it does not satisfy the hereditary property P. Call A the set of all vertices that are in G ′ but were not in G. We will show that finding a maximal stable set of G avoiding B, or finding a maximal induced P-subgraph of G ′ which contains A and avoids B are two equivalent problems.

MAXIMAL INDUCED SUBGRAPHS | 67

G G ′ B A G ′
1. First, suppose that there exists a maximal stable set S of G which does not intersect B. We will see that the graph

H := G ′ [S ∪ A] verifies µ(H) < µ(J P ).
As S is a maximal stable set of G, each edge in G has at least one endpoint in V \ S. Hence, removing from G ′ all the vertices of V (G) \ S destroys a vertex identified to c(J 1 ) or d in each copy of J 1 .

For each vertex s ∈ S, let us further observe the connected component H s of H containing s. It is composed of one copy of J ′ 1 and d G (s) "truncated" copies of J 0 , all glued together by identifying either c(J 1 ) or d into s (by "truncated" copy of J 0 , we mean either J 0 -c(J 1 ) or the connected component of J 0 -d that contains c(J 1 )). It follows λ(H s ) ⩽ λ s (H s ) < λ(J 1 ) because the truncated copies of J 0 are smaller than J 0 itself. Now, let us show that µ(H) < µ(J P ). Observe that the connected components of H are precisely {H s : s ∈ S} ∪ {J 2 , ..., J l }. We assumed that λ(J 1 ), ..., λ(J l ) is a non-increasing sequence, so λ(J i ) ⩽ λ(J 1 ) for all 2 ⩽ i ⩽ l.

If λ(J 2 ) < λ(J 1 ) (if the inequality is strict), then since λ(H s ) < λ(J 1 ) for all s ∈ S we conclude that λ(C) < λ(J 1 ) for any connected component C of H. This implies that max{λ(C) : C is a connected component of H} < λ(J 1 ). Therefore the sequence µ(H) is lexicographically strictly smaller than µ(J P ) since the first element of µ(H) is strictly smaller than the first element of µ(J P ).

If µ(G) was starting with a plateau, that is to say, if there exists j ⩾ 2 such that λ(J 1 ) = λ(J 2 ) = . . . = λ(J j ) (choose the largest such index j), then we conclude by noticing that the sequence µ(H) starts with the plateau λ(J 2 ) = . . . = λ(J j ), which is strictly shorter by one, and then all other values appearing in µ(H) are strictly smaller than λ(J 1 ). Indeed, since for all s ∈ S, λ(H s ) < λ(J 1 ) and since the only other connected components of H are copies of J 2 , ..., J l , the only connected components C of H for which λ(C) = λ(J 1 ) are precisely the copies of J 2 , ..., J j . So only the first j -1 elements of the sequence µ(H) will have value λ(J 1 ) and then, the sequence µ(H) will be lexicographically strictly smaller than µ(J P ).

In either case, we obtain that µ(H) < µ(J P ). As J P is the smallest obstruction for P, and since by definition of µ, µ(H) is larger than µ(K) for any subgraph K of H, the graph H does not contain any obstruction as an induced subgraph and H ∈ P. Therefore H is an induced P-subgraph of G ′ that contains A and does not intersect B.

2.

Conversely, assume that there exists a maximal induced P-subgraph H of G ′ containing A and avoiding B. Then J P is not an induced subgraph of H.

But every edge uv of G "induces" a copy of J 1 in G ′ (meaning, if you take both u, v, and a bunch of vertices of A) which together with the copies of J 2 , ..., J l would form a subgraph isomorphic to J P . Furthermore, u and v are the only vertices of that copy of J P that do not belong to A. Hence, since J P is an obstruction for P and since H must contain all the vertices of A, H does not contain u or does not contain v. So

V (H) ∩ V (G) is a stable set of G which does not intersect B.
So far, we have proven :

• In 1. that if S is a maximal stable set of G which does not intersect B, then H := G ′ [S ∪ A] is a P-subgraph of G ′ which contains A and does not intersect B.

• In 2. that if H is a maximal P-subgraph of G ′ which contains A and does not intersect B, then

S := V (H) ∩ V (G) is a stable set of G not intersecting B.
It remains to show that what we obtain in both cases is also maximal.

Let S be a maximal stable set of G which does not intersect B, let us prove that H := G ′ [S ∪ A] is a maximal P-subgraph of G ′ which contains A and does not intersect B. Assume H is not maximal and let H ′ ⊋ H be a maximal P-subgraph of G ′ which contains A and does not intersect B. By 2., we know that

S ′ := V (H ′ ) ∩ V (G) is a stable set of G avoiding B. Then, observe that S = V (H) ∩ V (G) ⊆ V (H ′ ) ∩ V (G) = S ′ . Moreover, there exists v ∈ V (H ′ ) \ V (H), consequently v / ∈ A so v ∈ V (G). Hence v ∈ S ′ \ S so S ′
is a stable set of G that avoids B and strictly contains S, contradicting the maximality of S. Now, let us prove that if H is a maximal P-subgraph of G ′ which contains A and does not intersect B, then S := V (H) ∩ V (G) is a maximal stable set of G which does not intersect B. Let S ′ ⊇ S be a maximal stable set of G avoiding B which contains S. We will prove that S ′ = S. By 1.

H ′ := G ′ [S ′ ∪ A] is a P-subgraph of G ′ which contains A and does not intersect B. But since H = G ′ [S ∪ A], in particular H is 4.2 MAXIMAL EDGE-SUBGRAPHS | 69 contained in H ′ , which would contradict the maximality of H unless S ∪ A = S ′ ∪ A. Since A ∩ S ′ = ∅, this implies S ′ = S.
Hence, without any assumptions on the class P, it is not possible to enumerate all maximal induced P-subgraphs of a graph G in polynomial delay using the simple algorithm derived from the extension problem. This, however, does not mean that Flashlight Search cannot be efficient at all, since the sets A and B could in fact be assumed to have certain specific properties depending on P, and which could make the extension problem easy to solve in special cases (see for instance [START_REF] Conte | Enumeration of Maximal Common Subsequences Between Two Strings[END_REF][START_REF] Mamadou | On the enumeration of minimal dominating sets and related notions[END_REF]).

Maximal edge-subgraphs

In the previous section, the extension problem for maximal induced subgraphs was proved to be NP-hard. In the present one, we define the extension problem for maximal edge-subgraphs. This problem is further investigated to try and determine in which cases the extension problem for maximal edge-subgraphs is polynomial, and in which cases it is NP-hard.

Extension problem. For a hereditary graph property P, the extension problem for maximal edge-subgraphs is stated as follows. Given a graph G = (V, E) and two disjoint subsets A and B of E, does there exist a minimal P-deletion of G containing all edges of A and no edge of B?

As for the vertex version, it does not suffice in general to look for maximal P-edgesubgraphs of G -B, because the P-subgraphs obtained this way may not be maximal P-subgraphs of G.

Recall that a graph property P is said to be monotone if it is closed under edge removal. In other words, P is monotone if for any graph G satisfying P and any edge e of G, G -e also satisfies P.

Such a general proof as in the case of maximal induced subgraphs is hard to obtain when considering maximal edge-subgraphs, even when the property P is assumed to be monotone. In the sequel, we explore the "edge version" of the extension problem to understand in which cases it can be solved by a polynomial algorithm. Three graph classes are considered: forests, graphs without short induced cycles, and graphs without long induced paths.

Forests

Forests are graphs without induced cycles. They consist in disjoint unions of trees. If P denotes the class of forests, which is a monotone property, the extension problem asks if there exists a maximal spanning forest of G containing A and avoiding B.

Assume first that G is connected. In this particular case, if removing B first disconnects G, then the answer is no: all spanning trees of G must contain at least one element from B. Else, B can be removed first. The set A, if it induces a forest, can then be extended in G -B to a spanning tree of G. In the case where G is not connected, a (maximal) spanning forest of G is the union of spanning trees of all connected components of G. Therefore, the extension problem for forests is polynomial.

This simple observation has already been made in the article of Read & Tarjan [START_REF] Read | Bounds on backtrack algorithms for listing cycles, paths, and spanning trees[END_REF] introducing the Flashlight method. They use it to design a very efficient algorithm, running in polynomial delay and polynomial space, for the enumeration of all spanning trees of a connected graph.

Nevertheless, the extension problem for maximal edge-subgraphs is not polynomial for all classes of graphs. In the following two sections, we exhibit two graph properties for which this problem is NP-hard.

P k -free graphs

For an integer k ⩾ 3, let us denote by P k the path on k vertices. We will now have a look on the class of all graphs that do not have long paths as induced subgraphs: the P k -free graphs. In particular, when k = 4, the class of P k -free graphs is exactly the class of cographs. Note that the property of being P k -free is not monotone: a cycle of length k is P k -free but removing one edge from it yields a P k .

In 2018, Casel et al. proved, among other results, that the extension problem with A = ∅ is NP-complete in the case of maximal matchings [START_REF] Casel | On the complexity of solution extension of optimization problems[END_REF]. Since maximal P 3 -free graphs correspond exactly to maximal matchings in triangle-free graphs, this result implies that the extension problem for maximal P 3 -free subgraphs is NP-complete, even in triangle-free graphs and with A = ∅. We extend this result in the present section, proving the following theorem. Theorem 4.2. The extension problem for maximal P k -free edge-subgraphs is NP-hard for all k ⩾ 3. Moreover, it is NP-complete when k equals 3 or 4.

Before proving Theorem 4.2, let us see how maximal P 4 -free edge-subgraphs can be recognised in polynomial time.

Consider a graph G = (V, E) and an edge-subgraph S of G, identified with its edge set (therefore S ⊆ E), since the class of P 4 -free graphs is stable under adding isolated vertices. We design a procedure, running in polynomial time, to determine if S induces a maximal P 4 -free edge-subgraph of G. The procedure relies on what is called the sandwich problem.

The sandwich problem [START_REF] Charles Golumbic | Graph sandwich problems[END_REF] is a decision problem defined as follows. We are given a graph property P, and two graphs G 1 = (V, E 1 ) and G 2 = (V, E 2 ) on the same

MAXIMAL EDGE-SUBGRAPHS | 71

vertex set such that E 1 ⊆ E 2 , which both typically do not satisfy property P. The question is to determine whether there exists a graph G = (V, E) satisfying P such that

E 1 ⊆ E ⊆ E 2 .
A polynomial algorithm answering this question for cographs -that is, P 4 -free graphs -was proposed by Golumbic, Kaplan & Shamir [START_REF] Charles Golumbic | Graph sandwich problems[END_REF]. Such an algorithm is called a sandwich algorithm in the sequel. The idea is now to use the sandwich algorithm for cographs to determine if a given edge set produces a maximal P 4 -free edge-subgraph.

Recognising a maximal P 4 -free edge-subgraph in polynomial time. Consider the graph G and its subgraph S. The "cograph property" can be tested in linear time, so we may assume that S induces a sub-cograph of G.

At the beginning, consider G 1 = S and G 2 = G. Since S is a cograph, the sandwich algorithm called on (G 1 , G 2 ) returns true. Then, it suffices to try adding edges to G 1 , one at a time, and call the sandwich algorithm: if it returns true on (G 1 + e, G 2 ) for at least one edge e ∈ E \ S, it means that there exists a sub-cograph of G strictly containing S, and S is not maximal. Else, the sandwich algorithm returns false on (G 1 + e, G 2 ) for each e ∈ E \ S, and S is a maximal P 4 -free edge-subgraph of G.

The sandwich algorithm for cographs being polynomial, this whole procedure also runs in polynomial time.

Equipped with this polynomial recognition procedure, we are now ready to prove Theorem 4.2.

Proof of Theorem 4.2. For k = 3, the result follows from the proof of Casel et al. [START_REF] Casel | On the complexity of solution extension of optimization problems[END_REF] and the previous discussion. Now, let us prove it for k = 4.

Let G = (V, E) be a graph, and let S ⊆ E be a set of edges of G. By the previous discussion, knowing if S is a maximal P 4 -free edge-subgraph of G is polynomial. Therefore, the problem is in NP. We will now prove that the extension problem for maximal P 4 -free edge-subgraphs is NP-hard.

The reduction is from 3-SAT. Begin with a 3-SAT formula, with clauses C 1 , . . . , C m , and variables X 1 , . . . , X n . Consider the graph G built from the formula as follows.

For each clause C j , build a vertex c j , and for each variable X i , build two vertices x i and x i corresponding to the associated literals, linked by an edge x i x i . Now, add an edge between x i (or x i ) and c j if the corresponding literal appears in clause C j . At this step, each vertex c j is of degree 3. Finally, for all j, add a pending vertex c ′ j to c j . Call the resulting graph G. An illustration of such a construction is given in Figure 4.4.

We define

A = {x i x i | 1 ⩽ i ⩽ n} and B = {c j c ′ j | 1 ⩽ j ⩽ m}.
These will be the edge sets A and B considered for the extension problem.

Suppose that there exists a maximal P 4 -free subgraph H of G, containing A and avoiding B. Since H is a maximal P 4 -free subgraph of G, adding to H an edge of B produces an induced P 4 . That is to say, each vertex c j is the endpoint of an induced P 3 . Thus, there exists i such that c j x i ∈ E(H) or c j x i ∈ E(H). Without loss of generality, suppose that c j x i ∈ E(H) (so c j x i / ∈ E(H)). In this case, there is no k such that

c k x i ∈ E(H), otherwise c j x i x i c k is an induced P 4 in H.
For all 1 ⩽ i ⩽ n, at most one of x i , x i has neighbours among {c 1 , . . . , c m }. Assigning the value 1 to the corresponding literal satisfies the formula.

Conversely, if the formula is satisfiable, there exists a maximal P 4 -free subgraph H of G containing A and avoiding B. It suffices to keep only edges incident to vertices corresponding to literals assigned the value 1. To avoid creating induced P 4 , keep only one edge incident to each vertex c j . This way, each vertex c j is the endpoint of an induced P 3 , and no edge of B can be added without creating a P 4 .

Consequently, the edge extension problem for P 4 -free graphs is NP-complete, even in triangle-free graphs because the graph G we built is triangle-free.

It is easy to adapt the previous reduction to show the NP-hardness of the problem for P k -free graphs, with k > 4. It suffices to subdivide each edge x i x i into a path of length k -3 whose edges are all put in the set A.

Graphs without cycles of length at most k

Another class of graphs that is worth studying is the class of graphs without cycles of length at most k, for a given k ⩾ 3, also known as graphs of girth at least k + 1, where the girth stands for the length of the shortest cycle. This is a monotone property. For this class of graph, it has been shown by Yannakakis in 1981 that the edge-deletion problem is NP-complete [START_REF] Yannakakis | Edge-deletion problems[END_REF]. In this case, the edge-deletion problem consists in finding a set of edges of minimum cardinality whose removal results in a graph without cycles of length at most k.

In the same fashion, we prove that the edge extension problem for graphs without cycles of length at most k, that is to say, determining if there exists a maximal edge

MAXIMAL EDGE-SUBGRAPHS | 73

subgraph without cycles of length at most k, containing A and avoiding B, is also NP-complete.

Theorem 4.3. The extension problem for maximal edge-subgraphs without cycles of length at most k is NP-complete for all k ⩾ 3.

Proof. First of all, checking if a set of edges induces a subgraph without cycles of length at most k can be done in time O(n k ), where n is the number of vertices of the input graph: it suffices to test all possible vertex subsets of size at most k. Moreover, as the property is monotone, maximality can also be checked in polynomial time.

The reduction is from the minimal Vertex Cover extension in triangle-free graphs, whose NP-completeness has been proven by Boros et al. [START_REF] Boros | An efficient incremental algorithm for generating all maximal independent sets in hypergraphs of bounded dimension[END_REF]Proposition 2]. The minimal Vertex Cover extension problem asks, given a graph G and a subset S of its vertex set, whether there exists an inclusion-wise minimal Vertex Cover of G containing S, that is, a subset X ⊇ S of vertices such that each edge has at least one endpoint in X. The original NP-completeness statement [START_REF] Boros | An efficient incremental algorithm for generating all maximal independent sets in hypergraphs of bounded dimension[END_REF] does not mention the triangle-free case, but the reduction used in the proof produces only triangle-free input graphs, which proves the NP-completeness we need.

First, we shall prove the result for k = 3. Let G = (V, E) be a triangle-free graph, and let S ⊆ V . We build another graph G + c by adding a universal vertex c to G. Since G is triangle-free, all triangles in G + c must include c. Moreover, for two vertices u, v ∈ V , the three vertices u, v, and c form a triangle in G + c if and only if uv ∈ E. Thus, there is a one-to-one correspondence between the edges of G and the triangles of G + c. We will show that finding an edge extension without cycles of length (at most) 3 is equivalent to finding a minimal Vertex Cover of G containing S, or finding a maximal triangle-free subgraph of G + c containing A and avoiding B.

Let H be a maximal triangle-free subgraph of G + c, containing A and avoiding B and let X = {v ∈ V | cv / ∈ E(H)}. Let us prove that X is a minimal Vertex Cover of G containing S. Since H is triangle-free, X is a Vertex Cover of G. Indeed, for each edge e of G there exists v ∈ e such that cv / ∈ E(H) (hence v ∈ X), otherwise e ∪ {c} induces a triangle in H.

Moreover, since H does not contain any edge of B, X contains S for otherwise there would be v ∈ S such that cv ∈ E(H).

Finally, since H is a maximal triangle-free subgraph of G + c, it is easy to see that the Vertex Cover X is minimal in G: if there were v ∈ X such that X \ {v} is a Vertex Cover of G, then all neighbours of v (except c) would have to be in X to cover all the edges. So, by definition of X, there is no neighbour u of v such that cu ∈ E(H), hence we can add the edge cv to H without creating any triangle. This contradicts the maximality of H.

Conversely, if we are given a minimal Vertex Cover of G containing S, then the subgraph of G + c given by (V ∪ {c}, A ∪ {cv | v / ∈ S}) is triangle-free, and it is maximal in G + c because the Vertex Cover is minimal in G.

This concludes the proof for k = 3.

For greater values of k, the proof can easily be adapted by subdividing each edge of G in G + c into a path of length k -2 (that is, adding k -3 new vertices on each edge), and defining A to contain all edges of those paths. Such a transformation is illustrated in

MAXIMAL EDGE-SUBGRAPHS | 75

As we have seen, in general, solving an extension problem is not easy: in the induced case, the extension problem is NP-hard in general, and in its edge version, there are also some situations in which it is NP-complete. Flashlight Search is efficient to solve many enumeration problems with polynomial delay, but unfortunately the technique is not applicable to all of our problems. Therefore, if we want to solve all the maximal subgraphs (induced or not) enumeration problems with a general technique, then Flashlight Search is not adapted. This is why a more sophisticated technique is required.

Chapter 5 Proximity Search: polynomial delay

The results presented in this chapter are obtained by applying and adapting the Proximity Search technique. Parts of them were obtained as a joint work with Aurélie Lagoutte, Vincent Limouzy, Arnaud Mary and Lucas Pastor and appear in the 2020 preprint [START_REF] Brosse | Efficient enumeration of maximal split subgraphs and induced sub-cographs and related classes[END_REF]. [START_REF] Brosse | Polynomial delay algorithm for minimal chordal completions[END_REF].

Other parts of the results in this chapter (on chordal completions) have been obtained with Vincent Limouzy and Arnaud Mary and published in the proceedings of the 2022 ICALP conference

I

n this chapter, we study some classes of graphs in which the structure makes it easy to find an elimination ordering. The idea is then to apply Proximity Search: we will use this special, property-dependent ordering as the canonical ordering to define the proximity between two solutions.

The first two classes that will be considered here are cographs and threshold graphs. Both are well-studied classes of graphs for which it was not known if there exists polynomial delay algorithms enumerating maximal (induced or not) subgraphs of an arbitrary input graph.

Then, we focus on the class of chordal graphs. This graph class is very important since it is closely related to graph parameters such as treewidth and arises in many applications. A polynomial delay algorithm running in exponential space was already known for maximal induced chordal subgraphs and for minimal chordal deletions [START_REF] Conte | Proximity search for maximal subgraph enumeration[END_REF], but the question of the existence of a polynomial delay algorithm enumerating minimal chordal completions of a graph remained open.

Maximal induced sub-cographs

As mentioned earlier, the class of cographs is hereditary, and cographs can be recognised in linear time. This implies that finding one maximal induced sub-cograph of an input graph is easy, using a greedy algorithm.

To the best of our knowledge, no polynomial delay algorithm was known for the enumeration of maximal induced sub-cographs of a graph. The idea is to try using Proximity Search on the class of cographs and see if it helps to enumerate them efficiently. Plus, since cographs benefit from a twin construction ordering on their vertex set, as stated in Section 1.1.2, we have a natural candidate for defining a canonical ordering which could be useful in the Proximity Search framework.

If it were possible to solve the input restricted problem (see Section 2.2.4) for maximal induced sub-cographs in polynomial time, then it would yield a polynomial delay algorithm for their enumeration. However, we will show that in our particular case, this problem cannot be solved in polynomial time.

Observe a graph H consisting of k disjoint edges x 1 y 1 , . . . , x k y k . This graph is a cograph. In particular, it does not contain P 4 as an induced subgraph (see Section 1.1.2). Now, add a vertex v adjacent to all vertices x i for 1 ⩽ i ⩽ k, as shown in Figure 5.1. The resulting graph H + v is not a cograph any more, since it contains several P 4 . Removing one vertex among {x i , y i } for all 1 ⩽ i ⩽ k produces a maximal induced sub-cograph of H + v. This means in particular that H + v has at least 2 k maximal induced sub-cographs, which implies that the restricted problem has an exponential number of solutions. Hence, the input restricted problem approach cannot be used for the enumeration of maximal induced sub-cographs with polynomial delay. We will have to use another technique if we want to achieve this time complexity bound. Nevertheless, adding one vertex to a cograph produces only a polynomial number of induced P 4 . In this case, the results presented by Khachiyan et al. in the 2000s [START_REF] Khachiyan | On the dualization of hypergraphs with bounded edge-intersections and other related classes of hypergraphs[END_REF] can be used to obtain an incremental polynomial time algorithm for the enumeration of maximal induced sub-cographs. Since the size of the obstruction is constant, the

MAXIMAL INDUCED SUB-COGRAPHS | 79

algorithm of Eiter & Gottlob [START_REF] Eiter | Identifying the minimal transversals of a hypergraph and related problems[END_REF] can as well be used to achieve incremental polynomial time complexity. We show here that this time complexity can be improved to polynomial delay with the Proximity Search technique (see Section 2.2.5).

As it was shown by Corneil et al. [START_REF] Corneil | Complement reducible graphs[END_REF], a characterisation of cographs is that they can be constructed from an isolated vertex by recursively adding true or false twins to existing vertices. From such a construction, we obtain an ordering v 1 , . . . , v n on the vertices of a cograph H, such that for all j ∈ {1, . . . , n}, v j has at least one (true or false) twin in H[v 1 , . . . , v j ], that we called the twin construction ordering in Section 1.1.2.

Every maximal induced sub-cograph can then be identified with an ordered set of vertices; this is exactly what will be done in the sequel. This is why, for simplicity of notation, we sometimes refer to a solution S as a set of vertices instead of a graph (without introducing any ambiguity on the set of edges, since we are only considering induced subgraphs in this section).

Let G be a graph of which we want to enumerate all maximal induced sub-cographs. To use Proximity Search on this problem, we need:

• an ordering scheme on the maximal induced sub-cographs of G;

• a neighbouring function, enabling to generate from one maximal induced subcograph S some new maximal induced sub-cographs, among which one will provably be closer to a target solution.

Since the twin construction ordering of a cograph is in general not unique, the first thing to do is to make it canonical. This will be done by means of an arbitrary ordering u 1 , . . . , u n on the vertices of G, as for many problems solved with Proximity Search [START_REF] Conte | New polynomial delay bounds for maximal subgraph enumeration by proximity search[END_REF]. According to the arbitrary ordering just defined, we will say that u i is smaller than u j if i < j. The ordering scheme we use for maximal induced sub-cographs is defined as follows.

Ordering scheme. For any maximal induced sub-cograph S of G, the canonical ordering π(S) is the lexicographically smallest twin construction ordering of S, with respect to the arbitrary ordering u 1 , . . . , u n . In particular, for any S, π(S) is a sequence

v 1 . . . v k of vertices of G such that v 1 is the smallest vertex of G belonging to S.
It is worth mentioning that for any maximal induced sub-cograph S of G, the canonical ordering π(S) can be computed in polynomial time from the cotree associated with S, even if this is not required when using the classical Proximity Search framework.

An example of a cograph with its canonical ordering is given in Figure 5.2. In this example, the canonical ordering is 1, 4, 3, 2, 5.

To build the graph of Figure 5.2, we begin with the vertex of smallest id: 1, then 4 is added as a true twin of 1, followed by 3, a false twin of 1 in the subgraph induced by 1, 4, 3; after that 2 is added as a true twin of 1, and finally 5 is added as a false twin of the vertex 4. Equipped with this ordering scheme, we can then define the proximity between two maximal induced sub-cographs of G in the usual manner: if S and S ′ are two solutions, and the canonical ordering of

S ′ is v 1 . . . v |S ′ | , then S ∩ S ′ is the longest prefix v 1 . . . v i of π(S ′ ) such that {v 1 , . . . , v i } ⊆ S. In this case, |S ∩ S ′ | = i.
Recall that this notion of proximity is not symmetric and that the only solution S maximising S ∩ S ′ is S ′ itself. The next step is to define the neighbouring function neighbours that will be used to build the solution graph. Remark that, as the class of cographs is hereditary, the greedy complete function which adds one vertex at a time while the result is a cograph can be used to maximise an induced sub-cograph. This maximisation function runs in polynomial time because the recognition algorithm for cographs does so. Moreover, it is easy to make this complete function deterministic by following the arbitrary ordering u 1 , . . . , u n .

In order to be able to use Proximity Search, the cardinality of neighbours(S) should be polynomial in n for any solution S. We will see that the following neighbouring function satisfies this requirement.

Definition 5.1 (Neighbouring function for maximal induced sub-cographs). Let S be a maximal induced sub-cograph of G. For all x /

∈ S and all y ∈ S, we define

S ′ xy := complete((S \ (N G (x)△N S (y))) ∪ {x, y}).
Then let neighbours(S)

:= S ′ xy | x / ∈ S, y ∈ S .

Each solution has at most a quadratic number of neighbours.

The idea behind this definition of neighbours for maximal induced sub-cographs is to add a vertex x while making sure that x and y become twins (true or false according to their adjacency in G) in S ′ xy . This neighbouring function is illustrated in Figure 5.3, where the circled vertices represent the elements of (N G (x)△N S (y)). Two of them are removed from S so that x and y become twins in (N G (x)△N S (y))) ∪ {x, y}. After that, the induced sub-cograph is maximised. Now, we need to ensure that the neighbouring function that has been defined for maximal induced sub-cographs will not generate induced subgraphs that are not solutions to our problem. It is the purpose of the following lemma.

MAXIMAL INDUCED SUB-COGRAPHS | 81

Lemma 5.2. For every maximal induced sub-cograph S, and for every x /

∈ S, y ∈ S, the graph S ′ xy is a maximal induced sub-cograph of the input graph G.

Proof. Let Ŝ := (S \ (N G (x)△N S (y))) ∪ {x, y} and suppose that Ŝ is not a cograph. Then there is an induced P 4 in Ŝ. Remark that Ŝ \ {x} is a cograph, as an induced subgraph of the cograph S. Hence necessarily x participates to this newly-induced P 4 , and y does not because it is twin with x. But substituting x for y produces an induced P 4 in Ŝ \ {x}, which is excluded. Therefore Ŝ is a cograph. The function complete, when given an induced sub-cograph of G, returns a maximal one. Consequently, S ′ xy is indeed a maximal induced sub-cograph of G. Lemma 5.2 guarantees that the neighbouring function is well-defined and that all neighbours of a solution are also solutions. Therefore, we can consider the supergraph of solutions, whose vertices are the maximal induced sub-cographs of G and an arc (S, S ′ ) exists if and only if S ′ ∈ neighbours(S). Now, it remains to show that this supergraph of solutions is strongly connected; in other words, that every solution can be reached from any other by increasing their proximity at each step.

Lemma 5.3. Let S and S * be two distinct maximal induced sub-cographs of a given graph G. There exist x /

∈ S and y ∈ S such that

|S ′ xy ∩ S * | > |S ∩ S * |. Proof. Denote by v 1 , . . . , v |S * | the canonical ordering of S * . If |S ∩ S * | = 0, then v 1 / ∈ S. Let y ∈ S, then v 1 ∈ S ′ v 1 y and it immediately follows |S ′ v 1 y ∩ S * | ⩾ 1 > |S ∩ S * |. Else, let k be the smallest index such that v k / ∈ S (in this case, |S ∩ S * | = k -1). Since v 1 , . . . , v k is a prefix of the twin construction ordering of S * , there exists i < k such that v k and v i are twins in S * [v 1 , . . . , v k ]. By minimality of k, v i is a vertex of S. Consider S ′ v k v i . It is a cograph by Lemma 5.2. It remains to show that S ′ v k v i contains v 1 , . . . , v k .
For contradiction, assume that there exists j ∈ {1, . . . , k -1} such that

v j / ∈ S ′ v k v i . Since {v 1 , . . . , v k-1 } ⊆ S ∩ S * , it implies that v j ∈ N G (v k )△N S (v i ). But by definition of the canonical ordering of S * , v i and v k are twins in G[v 1 , . . . , v k ], so no vertex of {v 1 , . . . , v k } can be in N G (v k )△N G (v i ). Therefore, S ′ v k v i contains v 1 , . . . , v k . Consequently, |S ′ v k v i ∩ S * | ⩾ k > |S ∩ S * |.
By Lemma 5.3, the supergraph of solutions is strongly connected. In other words, the problem of enumerating all maximal induced sub-cographs with the twin construction ordering scheme is proximity searchable. Then, Algorithm 2.4 can be used to enumerate all maximal induced sub-cographs in polynomial delay. Hence, we can state the following theorem.

Theorem 5.4. Maximal induced sub-cographs of a graph G can be enumerated in polynomial delay and exponential space with Proximity Search.

We also addressed the question of determining if there exists a polynomial delay algorithm computing the minimal cograph completions -or equivalently the minimal cograph deletions, since the class of cographs is self-complementary -of a graph G. As proved in Chapter 4, the corresponding extension problem is NP-complete, so Flashlight Search will not really serve our purposes. As for Proximity Search, finding an appropriate neighbouring function on maximal edge-sub-cographs turned out to be surprisingly difficult. In particular, when trying to adapt the transition function used for maximal induced sub-cographs, we could not make sure that the newly generated subgraphs were cographs. This leads to the following question.

Question 3. Can minimal cograph deletions be enumerated with polynomial delay?

Threshold graphs

In this section, Proximity Search is used to enumerate efficiently the maximal induced threshold subgraphs of a graph G. Unlike for cographs, a good ordering scheme and a good neighbouring function can be derived from the induced case to apply Proximity Search on the minimal threshold deletions. This adaptation of the ordering scheme and neighbouring function to the minimal threshold deletions problem is good news: it implies an efficient algorithm for the enumeration of minimal threshold deletions. Plus, as the class of threshold graphs is self-complementary, it directly implies an efficient algorithm for the enumeration of minimal threshold completions.

Maximal induced threshold subgraphs

By definition, all threshold graphs can be constructed from a single isolated vertex by adding at each step either an isolated vertex or a universal vertex, i.e. a vertex

THRESHOLD GRAPHS | 83

adjacent to all other vertices of the graph [START_REF] Chvátal | Aggregations of inequalities. Studies in Integer Programming[END_REF] (see Section 1.1.2). This construction provides an ordering v 1 , . . . , v n on the vertices of a threshold graph H, such that for all

1 ⩽ i ⩽ n, either v i is isolated in H[v 1 , . . . , v i ], or v i is universal in H[v 1 , . . . , v i ].
Note that finding a maximal induced threshold subgraph is not hard: a greedy algorithm adding vertices one by one while the resulting graph has the threshold property is well-suited for this purpose. As threshold graphs can be recognised in linear time, the greedy algorithm runs in polynomial time.

We will see how maximal induced threshold subgraphs can be enumerated with the help of Proximity Search. First, an ordering scheme is defined for maximal induced threshold subgraphs, relying on their construction ordering. Then, a neighbouring function allows us to transform a solution into another. The last step is to prove that the maximal induced threshold subgraphs enumeration problem with these ordering scheme and neighbouring function is indeed proximity searchable.

Ordering scheme. As it was the case for cographs, sometimes several threshold construction orderings are possible for a same threshold graph. To define a canonical threshold construction ordering on an induced threshold subgraph S of G, it suffices to fix an arbitrary ordering u 1 , . . . , u n on the vertices of G and consider the lexicographically smallest threshold construction ordering of S according to u 1 , . . . , u n .

In Figure 5.4 is represented a threshold graph. There are two possible threshold construction orderings of this graph: 1, 4, 2, 5, 3, 6 and 4, 1, 2, 5, 3, 6. The lexicographically smallest is 1, 4, 2, 5, 3, 6. The black vertices are added as universal, and the white ones are added as isolated vertices. Let G be a graph and let S be a maximal induced threshold subgraph of G. For any x ∈ V \ S, we can define two induced subgraphs of G:

S u x = complete({x} ∪ (S ∩ N (x))) and S i x = complete({x} ∪ (S \ N (x)))

| PROXIMITY SEARCH: POLYNOMIAL DELAY

where complete is the greedy completion function, adding vertices according to the arbitrary ordering defined a priori, while the threshold property is satisfied.

Then, let neighbours(S)

= {S u x | x ∈ V \ S} ∪ {S i x | x ∈ V \ S}.
Each solution has a linear number of neighbours.

The neighbouring function for maximal induced threshold subgraphs is illustrated in Figure 5.5. For a vertex x, two induced subgraphs are built: one in which x is universal, and one in which x is isolated. In this example, after the completion step, x is not universal nor isolated any more but the resulting graphs are maximal induced threshold subgraphs of G. It remains to ensure that the neighbouring function defined here only produces maximal induced threshold subgraphs of G. This is the idea of the following lemma.

Lemma 5.6. If S is a maximal induced threshold subgraph of a graph G, then for all

x ∈ V \ S, S u x and S i x are maximal induced threshold subgraphs of G.

Proof. Let G be a graph and let S be a maximal induced threshold subgraph of G.

It suffices to show that G[{x} ∪ (S ∩ N G (x))] and G[{x} ∪ (S \ N G (x))
] are threshold graphs. After that, the greedy complete function will extend them into maximal induced threshold subgraphs of G.

We know that S induces a threshold graph. Moreover, (S ∩ N G (x)) and (S \ N G (x)) are subsets of S, and since the threshold property is hereditary, they induce threshold subgraphs of S. Now, x is universal to (S ∩ N G (x)) so in particular, it is universal in G[{x} ∪ (S ∩ N G (x))]. As the class of threshold graphs is stable under adding a

THRESHOLD GRAPHS | 85

universal vertex, we immediately deduce that

G[{x} ∪ (S ∩ N G (x))] is a threshold graph. Similarly, x is isolated in G[{x} ∪ (S \ N G (x))],
and since the class of threshold graphs is stable under adding an isolated vertex, then G[{x} ∪ (S \ N G (x))] is a threshold graph.

Consequently, S u x and S i x are maximal induced threshold subgraphs of G.

As before, once we know that all neighbours of a solution are also solutions, it allows us to consider the supergraph of solutions induced by the function neighbours. Let us prove that this supergraph of solutions is strongly connected: this way, the problem is proximity searchable and Algorithm 2.4 can be used to enumerate efficiently the maximal induced threshold subgraphs. Lemma 5.7. Let S and S * be two maximal induced threshold subgraphs of a graph G. Assume that v k+1 is isolated in G[{v 1 , . . . , v k+1 }]. In particular, since we are dealing with induced subgraphs, it implies {v 1 , . . . , v k } ⊆ S * \ N (v k+1 ). Therefore, S i v k+1 contains {v 1 , . . . , v k+1 }, and

There exists x ∈ V such that either |S u x ∩ S * | > |S ∩ S * | or |S i x ∩ S * | > |S ∩ S * |. Proof. Let v 1 , . . . , v |S * | be the canonical ordering of S * . Let k = |S ∩ S * | be the smallest index such that v k+1 / ∈ S (if v 1 / ∈ S, then k = 0). By definition of k, we know that v k+1 / ∈ S. Since v 1 , . . . , v k+1 is a prefix of S * , in particular {v 1 , . . . , v k+1 } ⊆ S * and the induced subgraph G[{v 1 , . . . , v k+1 }] is threshold because S *
|S i v k+1 ∩ S * | > |S ∩ S * |. Similarly, if v k+1 is universal in G[{v 1 , . . . , v k+1 }], the same reasoning implies the inequality |S u v k+1 ∩ S * | > |S ∩ S * |.
From these two lemmas, we deduce that maximal induced threshold subgraphs are proximity searchable, hence the following theorem.

Theorem 5.8. Maximal induced threshold subgraphs of a graph G can be enumerated in polynomial delay and exponential space with Proximity Search.

In fact, it has been proved recently that the input restricted problem for maximal induced threshold subgraphs is polynomial [START_REF] Cao | Enumerating maximal induced subgraphs[END_REF]. This allows us to use the algorithm proposed by Cohen et al. [START_REF] Cohen | Generating all maximal induced subgraphs for hereditary and connected-hereditary graph properties[END_REF] (see Section 2.2.4) to enumerate the maximal induced threshold subgraphs with polynomial delay in polynomial space.

However, being able to enumerate the maximal induced threshold subgraphs with Proximity Search has not become totally pointless. Knowing a suitable ordering scheme for the maximal induced subgraphs problem will help us determine one for the minimal deletions problem, as we will see in the next section.

Minimal threshold deletions

Minimal threshold deletions can also be enumerated with the help of Proximity Search. Since the class of threshold graphs is stable under complement, it is equivalent to enumerate minimal threshold completions as well.

Recall that a minimal threshold deletion of G is a maximal threshold subgraph S of G. Since threshold graphs are closed under adding isolated vertices, it immediately follows that any minimal threshold deletion S satisfies V (S) = V (G). Hence, there will never be any ambiguity on the vertex set, so S will often be used to denote both the subgraph and its set of edges E(S) ⊆ E(G).

Finding one minimal threshold deletion. It has been proved that the class of threshold graphs is sandwich-monotone [START_REF] Heggernes | Single-edge monotonic sequences of graphs and linear-time algorithms for minimal completions and deletions[END_REF]. This means in particular that between two threshold deletions S and T of G such that T ⊆ S, there exists a sequence of single-edge additions allowing to go from T to S. But the edgeless graph T := (V, ∅) is a threshold subgraph of G: therefore it is a threshold deletion of G such that any minimal threshold deletion S satisfies T ⊆ S. Based on this observation, we will show how to find a minimal threshold deletion of G in polynomial time.

Since the edgeless graph is a threshold deletion, it is possible to start from the edgeless graph and try adding one edge at a time while the threshold property is satisfied. We stop when no more edge can be added without breaking the threshold property. Because threshold graphs are sandwich-monotone, we are sure that this procedure will stop only when a maximal threshold edge-subgraph, that is, a minimal threshold deletion of G, is found. Moreover, the threshold property is testable in linear time. Consequently, finding a minimal threshold deletion is possible in polynomial time with this technique.

As in Section 5.2.1, in order to use Proximity Search we need to define an ordering scheme on the solutions (here, on the edges, not on the vertices), and a neighbouring function to go from one solution to some others. The ordering scheme will be adapted from the maximal induced threshold subgraphs case as follows.

Ordering scheme. Let S be a minimal threshold deletion of G. The idea is to order the edges of S in such a way that when a new vertex v i is added in the threshold construction ordering, all the edges incident to v i in S[{v 1 , . . . , v i }] are consecutive and follow the threshold construction ordering. More formally, we consider the sequence ((v j v i ) i<j ) j⩽n , where v 1 , . . . , v n is the canonical (i.e. lexicographically smallest) threshold construction ordering of S. In fact, we can think of it as adding all edges incident to v i in S[{v 1 , . . . , v i }] at the same time.

The proximity between two minimal threshold deletions S and S * is then -as usualthe longest prefix of the canonical ordering of S * included in S.

THRESHOLD GRAPHS | 87

Since threshold graphs are sandwich-monotone, it is possible to derive a polynomial complete function for threshold graphs, trying to add one edge at a time while the resulting subgraph is threshold, and stopping when no more edge can be added without breaking the threshold property. Such a completion function returns a maximal induced threshold edge-subgraph, by definition of being sandwich-monotone.

Then, to transform a solution into another, the technique will be to choose a vertex and try to make it universal. We define the following neighbouring function. Definition 5.9 (Neighbouring function for minimal threshold deletions). Let G be a graph and let S be a minimal threshold deletion of G. For a vertex x of G, we will build a graph S x in which x is universal in the construction ordering. We define E G (x) := {xt | t ∈ N G (x)}, and consider the following sets of edges of G: The neighbouring function for minimal threshold deletions is illustrated in Figure 5.6. The vertex x is made universal by adding some edges and removing others. In this example, after the completion step, x is not universal any more but the resulting graph is a minimal threshold deletion of G. As before, we need to ensure that only solutions will be computed by neighbours.

1. E x (x) := E G (x); 2. for each v ∈ N G (x), E x (v) := {vw | w ∈ N S (v) ∩ N G (x)} ∪ {vx}; 3. for every other vertex v, E x (v) := ∅. Let S x := complete v∈V E x (v)
Lemma 5.10. If S is a minimal threshold deletion of a graph G, then for all x ∈ V , S x is a minimal threshold deletion of G.

Proof. Let x ∈ V . It suffices to show that S := v∈V E x (v) is a threshold graph.
In S, all non-neighbours of x are isolated vertices. Besides, adjacencies between vertices of N G (x) have not been modified from S. Moreover, since S is a threshold graph, S[N G (x)] is also a threshold graph; the addition of x as a universal vertex in S[N G (x) ∪ {x}] implies that S[N G (x) ∪ {x}] is also a threshold graph. Therefore, as the union of a threshold graph and isolated vertices is a threshold graph, S is a threshold graph.

It is then possible to apply the polynomial complete function to build S x , which is a minimal threshold deletion of G.

Once we know that all neighbours of a solution are also solutions, we can consider the supergraph of solutions. Let us prove that this supergraph of solutions is strongly connected.

Lemma 5.11. Let S and S * be two minimal threshold deletions of a graph G. There

exists x ∈ V such that | S x ∩ S * | > |S ∩ S * |.
Proof. Let v 1 , . . . , v n be the threshold construction ordering of S * , and consider the associated edge canonical ordering.

Let v k v i be the first edge of S * which does not appear in S. By definition, the neighbours of v k in S v k are all the neighbours of v k in G. Necessarily, we have the inclusion

N S * (v k ) ⊆ N Sv k (v k ). Hence any edge incident to v k in S * is also present in S v k .
Moreover, if an edge v j v i with j < k is present in S * , then it is also present in S by definition of v k v i as the first edge of S * which does not appear in S. Since v k v i is an edge of S * , it means that v k is universal in S * [v 1 , . . . , v k ]. Therefore every edge v j v i with j < k appearing in S * is an edge joining two neighbours of v k in G: it is not removed by the transition operation, so it appears in S v k .

Hence

S v k satisfies | S v k ∩ S * | > |S ∩ S * |.
From these two lemmas, we deduce that minimal threshold deletions are proximity searchable, hence the following theorem. Theorem 5.12. Minimal threshold deletions (resp. completions) of a graph G can be enumerated in polynomial delay and exponential space with Proximity Search.

In the case of threshold deletions, it was possible to adapt the canonical ordering and neighbouring function of the maximal induced threshold subgraphs case, in order to apply Proximity Search. Advantage was taken from the "sandwich-monotonicity" of threshold graphs. In fact, being sandwich-monotone (or equivalently, strongly accessible) is a very powerful property, as we will see in the next section.

MINIMAL CHORDAL COMPLETIONS | 89

Minimal chordal completions

Chordal completions were first introduced in the 1970s as a tool for solving large sparse systems of linear equations [START_REF] Rose | A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equations[END_REF][START_REF] Rose | Algorithmic aspects of vertex elimination on graphs[END_REF]. This was inspired by an algorithm known as the Elimination Game, proposed by Parter in 1961 and introducing the link between sparse matrix computation and graphs [START_REF] Parter | The use of linear graphs in gauss elimination[END_REF]. More precisely, minimal chordal completions are used to compute efficiently what is called the fill-in in sparse matrix factorisation. In fact, finding a perfect elimination ordering of a chordal graph corresponds to finding an ordering for the Gaussian elimination of its adjacency matrix [START_REF] Ohtsuki | A fast algorithm for finding an optimal ordering for vertex elimination on a graph[END_REF]. Chordal completions are still used nowadays for this purpose, as they provide indeed a very powerful tool [START_REF] Córdoba | On generating random Gaussian graphical models[END_REF]. However, this is far from being the only reason for minimal chordal completions to be interesting.

Being able to compute a tree-decomposition of a graph is useful in many situations. For example, one may want to compute the treewidth (minimum size of a bag minus one) since it appears as a parameter in many optimisation problems [START_REF] Robertson | Graph minors. iii. planar tree-width[END_REF]. But other parameters depend on finding a tree-decomposition, e.g. the so-called tree-independence number [START_REF] Dallard | Treewidth versus clique number. II. Tree-independence number[END_REF]. And the notion of being optimal for a tree-decomposition hugely depends on which parameter has to be optimised (the largest size of a bag, the smallest size of a stable set in a bag, the largest diameter of a bag. . .) [START_REF] Carmeli | Efficiently enumerating minimal triangulations[END_REF][START_REF] Dallard | Treewidth versus clique number. II. Tree-independence number[END_REF]. This is why finding inclusion-wise minimal chordal completions is in some situations even more relevant than finding a minimum-cardinality one (which is NP-complete anyway [START_REF] Yannakakis | Computing the minimum fill-in is NP-complete[END_REF]). Moreover, as the notion of "good" minimal chordal completion is not always easy to model, the enumerative approach makes a lot of sense. This way, one can generate a bunch of minimal chordal completions and choose which one best suits the problem according to their own criteria.

For all these reasons, it is interesting to be able to generate efficiently minimal chordal completions of a graph. For further reference about minimal chordal completions (from another viewpoint than enumeration), we refer the reader to the very complete survey by Heggernes [START_REF] Heggernes | Minimal triangulations of graphs: a survey[END_REF].

The question of enumerating all minimal chordal completions of a given graph has been addressed in 2017 by Carmeli, Kenig & Kimelfeld [START_REF] Carmeli | Efficiently enumerating minimal triangulations[END_REF], who proposed a highly non-trivial algorithm. Their algorithm runs in incremental polynomial time; its total complexity is quadratic in the number of solutions, and to avoid duplication of solutions, requires exponential space. The algorithm is based on a result by Parra & Scheffler [START_REF] Parra | Characterizations and algorithmic applications of chordal graph embeddings[END_REF], linking the minimal triangulations of a graph to the maximal stable sets of an auxiliary graph. In a later version of their paper, Carmeli et al. even proved that, under the Exponential Time Hypothesis, their approach could not be improved to achieve polynomial delay [START_REF] Carmeli | Efficiently enumerating minimal triangulations[END_REF]. This intractability result also holds for the exponential space.

In the paper of Carmeli et al. [START_REF] Carmeli | Efficiently enumerating minimal triangulations[END_REF][START_REF] Carmeli | Efficiently enumerating minimal triangulations[END_REF] and at a Dagstuhl seminar [START_REF] Boros | Enumeration in data management (dagstuhl seminar 19211)[END_REF], it was left as an open problem whether a polynomial delay or a polynomial space algorithm for the enumeration of minimal chordal completions could be obtained. Here, we answer this question concerning the time complexity. As for the space usage, it will be treated in Chapter 6.

The other two problems concerning chordal graphs, namely the maximal induced chordal subgraphs and the minimal chordal deletions enumeration, have been addressed by Conte et al. in the light of Proximity Search [START_REF] Conte | Proximity search for maximal subgraph enumeration[END_REF]. Both were proved to admit a polynomial delay algorithm, as well as the maximal induced connected chordal subgraphs problem. However, they could not manage to adapt Proximity Search to the minimal chordal completions enumeration.

In the sequel, we exhibit a polynomial delay and exponential space algorithm relying on Proximity Search to list all minimal chordal completions of a graph. First, Section 5.3.1 is devoted to the definition of an ordering scheme that will suit to minimal chordal completions. Then in Section 5.3.2, we introduce the neighbouring function and prove that the problem is proximity searchable. As a consequence, we obtain a polynomial delay algorithm for the enumeration of minimal chordal completions.

Ordering scheme for chordal completions

When looking for an ordering scheme for chordal completions, a property that turns out to be crucial is that of being sandwich-monotone (as it was the case for threshold deletions). It has been proved by Rose, Tarjan & Lueker that the class of chordal graphs is sandwich-monotone [START_REF] Rose | Algorithmic aspects of vertex elimination on graphs[END_REF]. This immediately implies that for any two chordal completions F 1 and F 2 of G, if F 1 ⊆ F 2 there exists a sequence of single-edge removals that permits to go from F 2 to F 1 . It rephrases as the following lemma. Lemma 5.13 ([75, Lemma 2]). Chordal graphs are sandwich-monotone. In particular, for any graph G, the chordal completions of G are sandwich-monotone.

The general idea is then to use the "sandwich-monotonicity" of chordal completions to derive a suitable ordering scheme. Then, we will use this ordering scheme in order to apply Proximity Search.

The Proximity Search framework has been designed to enumerate the inclusion-wise maximal sets of a set system. However, the same framework could as well be applied to the enumeration of inclusion-wise minimal sets of a set system, by considering the complements of the solutions. It is the approach we adopt for the enumeration of minimal chordal completions.

To this effect, we will not work directly with the edge sets of the completions but rather with the sets of their non-edges. For the input graph G = (V, E), let us denote by E c the set of its non-edges G, that is to say,

E c = V 2 \ E.
Here, a chordal completion is identified with its set of fill edges. In other words, we call a chordal completion of

MINIMAL CHORDAL COMPLETIONS | 91

G a set F ⊆ E c , such that the graph (V, E ∪ F ) is chordal. The set of all chordal completions of G is denoted by F, and the set of all minimal chordal completions of G is denoted by F min .

Moreover, we consider for any completion F its complement F , defined as F := E c \F . The goal of this section is to apply Proximity Search to the set F := {F | F ∈ F} in order to enumerate its maximal elements. That is to say, the set we want to enumerate with Proximity Search is

F max := max(F) = {F | F ∈ F min }.
From now on, the elements of E c (the non-edges of G) are assumed to be arbitrarily ordered. The following definitions are similar to the ones given in the paper by Conte et al. [START_REF] Conte | Listing maximal subgraphs satisfying strongly accessible properties[END_REF] but are defined on F instead of F.

Let F be a chordal completion of G and X be any subset of E c . The set X can be seen as the set from which removing elements is allowed. We define:

• Candidates(F, X) := {e ∈ X ∩ F : F \ {e} ∈ F} • Candidates(F ) := Candidates(F, F ) • c(F, X) := min(Candidates(F, X)) • c(F ) := min(Candidates(F ))
where the minimum is taken according to the arbitrary ordering on the elements of E c . Now, given a chordal completion F and a set X ⊆ E c , we denote by Del(F, X) the chordal completion included in F by iteratively removing c(F, X) from F at each step, until Candidates(F, X) it empty. Finally, we define Del(F ) := Del(F, F ). Note that, for any F , X, computing Del(F, X) corresponds to the following procedure. Function 5.1: Del(F, X)

1 while Candidates(F, X) ̸ = ∅ do 2 remove c(F, X) from F ; 3 return F Determining if Candidates(F, X) is empty or computing c(F, X)
is not hard: it suffices to try to remove one edge at a time, following the arbitrary order set at the beginning, until one edge is found whose removal leaves the graph chordal, or until all edges have been tested. This can be done in polynomial time because chordality can be tested in linear time [START_REF] Tarjan | Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs[END_REF]. Then, Function 5.1 consists in a polynomial number of calls to this procedure. Consequently, Del(F, X) is computable in polynomial time.

In fact, Function 5.1 has another advantage, stated as the following remark.

Furthermore, note that E c is a chordal completion of G: it corresponds to the clique completion. This immediately implies, by Remark 5.14, that E c can be turned into a minimal chordal completion in a deterministic manner. As a result, a minimal chordal completion of G can be found in polynomial time by computing Del(E c ).

Before going further, let us have a look on how the Function Del is used to find a minimal chordal completion of a graph. In the example of Figure 5.7, the input graph G is a C 6 , that is, a cycle on six vertices named a, b, c, d, e, f . At first, all the possible fill edges are added. Then, the fill edges are considered in lexicographic order; at each step we try to remove the lexicographically smallest fill edge whose removal does not create a chordless C 4 . In this example, at the moment the edge bf is considered, its removal creates a chordless C 4 . But the fact that E c is a chordal completion of G has even stronger implications, as stated in the following lemma.

Lemma 5.15. If F is a minimal chordal completion of G, then Del(E c , F ) = F .
Proof. By Remark 5.14, it holds Del(E c , F ) ∈ F min , and F ⊂ Del(E c , F ). As a result, since the only minimal solution containing

F is F itself, then Del(E c , F ) = F .
In the light of Lemma 5.15, we will now be able to define a suitable ordering on the solutions. Indeed, the procedure followed to compute Del(E c , F ) provides an ordering on the elements of F by considering the order in which the elements of F are removed to obtain F . From this ordering, we can define for any chordal completion F the canonical ordering Can(F ) := s 1 , ..., s |F | of F as follows:

• s 1 := c(E c , F ); • for all 1 ⩽ i < |F |, s i+1 := c(E c \ {s 1 , ..., s i }, F ).

MINIMAL CHORDAL COMPLETIONS | 93

Canonical ordering. For a set F and its canonical ordering Can(F ) := s 1 , ..., s |F | we define F i as the ith prefix of F , that is, the set of elements {s 1 , ..., s i } ⊆ F , and we set

F i := E c \ F i .
By definition of Candidates(E c , F ), any prefix F i of this ordering belongs to F. In other words, F i denotes the chordal completion of G, not necessarily minimal, obtained by removing the ith prefix of Can(F ) from the clique completion. This ordering will be used to measure the proximity between two solutions in order to call the Proximity Search algorithm for minimal chordal completions. Note that it can be computed in polynomial time for any solution, the complexity being essentially this of calling Function Del.

We now define the notion of proximity between two solutions that will be used in the sequel. For F 1 and F 2 two minimal completions of G, let Can(F 2 ) = f 1 , ..., f k be the canonical ordering of F 2 . The proximity F 1 ∩ F 2 between F 1 and F 2 is defined as the largest i ⩽ k such that {f 1 , ..., f i } ⊆ F 1 . The notion defined here corresponds to the standard proximity measure that is usually adopted when using the Proximity Search framework [START_REF] Brosse | Efficient enumeration of maximal split subgraphs and induced sub-cographs and related classes[END_REF][START_REF] Conte | Listing maximal subgraphs satisfying strongly accessible properties[END_REF][START_REF] Conte | New polynomial delay bounds for maximal subgraph enumeration by proximity search[END_REF] and it is not symmetric in general.

Note that the proximity is defined here on the set of elements of E c (that is to say, non-edges of G) which do not belong to the chordal completion. Since we are working on both the completions and their complements, by a slight abuse of language, when we speak about the proximity between two minimal completions, we actually mean the proximity between their complement sets.

Polynomial delay algorithm

We show in this section that the ordering scheme Can defined above is proximity searchable. Since the idea is to consider the complement sets of minimal completions rather than the completions themselves, we will seek to maximise the set of common non-edges between two minimal completions in order to increase the proximity. So, we actually show that Can is a proximity searchable ordering scheme of F.

The first goal is to define a suitable neighbouring function on the class of chordal graphs. Any solution must have a polynomial number of neighbours, each of them being computable in polynomial time in order to guarantee the polynomial delay when applying Proximity Search.

Given a chordal graph H and an edge e = {x, y} ∈ E(H), the flip operation Flip(H, e) consists in removing e from H, and turning the common neighbourhood of x and y into a clique. More formally, if

H ′ = Flip(H, e), then V (H ′ ) = V (H) and E(H ′ ) := (E(H) \ {e}) ∪ {uv | u, v ∈ N H (x) ∩ N H (y)}. The flip operation is illustrated in Figure 5.8.
Since H is chordal, the removal of e can create several chordless C 4 of which e was the only chord. We will see that completing the common neighbourhood of x and y Proof. Assume (for contradiction) that H ′ contains a chordless cycle C of length ℓ > 3. Suppose C contains only edges of H. Since H is chordal, it does not contain long induced cycles. Then necessarily C is a C 4 of H of which e was the unique chord, for otherwise there would be an induced cycle of length at least 4 (either C or a cycle made from e and edges of C) in the chordal graph H. By definition, the flip operation adds an edge between the other two vertices of C, meaning that C has a chord in H ′ . This cannot happen.

Therefore, C contains an edge e ′ = {z, t} added by the flip operation (i.e. e ′ is an edge of H ′ but not of H). Since C contains the edge e ′ , it does not contain any other fill edge added by the flip operation, otherwise a chord of C would also be added by the flip. Plus, we assumed that e ′ is added by the flip operation, so necessarily both z and t belong to N H (x) ∩ N H (y). Therefore, P := C -{e ′ } is a z -t path of H ′ , disjoint from x, y, and e ′ . Remark that P is an induced path of H since it contains only edges of H, that is, z and t are in the same connected component of H \ {x, y}, as illustrated in Figure 5.9 (left). Claim 5.17. Every vertex of P is in N H (x) ∩ N H (y).

Proof. Suppose that there exists a vertex s of P which is not a neighbour of x. We will show that there exists in H a chordless cycle containing s and x.

As s is not a neighbour of x, and z is by hypothesis, there exists q ∈ N (x) a vertex of P that is between z and s, and closest to s on P . Similarly, let r ∈ N (x) be a vertex of P that is between t and s, and closest to s.

The q -r subpath of P induced by all vertices between q and r is therefore a chordless path of H of which all internal nodes are non-neighbours of x. It follows that adding x to this q -r subpath creates a chordless cycle of length at least 4 in H. The chordless cycle is highlighted on Figure 5.9 (right). This is excluded, so all vertices of P are neighbours of x in H. .9: There is a z -t path P in H ′ , disjoint from e ′ . On the right, the vertices q, s, r and x belong to a chordless cycle of H. The edge xs does not belong to the graph.

By symmetry in x and y, we also deduce that all vertices of P are neighbours of y.

The claim is proved: every vertex of P is in N H (x) ∩ N H (y).

By the previous Claim, the flip operation turns the cycle C into a clique. Hence C has length 3, a contradiction.

When dealing with chordal completions, the notation of the flip operation will be slightly adapted: for F ∈ F, and e ∈ F (e is always chosen among the fill edges of the completion), we will omit G in our notation and write Flip(F, e) instead of, for example, Flip(G ∪ F, e).

From Lemma 5.16, we are then able to deduce the following equivalent in terms of chordal completions. Proof. The only edge that is in F but not in Flip(F, e) is e. Since e ∈ F , it implies that all edges of G are still in G Flip(F,e) . As Flip(F, e) is chordal by Lemma 5.16, in particular it is a chordal completion of G.

We are now ready to explain the neighbouring function used to enumerate F min . Observe that Flip(F, e) is a chordal completion of G that is not necessarily minimal. It needs to be minimised with Function Del in order to become a solution of our problem.

Neighbouring function. Given F ∈ F min and e ∈ F , we define the successor of F according to e as the minimal completion Succ(F, e) := Del(Flip(F, e)). We now define the neighbours of a solution F as neighbours(F

) := {Succ(F, f )|f ∈ F }.
As a corollary of Remark 5.14 and Lemma 5.18, Succ(F, e) ∈ F min . Observe that each solution has a polynomial number of neighbours since | neighbours(F )| ⩽ |F |. Now that the neighbouring function is properly defined, it is easy to notice that it can be computed in polynomial time. However, it remains to prove that minimal chordal completions are proximity searchable. To achieve this we need to prove that the supergraph of solutions defined by the relation neighbours is strongly connected. This will allow us to use Proximity Search on the set of minimal chordal completions of a graph G. Lemma 5.19. Let F 1 and F 2 be two minimal chordal completions of a graph G. Let f 1 , . . . , f k = Can(F 2 ) and let i := F 1 ∩ F 2 . Then the following statements hold:

1. f i+1 / ∈ F 1 ; 2. Succ(F 1 , f i+1 ) ∩ F 2 > i.
Proof. 1. By definition of i as the length of the largest prefix of Can(F 2 ) included in

F 1 , it holds f i+1 / ∈ F 1 . 2. Let F ′ := Flip(F 1 , f i+1
), we will show that F ′ increases the proximity with F 2 by proving the inclusion {f 1 , ...,

f i+1 } ⊆ F ′ . Since Succ(F 1 , f i+1 ) ⊆ F ′ , it implies that {f 1 , ..., f i+1 } ⊆ Succ(F 1 , f i+1 ), and finally Succ(F 1 , f i+1 ) ∩ F 2 ⩾ i + 1.
First, notice that by definition of Flip, f i+1 / ∈ F ′ . Let x and y be the two endpoints of f i+1 . Assume for contradiction that an edge f j , j ⩽ i is added when completing N G F 1 (x) ∩ N G F 1 (y) into a clique. As stated earlier, the notation F 2 i+1 is used to denote the set {f 1 , ..., f i+1 }, which is included in F 2 , and F i+1 2 represents the associated chordal completion.

Let u and v be the two endpoints of f j . Then x, u, y, v forms a C 4 of which f i+1 was the unique chord in G F 1 . By definition of Can(F 2 ), the (i + 1)th prefix F i+1 2 is a chordal completion of G, and since neither the chords f j nor f i+1 belong to it, at least one of the edges xu, uy, yv or vx does not belong to F i+1 2 since otherwise x, u, y, v would form a chordless C 4 in F i+1 2 . Assume without loss of generality that xu / ∈ F i+1 2 . Since F 2 i+1 = {f 1 , ..., f i+1 }, there exists ℓ ⩽ i such that xu = f ℓ . But then we have found an edge f ℓ / ∈ F 1 with ℓ ⩽ i, which contradicts the assumption

F 1 ∩ F 2 = i. Consequently, Succ(F 1 , f i+1 ) ∩ F 2 > i.
As a consequence, since the polynomially computable function Succ is able to increase the proximity between two solutions, the ordering scheme defined by Can is proximity searchable. More formally, the set of minimal chordal completions of a graph G, with the ordering scheme Can and the function neighbours defined on F by neighbours(F ) := {X | X ∈ neighbours(F )} is proximity searchable.

Therefore, Algorithm 2.4 can be used to enumerate F max or equivalently F min with polynomial delay. Yet, applying Proximity Search usually gives polynomial delay with exponential space: to avoid duplication it is necessary to store all the generated solutions in a lookup table. Each newly generated solution is then searched in the

MINIMAL CHORDAL COMPLETIONS | 97

table in polynomial time. The complexity results achieved so far on minimal chordal completions are summarised in the following Theorem.

Theorem 5.20. There exists a polynomial-delay algorithm for the enumeration of minimal chordal completions of a graph, running in exponential space.

Remark that, to prove minimal chordal completions are proximity searchable, we needed in the proof of Lemma 5.19 a special property satisfied by the ordering scheme Can. Indeed, in order for the proof to be correct, the prefixes of a solution must induce partial solutions, here non-necessarily minimal chordal completions of G. In the present case, this property is intimately linked with the "sandwich-monotonicity" of chordal completions. Although this requirement seems in a sense quite natural, it is not always satisfied: for example, the ordering scheme we used for minimal threshold deletions does not have this property.

Proximity Search can be used on all the problems we considered in this chapter. This powerful technique allows us to enumerate maximal induced sub-cographs and threshold subgraphs, as well as minimal threshold and chordal completions with a remarkable efficiency. The main drawback of Proximity Search is that in general it uses exponential space: one must store all generated solutions in order to determine if the newly found one has already been generated in the past.

The next goal is to find a general technique able to achieve both polynomial delay and polynomial space for many enumeration problems. This is why in the next chapter, we will expose a new technique that allows us to achieve polynomial space for all the problems we solved here with Proximity Search, and many others.

Chapter 6 Proximity Search extensions

In this chapter, we reduce the space usage of some enumeration problems solved with Proximity Search. To this effect, we propose some extensions of the framework. Parts of the results of this chapter appear as joint work with Vincent Limouzy and Arnaud Mary in the proceedings of the 2022 ICALP conference [START_REF] Brosse | Polynomial delay algorithm for minimal chordal completions[END_REF].

T he Proximity Search framework has proved efficient concerning the enumeration of maximal (induced or not) subgraphs satisfying a property P.

However, this technique presents some limitations, in particular on the space usage of the algorithms based on it. This is why the present chapter is dedicated to the formulation of some extensions of the Proximity Search framework.

First, we formalise the idea that was used to derive an ordering scheme for minimal threshold deletions from the one used for maximal induced threshold subgraphs in Chapter 5. In fact, we show that having an ordering on the elements of a solution is not strictly necessary: it is possible to add a bunch of elements at the same time while keeping a good notion of proximity.

Then, in the light of the general framework newly defined, we introduce a new method called Canonical Path Reconstruction, aiming to reduce the space usage of Proximity Search on several enumeration problems. This technique consists in the polynomial-time computation of a function Parent with which it is possible to define a spanning arborescence on the supergraph of solutions in the manner of Reverse Search.

In Sections 6.1 and 6.2, we set ourselves in the more general framework of set systems, where Proximity Search is meant to be applied. The name set system simply denotes a family of subsets -often denoted by F -of a ground set U .

In fact, induced subgraphs and graph deletions, as well as graph completions (even if this last case is a little bit less obvious) correspond to particular set systems. An induced subgraph can be seen as a set of vertices of the input graph, and a graph deletion -provided the graph property under consideration is closed under adding isolated vertices, which is always the case for the graph properties studied in this thesiscan be seen as a set of edges. There is an obvious bijection between the set of all (induced or not) P-subgraphs, for a property P, and the family of all sets of vertices (resp. edges) inducing P-subgraphs.

What we enumerate with Proximity Search are the inclusion-wise maximal elements of a set system. Sometimes, the set system is closed under inclusion (as for induced subgraphs satisfying a hereditary property), but in general it is not the case. Think for example about the minimal chordal completions of a graph, for which the corresponding set system is not hereditary.

Therefore, considering the elements of a solution one by one may not be the most accurate approach: sometimes, it is better to add a set of elements and to treat it as a whole, than to split it arbitrarily to fit an element-by-element framework. For this reason, we introduce in the next section a generalisation of the Proximity Search technique.

General set proximity

In certain cases, we are not able to define an interesting ordering on the elements of a solution, e.g. when dealing with maximal edge-subgraphs that satisfy a certain property. Recall when Proximity Search has been applied to enumerate minimal threshold deletions in Chapter 5: the canonical ordering was adapted from the induced subgraphs case to simulate the simultaneous addition of several edges. In this situation, as in some others, we would prefer to build a solution by adding at each step not one element but a bunch of elements all at the same time.

However, this cannot be done directly with Proximity Search since this method precisely relies on the encoding of solutions as ordered sequences of elements. To cope with this limitation, we propose here a generalisation of Proximity Search. Instead of considering an ordering on the elements of the ground set, we define an ordering scheme as an ordered sequence of disjoint subsets of the ground set.

Let us consider a set system F on a ground set U . We are interested in enumerating the set F max of all inclusion-wise maximal elements of F. Definition 6.1 (Set-ordering scheme). A set-ordering scheme Π of F is a function that associates to each F ∈ F an ordered partition Π(F ) = E 1 , . . . , E k of F such that for any F ∈ F and any i ⩽ k, there exists a family T i (depending on E 1 , . . . , E i-1 ) of subsets of U , called admissible sets, with E i ∈ T i .

GENERAL SET PROXIMITY | 101

In particular, being a partition of F means that k i=1 E i = F , and for any i ̸ = j, E i ∩ E j = ∅. Interestingly, this new notion of ordering scheme could even be considered on set systems that are not accessible1 , but satisfy weaker conditions.

With this definition of a set-ordering scheme, an ordering scheme in the usual sense (defined in Section 2.2.5) is a set-ordering scheme where at step i, the sets E j , j ⩽ i, are in fact the singletons {v j }, and we have

T i = {{v} | v / ∈ {v 1 , . . . , v i-1 }}.
Ordering schemes can possess some nice properties. For example, it often happens that for a given (set-)ordering scheme, all prefixes of a solution induce partial solutions, that is, non-necessarily maximal elements of the family F. Note that this property is automatically satisfied when dealing with hereditary set systems, as a prefix is in particular a subset. This corresponds to the "natural" property that was used in the proof of Lemma 5.18 when showing that the enumeration of minimal chordal completions was indeed proximity searchable. It is called the prefix property and is in fact a typical requirement for Proximity Search-based techniques such as canonical reconstruction [START_REF] Conte | Proximity search for maximal subgraph enumeration[END_REF].

Definition 6.2 (Prefix property). A set-ordering scheme Π of F has the prefix property if for any

F ∈ F with Π(F ) = E 1 , . . . , E k , for any i ⩽ k, i j=1 E j ∈ F.
In other words, all prefixes of Π(F ) induce partial solutions (non-necessarily maximal elements of F).

When the ordering scheme for threshold deletion was adapted from the induced subgraphs case, the principle was the following. We considered a solution S as a set of edges, and started from the edgeless graph on V (G). Then, we simulated the addition of a new vertex v k by adding all edges between v k and the v i , i < k, at the same time (in an arbitrary order). In fact, it corresponds to this new notion of set-ordering scheme.

At step k, the set T k of admissible sets is the collection of all neighbourhoods in {v 1 , . . . , v k-1 } of the remaining vertices, that is,

T k = {R ⊆ {vw | w ∈ N G (v) ∩ {v 1 , . . . , v k-1 }} | v / ∈ {v 1 , . . . , v k-1 }} .
Then,

E k = {v k w | w ∈ N S (v k ) ∩ {v 1 , . . . , v k-1 }}.
Moreover, the graph on V (G) with edge set E 1 ∪ . . . ∪ E k obtained at step k is a threshold graph, since it corresponds to the graph induced in S (a threshold graph) by {v 1 , . . . , v k }, plus some isolated vertices.

Therefore, adapting the usual ordering scheme to threshold deletions produces in fact a set-ordering scheme having the prefix property.

In fact, one can go further. When deriving the set-ordering scheme on threshold deletions, what was actually used is that the class is hereditary and closed under adding isolated vertices. Therefore, such a set-ordering scheme can be constructed for other graph properties, e.g. for cograph deletions. We state the following observation. Observation 6.3. For a hereditary graph class P, closed under adding isolated vertices, with a "usual" ordering scheme for induced P-subgraphs, a set-ordering scheme with the prefix property can always be derived for P-deletions.

We have seen that set-ordering schemes extend the classical notion of ordering scheme. Let us now look at how the other aspects of Proximity Search are adapted in the general set framework. In particular, the new notion of set-ordering scheme implies a new definition of the proximity on solutions seen as ordered partitions rather than sequences.

Proximity. Given two sets F and F ′ ∈ F max with Π(F ′ ) = E 1 , . . . , E k , the proximity F ∩ F ′ between F and F ′ is the largest index i ⩽ k such that E j ⊆ F for all j ⩽ i, or in other terms, i j=1 E j ⊆ F . With this definition, the proximity is not a set any more (as it was the case in the original Proximity Search), but a number. When the sets E i are singletons, this new proximity corresponds to the cardinality of the "classical" proximity. In practice, this does not change a lot from the classical framework, since Proximity Search is about increasing the proximity, which means "increasing the number of elements in the proximity" if the proximity is defined as a set. Therefore, using the corresponding number to define the proximity does not lose any useful information compared to the usual definition.

For simplicity of notation, we keep the same symbol ∩ as before to denote the proximity. This is why, unlike in Chapter 5, for any two solutions F and F ′ , the neighbouring function will not increase |F ∩ F ′ | but simply F ∩ F ′ .

In fact, with this newly defined proximity notion, the definition of a proximity searchable ordering scheme remains almost the same. The only real difference lies in the definition of the proximity function used in practice. We recall here what it means for a problem to be proximity searchable, according to the definition given in the original paper [START_REF] Conte | New polynomial delay bounds for maximal subgraph enumeration by proximity search[END_REF]. Definition 6.4 (Proximity searchable). An enumeration problem is called proximity searchable if one solution can be computed in polynomial time, and there exists a proximity function ∩ and a polynomial-time-computable function neighbours such that for any two solutions F , F * ∈ F max , there exists F ′ ∈ neighbours(F ) satisfying

F ′ ∩ F * > F ∩ F * .

CANONICAL PATH RECONSTRUCTION | 103

Therefore, our framework corresponds to a more general case of Proximity Search than the one usually considered.

By definition, a polynomial-time computable function neighbours, able to increase the proximity to a target solution, induces a path between any two solutions in F max . This guarantees that the supergraph of solutions is strongly connected -provided that the neighbouring function is well-chosen -and that the solution space can be explored in a DFS manner with Algorithm 2.4. This can be stated as follows, as an analogous of the original Proximity Search theorem [START_REF] Conte | New polynomial delay bounds for maximal subgraph enumeration by proximity search[END_REF]. Theorem 6.5 (Set Proximity Search). For a given enumeration problem, if there exists a set-ordering scheme and a polynomial-time-computable function neighbours able to increase the proximity to a target solution, then the enumeration problem admits a polynomial delay enumeration algorithm.

The novelty of our approach is to measure the proximity according to an ordering scheme on element sets, and not just single elements. In particular, with this definition, the set of all known proximity searchable problems is enlarged. In this sense, the general set proximity framework extends the usual Proximity Search. Now that the framework is set up, it is time to see which improvements can be made in order to achieve better space complexity.

Canonical path reconstruction

In this section, we consider a set system F on the ground set U , and we assume that the problem of enumerating the set F max of all maximal elements of F is proximity searchable. In particular, this means that there exists Π a set-ordering scheme on F, a function neighbours able to increase the proximity to a target solution, and F 0 ∈ F max a "reference solution" that can be found in polynomial time. The goal is to design a new Proximity Search-based technique achieving polynomial space. Some work has already been done about the space complexity of enumeration with Proximity Search. In the original Proximity Search paper [START_REF] Conte | Proximity search for maximal subgraph enumeration[END_REF], the authors present a technique that allows them to enumerate the maximal elements of a set system, provided this set system is commutable, that is, satisfies the following definition. Definition 6.6 (Commutable set system). A set system F is called commutable if it is strongly accessible and satisfies the commutable property. Formally, a commutable set system satisfies the following two conditions.

strongly accessible: ∀X, Y ∈ F, X ⊆ Y, ∃y ∈ Y \ X, X ∪ {y} ∈ F; commutable property: ∀X, Y ∈ F, X ⊆ Y, ∀a, b ∈ Y \ X, (X ∪ {a} ∈ F) ∧ (X ∪ {b} ∈ F) =⇒ X ∪ {a, b} ∈ F.
Intuitively, being commutable means that if two elements can be added separately while staying in the family, then both can be added at the same time. This requirement, however, is quite strong: many set systems are not commutable. For example, although threshold graphs are strongly accessible (see Section 5.2), the commutable property is not satisfied by threshold graphs, as illustrated in Figure 6 By definition, commutable set systems are in particular strongly accessible (but we have just seen that the converse is not true). Moreover, hereditary set systems are commutable. A summary of the inclusions between the different properties of set systems is presented in Figure 6.2. The idea now is to translate the Reverse Search arborescence into our general set proximity framework, and determine under which conditions this arborescence actually exists.

Accessible

Strongly Accessible Commutable

Since the problem under consideration is assumed to be proximity searchable, for any F ∈ F max , there exists a path from F 0 to F in the supergraph of solutions. It is then possible to consider a function Next which for any two solutions F and F * in F max , chooses deterministically a solution

F ′ ∈ neighbours(F ) such that F ′ ∩ F * > F ∩ F * .
The deterministic choice of the solution increasing the proximity with F * can be seen as the following procedure. First, define a preference order, denoted by < Next , on

CANONICAL PATH RECONSTRUCTION | 105

the set of neighbours of the current solution. Then, select the minimum one according to < Next . The typical -but not mandatory -choice for Function Next will be to select the lexicographically smallest (according to an arbitrary ordering on the ground set) such solution F ′ , that is, < Next = < lex .

Remark that for any two solutions F and F * ∈ F max , Next(F, F * ) can be computed in polynomial time. Indeed, to compute Next(F, F * ), it suffices to compute neighbours(F ), and for each solution F ′ in neighbours(F ), compute the proximity between F ′ and F * and check whether F ′ is smaller than the current best candidate for the ordering < Next (notice that we do not need to compute Π(F ′ )).

Let f denote the size of a largest solution, and N be the complexity of the (polynomial) Function neighbours. Then the two required computations can be done in O(f ), and since | neighbours(F )| < N , the Function Next can be computed in time O(f N ).

Canonical path. Equipped with this function Next, we can now define for any solution F ∈ F max the canonical path of F as the sequence F 0 , . . . , F k = F of solutions such that for each 1

⩽ i ⩽ k, F i = Next(F i-1 , F ).
In particular, with the definition we gave for Function Next, the solutions F i on the canonical path of F get closer and closer to F as i increases. This can be restated as the following observation. Observation 6.7. Let F ∈ F max and let F 0 , . . . , F k be its canonical path. Then for any i < j ⩽ k, F j ∩ F > F i ∩ F .

If the solutions on the canonical path of F are closer and closer to F , then in particular, there cannot be too many solutions on this canonical path. Their number is bounded by the number of elements in F , plus one if the root solution F 0 had no common element with F . This can be formulated as the immediate following Corollary, ensuring that canonical paths are of polynomial size. Note that the canonical path is not necessarily the path that is followed when exploring the supergraph of solutions with Algorithm 2.4. A solution could be found in a totally different way. In fact, except for F k-1 , the other ancestors of F in the exploration arborescence may not be part of its canonical path. For instance, there is no reason for F k-1 to be generated from F k-2 in the enumeration process. However, the canonical path is uniquely determined for each solution F ̸ = F 0 . This will help us define a suitable parent-child relation over F max which does not require the system to be commutable, in order to obtain a polynomial space algorithm.

Parent relation. In the context of canonical path reconstruction, the parent of a solution F ̸ = F 0 , denoted Parent(F ), is defined as the last solution before F in its canonical path. In other words, if the canonical path of F is the sequence F 0 , . . . , F k = F , then Parent(F ) = F k-1 . With this Parent function, we can define the set Children

(F ) = {F ′ ∈ neighbours(F ) | Parent(F ′ ) = F } of children of a solution F .
Note that, in order to achieve polynomial delay, it is necessary to be able to compute the parent of any solution (except F 0 that does not have a parent) in polynomial time. With our definition, this is in fact the case: for any solution F , its parent Parent(F ) can be computed in polynomial time, provided that neighbours and the ordering Π can be computed in polynomial time. The complexity of computing the parent of a solution is detailed in Lemma 6.9. The parent relation induces a spanning subgraph of the supergraph of solutions. However, if we are not lucky enough, it can happen that this relation induces cycles. Indeed the canonical path of a solution is not necessarily the same as the canonical path of its parent. In particular, this implies, if we decide to explore the supergraph of solutions by following only the transitions authorised by the function Parent, some solutions could never be attained. Such a situation is illustrated in Figure 6.3, where the three solutions P , Q, and R are the parent of each other. They cannot be reached from F 0 by following the parent relation. Therefore, if no further assumption is made on the problem, nothing can be said about the space complexity of Proximity Search with canonical path reconstruction.

Logically, our goal is now to find out under which assumptions the function Children induces an arborescence on the solution space. Then, using a technique similar to Reverse Search, it will be possible to follow the arborescence to enumerate F max with polynomial delay and polynomial space. Prefixes. Given F ∈ F, F = E 1 , . . . , E k , we define F i the ith prefix of Π(F ) as

F i = E 1 , . . . , E i for all i ⩽ k.
For each i, we need to be able to compute the family T i of admissible sets in polynomial time. This set family T i is specific to the problem under consideration, but since it is used when computing Π, it must be computable in polynomial time. Then, we define F i + as the set of all admissible sets R ∈ T i such that

E 1 ∪ . . . ∪ E i ∪ R ∈ F.
A crucial tool that was needed to achieve polynomial delay polynomial space enumeration for strongly accessible set systems [START_REF] Conte | Listing maximal subgraphs satisfying strongly accessible properties[END_REF] is the existence of a prefix closed ordering scheme. Due to the rigidity it implies, the prefix closed property helps to make sure to follow the "right path" when exploring the supergraph of solutions. This notion can easily be translated in the context of set-ordering schemes. Definition 6.11 (Prefix closed). A set-ordering scheme is said to be prefix closed if it has the prefix property, and for any F ∈ F with Π(F ) = E 1 , . . . , E k and for any i < k there exists a preference relation

< F i over F i + such that E i+1 = min < F i {X ∈ F i + | X ⊆ F }.
Remark that the so-called preference relation associated with a prefix F i does not need to be a total ordering on F i + . In fact, the important property is the existence of a unique minimal element in

F i + for < F i .
This means in particular that with a prefix closed ordering scheme, the next element is uniquely determined by the given prefix. Being prefix closed makes the (set-)ordering scheme easier to compute in polynomial time. Moreover, the existence of a preference relation can be used to derive an ordering on all solutions.

Total ordering on the solution set. For a prefix closed set-ordering scheme Π, it is possible to define a total ordering ≺ Π over F max in the following way. Let F 1 , F 2 ∈ F max , with Π(F 1 ) = D 1 , . . . , D k , Π(F 2 ) = E 1 , . . . , E ℓ and let j ⩾ 0 be the largest index such that the jth prefix of F 1 and F 2 is the same, that is,

F j 1 = D 1 , . . . , D j = E 1 , . . . , E j = F j 2 .
Let us denote by L the largest common prefix of F 1 and F 2 , that is, L := F j 1 = F j 2 (note that the set L is not necessarily equal to F 1 ∩ F 2 , the largest prefix of F 2 contained in F 1 , since its elements can appear in any order in F 1 ). Then

F 1 ≺ Π F 2 if D j+1 < L E j+1 .
From now on, we will assume that the problem under consideration admits a prefix closed ordering scheme. Therefore, our problem becomes the enumeration of all maximal elements of a set system F, with a suitable, polynomial-time computable neighbouring function neighbours and a prefix closed ordering scheme Π. We consider the functions Parent and Children as defined previously.

We will see in what follows that being prefix closed is indeed the right notion to achieve polynomial space with canonical path reconstruction.

First, let us begin with a series of two technical lemmas. In general, nothing can be said about the canonical paths of two different solutions. However, if a solution F shares a common prefix with another solution on its canonical path, then it is possible to prove that they also share their canonical paths. It is the purpose of the following lemma. Lemma 6.12. Let F ∈ F max with Π(F ) = E 1 , . . . , E ℓ ; let F 0 , . . . , F k be its canonical path and let i

⩽ k. If E 1 , . . . , E F i ∩ F is a prefix of Π(F i ), then the canonical path of F i is F 0 , . . . , F i .
Proof. Since F i ∈ F max , in particular it has a canonical path. Consider T 0 , . . . , T h the canonical path of F i . First, by definition we have T 0 = F 0 . Now, let j < i be such that T 0 , . . . , T j = F 0 , . . . , F j . We will prove that F j+1 = T j+1 , implying by induction the equality T 0 , . . . , T i = F 0 , . . . , F i . By Observation 6.7, since j < i we know that F j ∩ F < F i ∩ F , so there exists

r < F i ∩ F such that E 1 ∪ . . . ∪ E r ⊆ F j and E r+1 \ F j ̸ = ∅. By hypothesis, we know that E 1 , . . . , E r+1 is a prefix of Π(F i ). Hence it follows r = F j ∩ F = F j ∩ F i < F i ∩ F .
Recall that Function Next is a deterministic function choosing among the neighbours of the current solution, one that increases the proximity to the target solution. In other words, Next puts a preference order < Next on the neighbours, and selects the minimum according to < Next .

Using this notation, we can then write

F j+1 = Next(F j , F ) = min < Next {F ′ ∈ neighbours(F j ) | E 1 ∪ . . . ∪ E r+1 } ⊆ F ′ } by definition of Function Next = min < Next {F ′ ∈ neighbours(T j ) | E 1 ∪ . . . ∪ E r+1 ⊆ F ′ } = Next(T j , F i ) = T j+1
since T j = F j and since E 1 , . . . , E r+1 is a prefix of F i .

CANONICAL PATH RECONSTRUCTION | 109

Therefore, F 0 = T 0 and for any j < i such that F j = T j , we have F j+1 = T j+1 . This implies in turn T 1 , . . . , T i = F 1 , . . . , F i and the lemma is proven.

The next technical lemma links the proximity between two solutions to the total order that was defined according to Π on the set of all solutions. This order will be crucial in the sequel, namely when proving that the function Children induces an acyclic relation on the solution space. Lemma 6.13. Let F 1 , F 2 ∈ F with Π(F 1 ) = D 1 , . . . , D ℓ and Π(F 2 ) = E 1 , . . . , E k . Assume furthermore that there exists j ⩽ ℓ such that for any i ⩽ j, D i ⊆ F 2 . Then one of the two possibilities holds:

1. F 2 ≺ Π F 1 ; 2. D i = E i for all i ⩽ j.
Proof. Suppose that there exists i ⩽ j such that D i ̸ = E i (otherwise the second case holds), and let us consider the smallest such i.

Then F i-1 1 = F i-1 2 . Denote by L this common prefix, that is, L := F i-1 1 = F i-1 2 . Moreover, we know that D i ⊆ F 2 and D i ∈ L + . Since Π is prefix closed, it implies E i < L D i , hence F 2 ≺ Π F 1 .
With the last two lemmas, we are now ready to prove the Function Children induces an arborescence on the solution set F max , since we assumed that the ordering scheme Π is prefix closed. Theorem 6.14. If the ordering scheme Π is prefix closed, then Children defines a spanning arborescence on F max rooted at F 0 .

Proof. The supergraph of solutions defined by Function Children is the directed graph on F max with arc set {(F i , F j ) | F j ∈ Children(F i )}. We will show that this supergraph of solutions is an arborescence.

Since each solution F ∈ F max \ {F 0 } has only one in-neighbour Parent(F ), it is sufficient to show that for all F ∈ F max there exists a path from F 0 to F . Let us denote by R(F 0 ) ⊆ F max the set of all sets F ∈ F max for which there exists a path from F 0 to F .

Assume for contradiction that R(F 0 ) ̸ = F max and let

F := min ≺ Π (F max \ R(F 0 )). Let Π(F ) = E 1 , . . . , E ℓ and let F 0 , . . . , F k be the canonical path of F . Now, consider the smallest index i * ⩽ k such that F i * / ∈ R(F 0 ). If i * = k then F k-1 ∈ R(F 0 ) and since F k-1 = Parent(F ), F would belong to Children(F k-1
) and then F would belong to R(F 0 ). Hence, assume i * < k.

Let j := F i * ∩ F . By minimality of F with respect to ≺ Π , we have F ≺ Π F i * . Therefore, F i * ≺ Π F does not hold (since F i * ̸ = F ). Hence by Lemma 6.13, since E 1 ∪ . . . ∪ E j ⊆ F i * by definition of the proximity, the jth prefix of Π(F i * ) is E 1 , . . . , E j . Now, by Lemma 6.12, the canonical path of F i * is F 0 , . . . , F i * , thus F i * has F i * -1 as its parent. By minimality of i * , we know that F i * -1 ∈ R(F 0 ) and since in addition

F i * ∈ Children(F i * -1 ), we deduce F * i ∈ R(F 0 ), leading to a contradiction.
It is somehow counter-intuitive to observe that the canonical path of a solution is not necessarily part of the final arborescence rooted at F 0 . This canonical path is only computed to find the last solution in the path before F to define it as the parent of F . What we proved is that while the so-defined parent-child relation does not exactly follow the canonical paths, it still forms a spanning arborescence on the solution set rooted at F 0 . Now that we have an arborescence on the solution set, the idea is to explore it in a depth-first manner. The most suited algorithm is undoubtedly Reverse Search, explicitly designed for this purpose.

Observe that the naive implementation of Algorithm 2.2 (see Section 2.2.3) may use exponential space, since the height of the recursion tree might be exponential. Indeed,the recursion tree corresponds to the arborescence defined by the parent-child relation and we are not able to guarantee that its height is polynomial. However, since the functions Parent and Children are computable in polynomial time, we do not need to store the state of each recursion call. The classical trick introduced by Tsukiyama et al. in 1977 [START_REF] Tsukiyama | A new algorithm for generating all the maximal independent sets[END_REF] and formalised by Avis & Fukuda in 1996 [START_REF] Avis | Reverse search for enumeration[END_REF] as part of the Reverse Search algorithm is to use the function Parent to perform the backtrack operation on the fly. Indeed, this function is able to navigate backward in the tree, removing the need of keeping in memory all recursion calls. Thus, the algorithm only needs to keep in memory the current solution, and not the whole set of all the solutions that have already been found.

Therefore, Theorem 6.14 implies that, when the set-ordering scheme is both proximity searchable and prefix closed, it is possible to use the canonical path reconstruction method to enumerate F max efficiently. This rephrases as the following theorem. Theorem 6.15. Let F be a set system with a polynomially computable function neighbours and a prefix closed ordering scheme. If the enumeration of all maximal elements of F is proximity searchable, then F max can be enumerated with polynomial delay and polynomial space.

Applications of canonical path reconstruction

In the present section, we take interest on some problems for which canonical path reconstruction provides an efficient, polynomial space algorithm. This is for example the case for minimal chordal completions, whose ordering scheme is naturally prefix closed. However, it can be successfully applied to other problems. For example, a polynomial delay algorithm was known for the enumeration of maximal induced chordal subgraphs 6.3 APPLICATIONS OF CANONICAL PATH RECONSTRUCTION | 111 [START_REF] Conte | Proximity search for maximal subgraph enumeration[END_REF], but this algorithm runs with exponential space. We exhibit here a prefix closed ordering scheme for this problem, allowing us to use canonical path reconstruction, therefore reducing the space complexity of the maximal induced chordal subgraphs enumeration problem.

Minimal chordal completions in polynomial space

In Chapter 5, we proved that minimal chordal completions are proximity searchable with the canonical ordering Can (see page 93), thus there exists a polynomial delay algorithm for their enumeration. We would like to make the enumeration process work in polynomial space, since this could lead to an algorithm that is more usable in practice. To achieve this space complexity, a first idea would be to use the Proximity Search technique developed for commutable set systems [START_REF] Conte | Listing maximal subgraphs satisfying strongly accessible properties[END_REF], when the ordering is prefix closed.

As stated earlier, chordal completions form a strongly accessible set system since they are sandwich-monotone, and so are their complements. However, the set of chordal completions is not a commutable set system, and neither is the set of their complements. Take for example the completion H of a P 4 containing an edge e joining the two endpoints, and the two chords a and b, as shown in Figure 6 Therefore, we cannot try to enumerate the minimal chordal completions of a graph in polynomial space with this technique. Instead, we will prove the problem satisfies the conditions of Theorem 6.15. With canonical path reconstruction, it will be possible to define a suitable parent-child relation in order to organise the space of solutions in an arborescence. This way, the enumeration of minimal chordal completions of a graph will need only polynomial space.

Neighbouring function and ordering scheme. For this enumeration problem, we use the same neighbouring function (based on the Flip operation) and ordering scheme (namely, Can) as in Section 5.3. It is stated in Theorem 5.20 that the minimal chordal completions enumeration problem, with the corresponding neighbouring function and the ordering scheme Can, is proximity searchable. Maximum Cardinality Search (MCS for short), and presented here as Algorithm 6.1, produces a reverse perfect elimination ordering whenever G ′ is chordal. Algorithm 6.1: Maximum Cardinality Search (MCS) [START_REF] Tarjan | Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs[END_REF] input : To illustrate how Algorithm 6.1 works, let us have a look on the example of Figure 6.6. The graph is chordal and has vertices a, b, c, d, e, and f . At first, the algorithm selects the vertex of smallest id, a. Then, weights are put on the neighbours of a, symbolised by dots on the picture. At each step, the algorithm selects the vertex of largest weight and increases the weights of its neighbours, until all vertices have been eliminated. In this example, the graph is chordal and the ordering returned by Algorithm 6.1 is abedcf , which is indeed the reverse of a PEO.

A graph G = (V, E) output : A reverse PEO of G if G is chordal 1 Begin with all vertices unnumbered. 2 foreach vertex v ∈ V do
Since the ordering scheme produced by Maximum Cardinality Search, called here MCS-ordering scheme, is the reverse of a perfect elimination ordering on chordal graphs, it follows [START_REF] Conte | Proximity search for maximal subgraph enumeration[END_REF] that our problem is proximity searchable. This rephrases as the following lemma. Lemma 6.18. The problem of enumerating maximal induced chordal subgraphs with the previously defined neighbouring function and the MCS-ordering scheme is proximity searchable.

In order to apply Theorem 6.15, we need our ordering scheme to be prefix closed. This will allow us to use canonical path reconstruction with the guarantee that every solution is outputted exactly once, therefore using only polynomial space. That is what we will do when proving the following lemma. Lemma 6.19. The MCS-ordering scheme is prefix closed. Proof. Let G be a graph. A maximal chordal subgraph S 0 of G can be found by applying a greedy algorithm adding vertices one by one while the resulting induced subgraph is chordal.

First, the MCS-ordering scheme has the prefix property. Indeed, the property of being chordal is hereditary, therefore any prefix of the canonical ordering of a solution is an induced subgraph of this solution, that is, a chordal graph.

Then, since the property of being chordal is hereditary, in particular it is also strongly accessible, and the set of candidates X + for any partial solution X is well-defined and non-empty unless X is a maximal induced chordal subgraph of G. Let us consider a (non-maximal) set of vertices X which induces a chordal subgraph of G. By definition, the elements of X + are the vertices x ∈ V (G) \ X such that G[X ∪ {x}] is chordal.

We give an ordering < X of X + in the following manner. We say that x < X y if either |N (x) ∩ X| > |N (y) ∩ X| or N (x) ∩ X = N (y) ∩ X and x < y. This way, vertices of large degree in X are ordered first and the ties are broken according to the arbitrary ordering of the vertices. In other words, the vertices of X + are ordered by considering the lexicographic order of the tuple (n -|N (x) ∩ X|, x), with x ∈ X + .

Equipped with this ordering of X + for any subset of vertices inducing a chordal subgraph, it is straightforward to see that the MCS-ordering scheme satisfies Definition 6.11.

We are now able to use Proximity Search on the set of maximal induced chordal subgraphs of G, and ensure that the ordering we consider is prefix closed. Therefore our setting satisfies the requirements for Theorem 6.15. Hence, for each solution S different from the root solution S 0 , it is possible to compute in polynomial time the canonical path of S. The parent Parent(S) of S is then defined as the last solution before S on its canonical path, as in Section 6.2. This implies the following result. Theorem 6.20. Maximal induced chordal subgraphs can be enumerated with polynomial delay in polynomial space.

Maximal connected induced chordal subgraphs

In fact, the MCS-ordering scheme is also prefix closed when considering maximal connected induced chordal subgraphs. It has been proved by Conte et al. that -with the appropriate neighbouring function they provide -the problem of enumerating maximal connected induced chordal subgraphs with any ordering scheme corresponding to the reverse of a perfect elimination ordering is proximity searchable. Moreover, by definition the MCS-ordering scheme also has the prefix property for connected induced chordal subgraphs. Therefore, the proof of Lemma 6.19 also holds in the case of connected induced chordal subgraphs. As a consequence, the same result holds for maximal connected induced chordal subgraphs. Theorem 6.21. Maximal connected induced chordal subgraphs can be enumerated with polynomial delay in polynomial space.

Conclusion

T he ultimate goal of a thesis on the subject would be to find a general technique, applicable to the most possible graph classes, for the enumeration of minimal completions, minimal deletions, maximal induced subgraphs that belong to the considered class. If such a general technique does not exist for all (hereditary) classes of graphs, then a natural question arises: which graph classes admit an efficient (e.g. polynomial delay) enumeration algorithm for minimal completions (resp. deletions) or maximal induced subgraphs, and which ones do not?

Neither of these questions is an easy task. In this thesis, advances have been made concerning the theoretical knowledge of the minimal completions, minimal deletions, and maximal induced subgraphs enumeration problems.

Many efficient techniques already exist for enumeration purposes, and they are often well suited to the problems we considered here, in particular to maximal induced subgraphs enumeration. For some graph classes, such as split graphs, cographs, and threshold graphs, the existence of a polynomial delay algorithm enumerating maximal induced subgraphs was still unknown. We showed that these three problems could be solved efficiently using existing techniques, by relying on the structural characterisations of graphs in those three classes.

For split graphs, the input restricted problem introduced by Cohen, Kimelfeld & Sagiv [START_REF] Cohen | Generating all maximal induced subgraphs for hereditary and connected-hereditary graph properties[END_REF] proved its efficiency regarding both time and space. For the enumeration of maximal induced sub-cographs and threshold subgraphs, we managed to apply the more recent Proximity Search technique proposed by Conte & Uno [START_REF] Conte | New polynomial delay bounds for maximal subgraph enumeration by proximity search[END_REF], and exhibited non-trivial polynomial delay, exponential space algorithms for these two problems.

When it comes to minimal completions and deletions, it seems even harder in general to find a suitable way to apply an existing technique. However, in certain cases, the properties satisfied by the graphs in the considered class allow us to link the minimal completions with other structures for which the complexity of enumeration is known. It is the case with minimal split completions: due to the many properties satisfied by split graphs, it is in fact equivalent to enumerate the (inclusion-wise) maximal stable sets of a modified graph. Fortunately, the last problem has been known to be solvable with polynomial delay in polynomial space for a long time [START_REF] Tsukiyama | A new algorithm for generating all the maximal independent sets[END_REF]. An efficient algorithm for the enumeration of minimal split completions (and deletions since the class is self-complementary) follows immediately. Nevertheless, there is obviously no reason for such a correspondence to be found for any class of graphs.

In general, the assumptions for using an existing enumeration technique that yields good complexity results (Reverse Search, input restricted problem) are quite restrictive. Despite Flashlight Search to achieve good complexity results very simply, we showed in Chapter 4 that it cannot be used as a general technique for the enumeration of maximal induced subgraphs in a prescribed class P. Indeed, the associated extension problem is NP-hard when no further assumption is made on P.

Therefore, other options have to be considered: newer, less known techniques seem promising. We have seen in particular in Chapter 5 that Proximity Search turns up useful when enumerating maximal induced sub-cographs and threshold subgraphs. In fact, Proximity Search can also be used for minimal deletions enumeration problems. For example, it allows us to enumerate all minimal threshold deletions (and completions) with polynomial delay, whereas the class of threshold graphs is not monotone -the counterpart of hereditary for edge problems.

Although threshold graphs are not monotone, they still possess an interesting property: they are sandwich-monotone. This property makes the computation of a minimal deletion and the completion process into a minimal deletion easier when applying Proximity Search. However, it is quite a strong requirement, and it is not satisfied by all graph classes: for example cographs, trivially perfect graphs, P 3 -free graphs, are not sandwich-monotone.

Polynomial sandwich algorithms [START_REF] Charles Golumbic | Graph sandwich problems[END_REF] have been briefly mentioned in this thesis: when they exist -it is the case for cographs, trivially perfect graphs, and P 3 -free graphs [START_REF] Charles Golumbic | Graph sandwich problems[END_REF][10, v1] -, a polynomial-time computable completion function can be found even if the class is not sandwich-monotone. This could be useful to apply Proximity Search to many new problems. We leave as an open question the minimal deletions enumeration problems into the three aforementioned classes. Alongside that, further investigation on sandwich problems appears to be another interesting path to follow for future research.

Question 4. Can minimal deletions of a graph into cographs, trivially perfect graphs, or P 3 -free graphs be enumerated with polynomial delay (with or without the help of Proximity Search)?

Finally, the question of how efficiently it is possible to enumerate the minimal chordal completions of a graph has been a hot topic in research for at least the last decade [START_REF] Carmeli | Efficiently enumerating minimal triangulations[END_REF][START_REF] Boros | Enumeration in data management (dagstuhl seminar 19211)[END_REF]. The best algorithm up to date was proposed in 2017 and has incremental delay. We were interested in this problem and we proved Proximity Search can also be used to enumerate the minimal chordal completions with polynomial delay. Our graphs. To the best of our knowledge, no polynomial delay algorithm for maximal induced subgraphs is known in any of those classes.

In fact, all the Proximity Search-based techniques currently used rely heavily on solution orderings. We proved that it is possible to relax the notion of ordering scheme, introducing set-ordering schemes. With set-ordering schemes, solutions are not seen as ordered subsets of the ground set any more, but rather as ordered partitions. This extension of the "usual" Proximity Search technique could help to find some new problems to which Proximity Search can be applied, implying the existence of a polynomial delay algorithm. If moreover the problems satisfy the requirements for canonical path reconstruction, then polynomial space will be achieved as well.

General set proximity makes it natural to think about some minimal deletions problems as derived from the corresponding maximal induced subgraphs problems. This was for example the case when Proximity Search was applied to enumerate the minimal threshold deletions of a graph. Naturally, the following question arises.

Question 5. In which cases can an algorithm enumerating the minimal deletions be derived from the maximal induced subgraphs enumeration with the help of general set proximity?

Minimal completions and deletions are not the only interesting objects that can be enumerated in graphs. Potential Maximal Cliques of a graph were introduced in the early 2000s [START_REF] Bouchitté | Listing all potential maximal cliques of a graph[END_REF][START_REF] Todinca | Aspects algorithmiques des triangulations minimales des graphes[END_REF] as the sets of vertices inducing a clique in some minimal chordal completion. Due to their links with chordal completions and minimal separators, they are a powerful tool for the computation of treewidth and minimum fill-in. Currently, the best algorithm known for their enumeration [START_REF] Bouchitté | Listing all potential maximal cliques of a graph[END_REF] is quadratic in the number of solutions and uses exponential space. For applications, it would be interesting to be able to generate them more efficiently. This brings us to a problem that has been open for twenty years.

Question 6. Is it possible to generate all Potential Maximal Cliques of a given graph with polynomial delay, or in polynomial space?

For some graphs, connected greedy colourings use at most χ(G) colours (that is, the minimum feasible number of colours). However, it is not always the case: sometimes there does not exist any connected greedy colouring using less than χ(G) + 1 colours. A graph G with this last property is called ugly. The question we worked on was the following: for a given graph class, does it contain ugly graphs? We partially answered it for perfect graphs and K 4 -minor-free graphs, proving that no perfect graph is ugly, and no K 4 -minor-free graph is ugly.

These results appear in the preprint [START_REF] Beaudou | Connected greedy colourings of perfect graphs and other classes: the good, the bad and the ugly[END_REF] • Connected greedy colourings of perfect graphs and other classes: the good, the bad and the ugly, with Laurent Beaudou, Oscar Defrain, Florent Foucaud, Aurélie Lagoutte, Vincent Limouzy and Lucas Pastor, on ArXiv arXiv:2110.14003, 2021. Submitted for publication.

Locating-dominating sets in oriented graphs

The other project was realised with a team constituted during the annual French graph meeting JGA 2020. Given an oriented graph D = (V, A) on n vertices, a dominating set is a set S of vertices of D such that any vertex in V \ S has at least one in-neighbour in S. A set L is locating if for any two vertices u, v in V \ L, the in-neighbourhoods of u and v are different sets -permitting to differentiate u and v. We were interested in knowing the maximum size of a minimum set that is both locating and dominating.

It was already known [START_REF] Foucaud | Domination and location in twin-free digraphs[END_REF] that for tournaments, that is, orientations of complete graphs, such a set can contain at most ⌈n/2⌉ vertices. We extended this result to a larger class of oriented graphs. An oriented graph is a local tournament if the in-and out-neighbourhoods of any vertex induce tournaments. It is of course the case for tournaments, but this class contains way more oriented graphs; for example, oriented cycles are local tournaments.

We proved that any connected local tournament on n vertices has a locatingdominating set of size at most ⌈n/2⌉.

We also proved a conjecture of Foucaud, Heydarshahi & Parreau [START_REF] Foucaud | Domination and location in twin-free digraphs[END_REF] in a special case: when the oriented graph has no twins nor quasi-twins -for oriented graphs, two vertices sharing the same open (resp. closed) in-neighbourhood -, and has a vertex from which any other can be reached. In this case, we proved that the oriented graph has a locating-dominating set of size at most 2n 3 , and that this bound is tight, meeting the value that was previously conjectured.

These results can be found in the article [START_REF] Bellitto | Locatingdominating sets in local tournaments[END_REF] •

Summary

This thesis is about graph theory and more specifically enumeration algorithms for subgraphs or supergraphs. The problem we consider is the following: given a graph G and a graph property P, can we find an efficient algorithm generating exactly once all the inclusion-wise maximal (induced or not) subgraphs of G that satisfy the property P? We are interested as well in inclusion-wise minimal supergraphs of G -called minimal completions of G -verifying P. Efficient algorithms, running with polynomial delay in polynomial space, are obtained for some of these problems when P describes the classes of split graphs, cographs, threshold graphs and chordal graphs.

The thesis is organised as follows. First, the principal existing enumeration techniques are presented. Then, we are interested in the split property, for which we give a polynomial delay polynomial space algorithm enumerating minimal completions and deletions (maximal non-induced subgraphs). We are then interested in the well known Flashlight Search technique and show that it cannot be used to enumerate efficiently the maximal subgraphs in any class. After that, the recent Proximity Search technique is applied to the enumeration of maximal induced sub-cographs, maximal induced threshold subgraphs and minimal deletions into threshold graphs. This way, we obtain polynomial delay exponential space algorithms. This technique is also successfully applied to the enumeration of minimal completions into chordal graphs, for which the existence of a polynomial delay algorithm was an open problem. Finally, a generalisation of Proximity Search is proposed, and a new technique based on Proximity Search for polynomial delay polynomial space algorithms is introduced. We apply this technique to most of the problems solved in this thesis via Proximity Search, therefore reducing their space complexity.

Résumé

Cette thèse porte sur la théorie des graphes et plus particulièrement les algorithmes d'énumération de sous-graphes ou sur-graphes. Le problème auquel on s'intéresse est le suivant : étant donné un graphe quelconque G et une propriété de graphes P, peut-on trouver un algorithme efficace qui génère une et une seule fois tous les sousgraphes maximaux pour l'inclusion (induits ou non) de G qui vérifient la propriété P ? De même, on s'intéresse aussi aux sur-graphes de G minimaux pour l'inclusion -appelés complétions minimales de G -qui vérifient P. Des algorithmes efficaces, à délai polynomial en espace polynomial, sont obtenus pour certains de ces problèmes lorsque P décrit la classe des graphes split, des cographes, des graphes threshold et des graphes cordaux.

La thèse se décompose de la manière suivante. D'abord, les principaux algorithmes d'énumération existants sont présentés. Puis on s'intéresse à la propriété split, pour laquelle on donne un algorithme à délai polynomial en espace polynomial pour l'énumération des complétions minimales et délétions minimales (sous-graphes maximaux non induits). On s'intéresse ensuite à une technique d'énumération existante appelée Flashlight Search et on montre qu'elle ne peut être utilisée pour énumérer efficacement les sous-graphes maximaux dans n'importe quelle classe. Après cela, la récente technique de Proximity Search est appliquée à l'énumération des sous-graphes maximaux induits dans la classe des cographes, des sous-graphes threshold maximaux induits et des délétions minimales en graphe threshold. Nous obtenons ainsi des algorithmes à délai polynomial en espace exponentiel. Cette technique est aussi appliquée avec succès à l'énumération des complétions minimales en graphe cordal, pour lesquelles l'existence d'un algorithme à délai polynomial était un problème ouvert. Enfin, une généralisation de la technique de Proximity Search est proposée, et une nouvelle technique fondée sur le Proximity Search pour des algorithmes à délai polynomial en espace polynomial est introduite. Nous appliquons cette technique à la plupart des problèmes résolus dans cette thèse via Proximity Search, ce qui réduit leur complexité en espace.

Figure 1 . 1 :

 11 The two vertices x and y have the same neighbours: they are (true or false) twins.

Figure 1 . 2 :

 12 Figure 1.2: A chordal graph with its simplicial vertices identified. A corresponding clique tree is shown in the middle. The obstructions are long cycles (on the right).

C 4 2K 2 C 5 Figure 1 . 3 :

 2513 Figure 1.3: A split graph with its split partition. The coloured vertex can be placed either in the clique or in the stable set. The obstructions are shown on the right.

Figure 1 . 4 :

 14 Figure 1.4: A cograph (on the left) with its associated cotree. In this graph, the vertices 1 and 2 are true twins, the vertices 4 and 5 are false twins. The obstruction P 4 can be seen on the right.

Figure 1 . 5 :

 15 Figure 1.5: A threshold graph whose threshold construction ordering is 123456. White vertices were added as isolated, black vertices were added as universal. The three obstructions are presented on the right.

Figure 1 . 6 :

 16 Figure 1.6: Diagram showing the inclusions between all the mentioned graph classes. An arrow shows an inclusion (directed towards the smallest class).

Figure 1 . 7 :

 17 Figure 1.7: A graph with a split completion, a split deletion, and an induced split subgraph.

Figure 2 Figure 2 . 1 :

 221 Figure 2.1: Execution time of an output-polynomial algorithm. A vertical line indicates the output of a solution.

Figure 2 . 2 :

 22 Figure 2.2: Execution time of an incremental-polynomial algorithm. A vertical line indicates the output of a solution.

Figure 2 . 3 :

 23 Figure 2.3: Execution time of a polynomial delay algorithm. A vertical line indicates the output of a solution.

Figure 2 . 4 :

 24 Figure 2.4: Inclusions between the three complexity classes output-polynomial, incremental-polynomial, and polynomial delay.

{e 1 , e 2 } {e 2 , e 3 } {e 2 } {e 3 3 Figure 2 . 5 :

 122323325 Figure 2.5: Illustration of the tree explored by Flashlight Search.

Algorithm 2 . 1 : 4 S 7 T := ∅; 8 foreach I ∈ S do 9 if 10 T 11 else 12 foreach 13 if J is maximal in I i then 14 T

 2147891011121314 Maximal independent set generation input : An independent set system I on E (given by a membership oracle in time c) output : All maximal elements of I 1 S := ∅; /* the set of all partial solutions */; 2 i = 1; 3 while i ⩽ n do :=extend (S, e i , I); 5 increment i; 6 return S; Function extend (S, e i , I): I ∪ {e i } ∈ I then := T ∪ {I ∪ {e i }}; /* I ∪ {e i } is maximal in I i */; J ∈ I maximal within I ∪ {e i } do := T ∪ {J}; /* do not add if J ∈ T already */;

Figure 2 . 6 :

 26 Figure 2.6: An example of the arborescence induced by the function Parent on the solution space. Reverse Search consists in enumerating the solutions by following this arborescence.

Algorithm 2 . 2 : 3 Output 6 Output

 2236 The general Reverse Search algorithm input : An enumeration problem, together with a polynomially computable Parent function output : All solutions of the problem 1 S 0 := a particular "root" solution; 2 Call enum (S 0 ); Function enum (S): S if recursion depth is even; 4 foreach S ′ ∈ Children (S) do 5 Call enum (S ′ ); S if recursion depth is odd;

Algorithm 2 . 3 :

 23 Enumeration of the maximal induced P-subgraphs via the Input Restricted Problem input : A graph G output : All maximal induced P-subgraphs of G 1 H := any maximal P-subgraph of G; 2 S := {H}; /* the set of solutions already found */; 3 Output H; 4 Call recursiveGen (G, H, S);

Algorithm 2 . 4 : 4 S

 244 The general Proximity Search algorithm input : A ground set E, a property P, with a polynomially computable function neighbours output : All maximal subsets of E satisfying P 1 S := ∅; 2 S := an arbitrary maximal subset of E satisfying P; 3 Run enum(S, S); Function enum (S, S): := S ∪ {S}; 5

Figure 3 . 1 :

 31 Figure 3.1:The graph with the black edges is not split, but adding the three red (curved) edges produces a split completion of it. The two circled vertices form an inclusion-wise maximal stable set.

Figure 3 . 2 :

 32 Figure 3.2: Removing the edge {3, 5} from the split completion of Figure 3.1 does not break the split property.

Figure 3 . 3 :

 33 Figure 3.3: In this graph, the vertices 2 and 5 are redundant but the completion induced by the stable set {2, 5} (dashed edges) is minimal.

  have the inclusions G ⊆ H -A ⊆ H. By Lemma 3.4, |S| ⩽ |S ∪ I| ⩽ |S| + 1. Because S and I are both maximal stable sets of G we cannot have I ⊆ S, so necessarily |S ∪ I| = |S| + 1. Then, |S| + 1 = |S ∪ I| = |S| + |I \ S|. Therefore |I \ S| = 1, and we also have |S \ I| > 0 because S is maximal. Consequently there exist w ∈ V and U ⊆ V such that I = T ∪ {w} and S = T ∪ U , where U and T = S ∩ I are disjoint stable sets of G.

  Figure 3.4 illustrates this situation.

Figure 3 . 4 :

 34 Figure 3.4: A partition of V for the split completion H and another split partition for H -A. The vertex w is universal to C. Edges inside S ∩ C belong to H but not to H -A.

Figure 3 Figure 3 . 5 :

 335 Figure 3.5: There exists z such that xz ∈ E and yz is a fill edge in H.

Figure 3 . 6 :

 36 Figure 3.6: The two stable sets represented by circled vertices give the same minimal split completion.

3. 1 MINIMAL SPLIT COMPLETIONS | 57 Procedure 3 . 1 : 3 foreachTheorem 3 . 10 .

 157313310 Construction of the auxiliary graph input : a graph G /* Mark redundant and twin vertices */; 1 Begin with all vertices unmarked; 2 foreach unmarked x ∈ V do unmarked y ∈ N (x) do 4 if N [x] ⊆ N [y] then 5 mark y; /* Remove unnecessary vertices */; 6 foreach marked x ∈ V do 7 if V \ N G [x] is a stable set then 8 remove x; Minimal split completions (resp. deletions) of a graph can be enumerated with polynomial delay in polynomial space.

Figure 3 . 7 :

 37 Figure 3.7: A graph built from n/3 disjoint triangles.

Figure 3 . 8 :

 38 Figure 3.8: The maximal induced split subgraph on the right was obtained from the maximal clique and stable set identified in the graph on the left.

Figure 3 . 9 :Lemma 3 . 15 .

 39315 Figure3.9: A graph that is not split but can be turned into a split graph with split partition K + S by removing the vertex v.

Figure 4 . 2 :

 42 Figure 4.2: An obstruction J P and its connected components J 1 and J 2 . The two subgraphs J 0 and J ′ 1 are highlighted. The reduction is with the problem of finding a maximal stable set avoiding a set B ⊆ V (G), whose NP-completeness has been proven by Boros et al. [7, Proposition 2].

Figure 4 . 3 :

 43 Figure 4.3: G transforms into G ′ . The set B consists here in the only square vertex, and the set A in the smaller vertices. The circled vertices form a maximal stable set of G not intersecting B.

Figure 4 . 4 :

 44 Figure 4.4: The graph G obtained from a 3-SAT formula.

Figure 4 . 5 :

 45 Figure 4.5: Transformation of an instance of Vertex Cover extension into an instance of the triangle-free edge extension problem. Circled vertices are vertices in S, A is the set of edges of G (green), and B is the set of edges between c and vertices of S (red).

Figure 4 . 6 .Figure 4 . 6 :

 4646 Figure 4.6: Transformation for k = 5.

Figure 5 . 1 :

 51 Figure 5.1: The graph H consisting of k disjoint edges x 1 y 1 , . . . , x k y k is a cograph, and H + v has an exponential number of maximal induced sub-cographs.

Figure 5 . 2 :

 52 Figure 5.2: An example of a cograph with its cotree; the canonical ordering is 1, 4, 3, 2, 5.

xyFigure 5 . 3 :

 53 Figure 5.3: Illustration of the neighbouring function for maximal induced sub-cographs. The circled vertices belong to N G (x)△N S (y).

Figure 5 . 4 :Definition 5 . 5 (

 5455 The canonical ordering of this threshold graph is 1, 4, 2, 5, 3, 6. Now, let us define a neighbouring function able to produce new solutions from the already generated ones. Neighbouring function for maximal induced threshold subgraphs).

Figure 5 . 5 :

 55 Figure 5.5: Illustration of the neighbouring function for maximal induced threshold subgraphs.

  is. Moreover, by definition of the canonical ordering, we know that v k+1 is either isolated or universal in G[{v 1 , . . . , v k+1 }].

  , and define neighbours(S) := { S x | x ∈ V }. Each solution has a linear number of neighbours.

Figure 5 . 6 :

 56 Figure 5.6: Illustration of the neighbouring function for minimal threshold deletions.

Figure 5 . 7 :

 57 Figure 5.7: How to use the Function Del to compute a minimal chordal completion of a C 6 . The chordal completion {bf, cf, df } is minimal.

Figure 5 . 8 :

 58 Figure 5.8: The flip operation on e = {x, y}. The common neighbourhood of x and y is turned into a clique.

Figure 5

 5 Figure 5.9: There is a z -t path P in H ′ , disjoint from e ′ . On the right, the vertices q, s, r and x belong to a chordless cycle of H. The edge xs does not belong to the graph.

Lemma 5 . 18 .

 518 Let F be a chordal completion of a graph G. If F ∈ F min , and e ∈ F , then Flip(F, e) ∈ F. That is to say, Flip(F, e) is a chordal completion of G.

GFigure 6 . 1 :

 61 Figure 6.1:The set of threshold graphs is not commutable. In this illustration, G is threshold, G ∪ {a} and G ∪ {b} are also threshold, but G ∪ {a, b} is not (while G ∪ {a, b, e} is).

Figure 6 . 2 :

 62 Figure 6.2: Summary of the inclusions between the different properties of set systems.

Corollary 6 . 8 .

 68 If F ∈ F max , then its canonical path is of length at most |F | + 1.

Lemma 6 . 9 .Corollary 6 . 10 .

 69610 The function Parent can be computed in time O(p + f 2 N ) where f is a maximum size of a solution in F max , N is the complexity of function neighbours and p is the time needed to compute Π. Proof. To compute Parent(F ), we first need to compute Π(F ) and then to compute the canonical path of F . By Corollary 6.8, the path is of length at most |F |, so we only need to call |F | times the function Next. As mentioned previously, this last function can be computed in time O(f N ), whence the result. For any solution F , since the computation of Children(F ) is done by computing first the set neighbours(F ) and then filtering it according to the function Parent, we obtain the following complexity for the function Children. The function Children can be computed in time O(p + f 2 N 2 ) where f is a maximum size of a solution in F max , N is the complexity of function neighbours and p is the time needed to compute Π.

Figure 6 . 3 :

 63 Figure 6.3: The parent relation induces a cycle in the supergraph of solutions. Three solutions have disjoint canonical paths but they are the parent of each other. In this situation, the solutions P , Q, and R cannot be obtained by following the parent relation starting from F 0 .

3 5 Find 6 v i := u; 7 foreach

 567 weight(v) := 0; 4 for i = 1 to n do the unnumbered vertex u of maximum weight (break ties with smallest vertex id); unnumbered v ∈ N G (v i ) do 8 weight(v) := weight(v) + 1; 9 return v 1 , . . . , v n ;

Figure 6 . 6 :

 66 Figure 6.6: Example of an execution of Algorithm 6.1 on a chordal graph. The weights on the vertices are symbolised by dots.

  .4. The P 4 given by H \ {a, b, e} is chordal. Plus, both graphs H \ {a} and H \ {b} are chordal, whereas H \ {a, b} is not.

	b	a	b	a
	H e Figure 6.4: Chordal completions of an arbitrary graph (here a P 4 ) are not a commutable H \ {a} H \ {b} H \ {a, b} e e e H \ {a, b, e} set system.

  Locating-dominating sets in local tournaments, with Thomas Bellitto, Benjamin Lévêque and Aline Parreau, Discrete Applied Mathematics, 337:14-24, 2023.

	132 | INDEX
	incremental-polynomial, 30	retaliation-free paths, 44
	independent set system, 33	Reverse Search, 37
	induced P-subgraph, 24
	induced sub-cograph, 22	sandwich algorithm, 71
	induced subgraph, 17	sandwich problem, 70
	input, 27	sandwich-monotone, 18
	Input Restricted Problem, 40	self-complementary, 17
	input-sensitive, 28 Index instance, 27	set system, 99 set-ordering scheme, 100
	isolated, 22	simplicial, 19
	monotone, 18	solutions, 27 split, 20
	H-free, 17 P-completion, 24 P-deletion, 24 P-edge-subgraph, 24 neighbourhood, 16 neighbours, 16 node-deletion problem, 64 non-trivial, 64 P-edge-supergraph, 24 obstructions, 17 ≺ Π , 107 ordering scheme, 43	dependent set systems, 33 directed graph, 18 directed graphs, 18 dominating sets, 34 split partition, 20 strongly accessible, 103 strongly connected, 18 subgraph, 17 successor, 95 edge-deletion problem, 72 supergraph of solutions, 40, 42 edge-subgraph, 17 symmetric difference, 16
	accessible, 101 output-polynomial, 29	edge-supergraph, 17
	adjacent, 16 output-quasi-polynomial, 32	edges, 15 threshold, 22
	admissible sets, 100 output-sensitive, 28	enumeration algorithm, 28 threshold construction ordering, 22
	arcs, 18 outputs, 27	enumeration problem, 27 transition function, 42
	canonical ordering, 43 canonical path, 105 children, 106 chordal, 18 class, 17 clique tree, 20 parent, 38, 106 path, 16 perfect elimination ordering, 19 polynomial delay, 31 prefix closed, 107 prefix property, 101	extension problem, 35 extension problem for maximal edge-subgraphs, 69 extension problem for maximal induced P-subgraphs, 64 false twins, 16 transversal, 34 tree, 16 tree-decomposition, 19 true twins, 16 twin construction ordering, 21 twins, 16
	closed neighbourhood, 16 cographs, 21 Proximity Search, 42 proximity, 42, 102	fill edges, 24 Flashlight Search, 35 universal, 22
	commutable, 103 proximity searchable, 43, 102	forbidden induced subgraph, 17 vertices, 15
	commutable property, 103 complement, 16 connected, 16 connected-hereditary, 17 constant delay, 32 cotree, 21	girth, 72 graph, 15 graph edition, 26 graph modification, 26 Gray codes, 32
	cycle, 16	hereditary, 17
	degree, 16	incident, 16

Comment pourrais-je ne pas remercier Arnaud Mary pour tous les échanges et toutes les (bonnes) idées qui ont émergé de nos discussions et sessions de travail ? Maintenant c'est chose faite, et j'espère qu'on aura d'autres occasions d'échanger autour de l'énumération.During this thesis, I had the opportunity to meet several people from around the world and enjoyed discussing with them. First, I would like to thank Takeaki Uno who welcomed me twice in his lab in Tokyo. Then, a big thank you for the Italian team (Alessio, Andrea, Giulia, Davide, Alice and the others) and the Japanese team (Kunihiro, Kazuhiro, Takeaki, and the others) ; all the discussions we had during and around the WEPA conferences were precious ! Enfin, merci aux autres personnes avec qui j'ai pu travailler pendant cette thèse : Aline, Benjamin, Thomas, travailler avec vous, même à distance, fut une vraie réjouissance pour moi lors de cet épisode désagréable que fut le Covid (que je ne remercie pas, d'ailleurs). Merci aussi à tous et toutes les membres d'AlCoLoCo pour les sessions de travail au labo ou à la campagne, qui ont fait émerger de jolis résultats mais aussi et surtout de jolis problèmes !

That is to say, there must exist a bijection φ : X -→ V (H) such that for any two vertices u and v in X, uv ∈ E(G) if and only if φ(u)φ(v) ∈ E(H).

the first common vertex encountered when going from the leaves to the root

return T ;knapsack problem by extending partial solutions into maximal ones, or to enumerate all maximal feasible solutions of an inequality system[START_REF] Lawler | Generating all maximal independent sets: NP-hardness and polynomial-time algorithms[END_REF].It can also be used to solve enumeration problems on graphs. Lawler et al. applied their technique to the enumeration of all maximal complete k-partite subgraphs, that is, subgraphs formed of k disjoint sets, and where two vertices are adjacent if and only if they do not belong to the same set. Therefore, this technique gives an output-polynomial algorithm for the enumeration of maximal complete k-partite subgraphs.The setting being very general, Algorithm 2.1 can be applied to many different problems. It might not have the optimal complexity in all cases, but it still provides an efficient way to solve a large set of enumeration problems.

In mathematics, a function d : X × X → R ⩾0 on a set X is called a distance if it satisfies the properties of symmetry (∀x, y ∈ X, d(x, y) = d(y, x)), separation (∀x ∈ X, d(x, x) = 0), and the triangle inequality (∀x, y, z ∈ X, d(x, y) + d(y, z) ⩽ d(x, z)).

Remark 5.14. By Lemma 5.13, if F ∈ F then Del(F ) ∈ F min . That is to say, Del can be used to turn a chordal completion into a minimal one in a canonical way.

A quite weak assumption on a set system: it is accessible if for any non-empty member of the family, there exists an element that can be removed while staying in the family, or in more mathematical terms, ∀X ∈ F, X ̸ = ∅, ∃x ∈ X, X \ {x} ∈ F. All the set systems corresponding to sandwich-monotone graph properties are accessible.

Remerciements

Mes premiers remerciements vont naturellement à Vincent Limouzy, ainsi qu'à Aurélie Lagoutte et Lucas Pastor, pour leur encadrement pendant cette thèse au LIMOS. Je pourrais faire une énumération de toutes les raisons pour lesquelles je vous remercie mais je ne vais pas le faire, je laisse l'énumération pour le contenu proprement dit de ce manuscrit. Je voudrais surtout vous remercier d'avoir cru en moi et de m'avoir fait confiance quand je suis partie en disant que je reviendrais.

Merci Ioan Todinca d'avoir accepté d'être rapporteur de ma thèse, et merci pour vos commentaires enthousiastes sur mon travail. Roberto Grossi, thank you for having accepted to review my thesis, and for your constructive comments about my manuscript. Je remercie également Fatiha Bendali, Marthe Bonamy, Nofar Carmeli, Christian Laforest et Nicolas Trotignon pour avoir accepté de compléter mon (nombreux) jury, et pour les discussions intéressantes qui ont eu lieu lors de la soutenance.

To guarantee we are in the conditions of Theorem 6.15, it remains only to prove that the ordering scheme Can is prefix closed. This will not be very difficult since Can has been built this way. Lemma 6.16. The ordering scheme Can defined in Section 5.3.1 is prefix closed.

Proof. By construction, Can uses a preference relation on the non-elements of a partial solution, that is just the arbitrary ordering of E c among the candidates. Moreover, since the chordal completions of a graph are sandwich-monotone, it follows immediately that the ordering scheme Can has the prefix property.

Therefore, Can is straightforwardly prefix closed. Now, we are sure all requirements of Theorem 6.15 are satisfied. Therefore, it is possible to define for each solution F ̸ = F 0 its parent Parent(F ) as the last solution before F in its canonical path, as in Section 6.2. The parent of a solution is computable in polynomial time by lemma 6.9. We deduce the following result. Theorem 6.17. The minimal chordal completions of a graph can be enumerated with polynomial delay in polynomial space.

Maximal induced chordal subgraphs

In this section, we show that the canonical path reconstruction framework can be used on other problems that were known to admit a polynomial delay algorithm, but for which the existence of such an algorithm running in polynomial space was unknown. This is for example the case with two enumeration problems concerning chordal subgraphs: the enumeration of maximal induced chordal subgraphs and maximal connected induced chordal subgraphs. Both problems have been studied by Conte et al. in the light of the Proximity Search framework. Unless stated otherwise, any mention of their work in this section refers in fact to the original Proximity Search paper [START_REF] Conte | Proximity search for maximal subgraph enumeration[END_REF].

Here we consider the problem of listing maximal induced chordal subgraphs of a graph G. In the following, we assume that vertices of G are arbitrarily ordered. Since we work with induced subgraphs, the solutions will be seen as sets of vertices of G.

It is possible to enumerate maximal induced chordal subgraphs with polynomial delay, using the classical Proximity Search [START_REF] Conte | Proximity search for maximal subgraph enumeration[END_REF]. However, the algorithm obtained this way uses exponential space. We will see that the canonical path reconstruction framework can be used to reduce the space complexity of the problem. Conte et al., that we will use as well, is defined as follows. For a solution S ⊂ V , choose a vertex v of V \ S, and choose a maximal clique

Neighbouring function. The neighbouring function used by

. Then, add v to the solution and remove all neighbours of v in S that are not in Q (that is, remove N G (v) \ Q

APPLICATIONS OF CANONICAL PATH RECONSTRUCTION | 113

from the solution). This yields an induced chordal subgraph of G. It remains only to complete greedily the newly obtained solution into a maximal one denoted S v,Q . The neighbouring function for induced chordal subgraphs is illustrated in Figure 6.5. With the neighbouring function just defined, the set of neighbours of the solution S is defined as neighbours(S)

Since S is chordal, it has a linear number of cliques [START_REF] Fulkerson | Incidence matrices and interval graphs[END_REF][START_REF] Charles | Algorithmic graph theory and perfect graphs[END_REF], so there are a polynomial number of choices for Q. Therefore each solution has a polynomial number of neighbours, and the authors proved that this neighbouring function is proximity searchable.

Ordering scheme. It remains to find a suitable ordering on the elements of a solution. Recall that a perfect elimination ordering (PEO, defined page 19) of a graph is an ordering v 1 , . . . , v n of the vertices such that at each step i, the vertex v i is simplicial (its neighbourhood is a clique) in the subgraph induced by {v i , . . . , v n }, and chordal graphs are characterised by the existence of a PEO. In the original Proximity Search paper, the authors proved that all ordering schemes that produce reverse perfect elimination orderings of solutions are proximity searchable. We exhibit here such an ordering scheme which, in addition, is prefix closed. Indeed, the ordering scheme that was previously used to prove the existence of a polynomial delay algorithm for maximal induced chordal subgraphs fails to be prefix closed. More precisely, this ordering scheme consists in computing the entire lexicographically minimal perfect elimination ordering of the solution before reversing it. Consequently, if S is a maximal induced chordal subgraph with its reverse lexicographically minimal PEO, the ordering < S i of its ith prefix is not well defined in general. On the other hand, the "natural" greedy ordering, that can easily be computed on any solution, is prefix closed by definition but fails to be proximity searchable.

If G ′ = G[S] is an induced chordal subgraph of G, we consider π(G ′ ) = x 1 , . . . , x k the ordering of G ′ such that x 1 = min(S) and for each i < k, x i+1 is the smallest among vertices of maximum degree in {x 1 , . . . , x i }. In other words, we select at each step a vertex which has a maximum number of neighbours in the set of vertices already chosen. It has been proven by Tarjan & Yannakakis [START_REF] Tarjan | Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs[END_REF] that this procedure known as | 119 approach consisted in considering the complements of the chordal completions to define the proximity measure, which -to the best of our knowledge -had never been done previously.

Then, to be useful in practice, an efficient algorithm should only use polynomial space. That is why we considered the question of space usage for minimal chordal completions. Thanks to the sandwich monotonicity of chordal graphs, we were able to prove the existence of a polynomial delay, polynomial space algorithm. For this purpose, we introduced a parent relation between two solutions, permitting to explore the solution space without keeping in memory all the solutions already found.

Generalising this approach gave rise to a new extension of Proximity Search to obtain polynomial space: canonical path reconstruction. The requirements of this technique are weaker than those of the other Proximity Search-based polynomial space enumeration techniques [START_REF] Conte | Proximity search for maximal subgraph enumeration[END_REF]. Consequently, our framework can be applied to a wider range of problems, guaranteeing polynomial delay and polynomial space under weaker assumptions. Some of the problems that were solved at the beginning with Proximity Search satisfy in fact those requirements, one of which is the class being sandwichmonotone. For example, our technique directly gives an algorithm listing the maximal induced (connected or not) chordal subgraphs of a graph in polynomial space.

The results about polynomial delay enumeration algorithms mentioned in this thesis are summarised in Table 7 When considering the maximal subgraphs and minimal supergraphs, other classes of interest include -but are not limited to -triangle-free graphs (which may be a candidate for the non-existence of a polynomial delay algorithm), perfect graphs, and planar

Contributions Contributions on enumeration

The results presented in this thesis gave rise to the following two articles, one of which is published [START_REF] Brosse | Polynomial delay algorithm for minimal chordal completions[END_REF] and the other one is submitted to a specialised journal [START_REF] Brosse | Efficient enumeration of maximal split subgraphs and induced sub-cographs and related classes[END_REF].

Contributions on other subjects

Other results have been obtained during my PhD, that have not been presented in the present manuscript but gave rise to two papers, submitted to or published in specialised journals. They are about graph theory but do not concern enumeration.

Connected greedy colourings First, a project took place with the AlCoLoCo working group in Clermont-Ferrand about connected greedy colourings of graphs.

Given a graph G and a vertex ordering σ : v 1 . . . v n of V (G), the "first-fit" greedy colouring algorithm gives colours to all vertices of G in order σ by assigning to each vertex the smallest colour unused in its neighbourhood. By restricting this procedure to vertex orderings that are connected, we obtain connected greedy colourings.