AlGCo : algorithmes, graphes et combinatoire

Nicolas Trotignon CNRS, Ens Lyon
Décomposition des graphes parfaits.

La conjecture forte des graphes parfaits, énoncée dans les années 1960 par Claude Berge a été démontrée en 2002 par Chudnovsky, Robertson, Seymour et Thomas par des méthodes de décompositions de graphes. Je rappellerai très brièvement les principales notions et les idées de la preuve. J'insisterai sur le verrou qui empêche d'utiliser la preuve pour résoudre la dernière "grande question" ouverte sur les graphes parfaits, à savoir leur coloration en temps polynomial par un algorithme purement combinatoire. Ce verrou provient de décompositions "pathologiques", qui ont de bonnes propriétés pour la preuve, mais pas pour les algorithmes, par exemple les "skew partitions" inventées par Chvatal. Les skew partitions ont pour cas particulier les "star cutset", dont il sera principalement question par souci de simplification. A la fin de l'exposé, je présenterai très brièvement un résultat obtenu récemment avec Chudnovsky, Trunck et Vuskovic : un algorithme en temps polynomial qui colore les graphes parfaits sans "balanced skew partition".

Annie Chateau LIRMM
Parcours optimaux de graphes de scaffolding avec ou sans répétitions.

Cet exposé débutera inévitablement par des (rapides et compréhensibles) considérations bioinformatiques, notamment sur le séquençage et l'assemblage de génome, permettant de mettre en perspective les problèmes exposés par la suite. Mais nous ferons à cette occasion la connaissance d'un graphe fort intéressant, le graphe d'échafaudage (scaffold graph). En plus d'être de taille potentiellement rédhibitoire, ces graphes, qui sont en réalité des multigraphes arêtes-valués munis d'un couplage parfait, ne sont ni planaires, ni métriques, pas vraiment denses ni vraiment peu denses, et possèdent encore d'autres qualités qui leur permettent de s'échapper des classes de graphes classiques. Le problème consiste à linéariser ces graphes tout en optimisant une (ou plus...) fonction de poids sur les arêtes. Je présenterai tout d'abord une version (très) simplifiée du problème, qui rejoint le problème du MAX-TSP pour lequel on dispose d'algorithmes d'approximation. Ensuite, je vous présenterai quelques extensions du modèle, notamment en introduisant des multiplicités au niveau des arêtes du couplage, des multi-critères, des transformations du graphe, etc. Nous pourrons discuter de potentielles solutions de ces extensions, limitées uniquement par la puissance de notre imagination et la réalité biologique de ces graphes.

Gwenaël Joret Université Libre de Bruxelles
On Sheehan's second hamiltonian cycle conjecture.

An old conjecture of Sheehan states that every hamiltonian d-regular graph with d > 2 has at least two hamiltonian cycles. The d=3 case is a classical theorem of Smith & Tutte (1946). More generally, the conjecture is known to be true for every odd d (Thomason, 1977). For even d on the other hand, nothing was known until Thomassen showed in 1998 that the conjecture holds if d is large enough. His approach uses the probabilistic method and has subsequently been improved by various authors, the current record being d >= 24 (Haxell, Seamone, Verstraete, 2006).

In this talk I will give an informal introduction to this topic, focusing on the different proof techniques. These include Thomason's lollipop argument, the Lovasz Local Lemma, and the recent entropy compression method of Moser and Tardos.

Masters (2)
Amal Mejdoub & Jean-Florent Raymond

Amal Mejdoub : Sommet-arboricité dans les graphes planaires.

La sommet-arboricité d'un graphe G est le nombre minimum k tel qu'on peut partitionner l'ensemble des sommets de G en k sous-ensembles induisant chacun une forêt. Pour les graphes planaires, la sommet-arboricité est au plus 3. Je vais m'intéresser pendant mon stage à étudier la complexité de la taille de la plus grande forêt dans les graphes planaires bipartis et degré maximum 4. Il a été montré que décider si la sommet-arboricité est au plus 2 est NP-complet dans les graphes planaires maximaux. A partir de ce résultat, je vais étudier la complexité de la 2-sommet-arboricité dans les graphes planaires de degré borné. Enfin, je vais améliorer des bornes déjà existantes pour la plus grande forêt et la plus petite forêt.

Jean-Florent Raymond : Extensions du théorème d'exclusion des graphes planaires.

Un résultat majeur de la théorie des mineurs est le théorème d'exclusion des graphes planaires. Après un bref rappel des notions et de résultats classiques, je présenterai quelques développements récents autour de l'exclusion de graphes planaires particuliers et de la relation d'Erdős–Pósa.

Masters (1)
Julien Baste & Margaux Nattaf

Julien Baste : The role of planarity in connectivity problems parameterized by treewidth.

Dans cette présentation nous nous intéresserons à des problèmes "de connexité" paramétrés par la treewidth. Notre objectif est de montrer les liens et les différences de complexité de ces problèmes entre les graphes généraux et les graphes planaires. Nous utiliserons trois exemples montrant l'existence de trois types différents de problèmes : 3-Coloring, Cycle Packing et Monochromatic Disjoint Paths. Les complexités considérées sont toutes comprises entre 2^{O(tw)}*poly(n) et 2^{O(tw log tw)}*poly(n), où tw est la treewidth et n le nombre de sommets du graphe en entrée.

Margaux Nattaf : Kernels et Matroides.

Récemment développées, les techniques de kernelisation à base de matroïdes ont permis de trouver des noyaux polynomiaux (randomisés) pour certains problèmes pour lesquels leur existence était inconnu tels que Odd Cycle Transversal, Almost 2-SAT ou des restrictions de problèmes de coupes (s-Multiway cut, s-Multicut).

Kolja Knauer I3M, Université Montpellier 2
Three ways to cover a graph.	Les transparents de l'exposé -->

We consider the problem of covering a host graph G with several graphs from a fixed template class T. The (classical) covering number of G with respect to T is the minimum number of template graphs needed to cover the edges of G. Parameters that arise this way are for example thickness, track-number and all kinds of arboricities. We introduce two new covering parameters: the local and the folded covering number. As in the global covering number each measures how far G is from the template class in a certain sense. The folded covering number has been investigated thoroughly for some template classes, e.g., interval graphs and planar graphs, yielding interval and splitting number, respectively. The local covering number was given only little attention. The three covering numbers presented not only unify the notion in the literature, they as well seem interesting in their own right, e.g., provide new approaches to attack or support classical open problems. We provide new bounds on some covering numbers w.r.t. several template classes. The classical graph parameters turning up this way are interval-number, track-number, and linear-, star-, and caterpillar arboricity. As host graphs we consider graphs of bounded degeneracy, bounded degree, or bounded tree-width, as well as, outerplanar, planar bipartite and planar graphs. We also discuss some algorithmical questions. Joint-work with Torsten Ueckerdt.

Jaroslaw Blasiok University of Warsaw
Chain minor ordering is Fixed Parameter Tractable.

We study certain < relation on finite posets called "chain minor", and in particular "Chain Minor Ordering" problem of deciding for given posets $P$ and $Q$ $P < Q$. We prove that "Chain Minor Ordering" problem admits FPT solution, when parametrized by $|P|$; our algorithm has time complexity $O(f(|P|)|Q| \log |Q|)$, and linear space complexity, therefore solving open question by Downey and Fellows. We also present randomized version of this algorithm having slightly better time complexity (with respect to $|Q|$): $\Oh(f(|P|)|Q|)$. It has long been known, due to work of Gustedt, that "chain minor" relation is well-quasi-order; such relations became recently widely studied, mainly because every set of objects closed under wqo relation could be characterized by finite set of forbidden objects with respect to that relation. In particular, presented algorithm for "Chain Minor Ordering" yields linear algorithm for recognition problem for any family closed under chain minor.

Mathias Weller LIRMM, Montpellier
Interval Scheduling and Colorful Independent Sets.

INDEPENDENT SET is a famous NP-hard graph problem which, given an undirected graph G and an integer k, asks whether G contains at least k vertices that all are pairwise non-adjacent. In particular, it has numerous applications in scheduling, e.g. resource allocation and steel manufacturing. Here, one encounters special graph classes such as 2-union graphs (that is, edge-wise unions of two interval graphs on the same vertex set) and subclasses thereof, including strip graphs (that is, requiring one of the two interval graphs to be a disjoint union of cliques). Independent Set remains NP-hard in these restricted cases but, in particular, is known to show better polynomial-time approximability (constant-ratio approximations). We complement and extend known results by providing a dichotomy concerning the complexity for Independent Set on 2-union graphs: it becomes polynomial-time solvable when both input interval graphs are restricted to be cluster graphs and it is NP-hard, otherwise. Moreover, we identify natural parameterizations and, in particular, use these to chart the possibilities and limits of effective polynomial-time preprocessing and fixed-parameter algorithms for Independent Set on these practically motivated graph classes, including the well-known JOB INTERVAL SELECTION problem. Our investigations significantly profit from novel formulations of the underlying problems using (list-)colored interval graphs, which give the problems a more combinatorial than a geometric flavor.

Nicolas Lichiardopol Lycée A. de Craponne, Salon, France
Proof of Caccetta-Hagkvist conjecture for oriented graphs of independence number 2

In his paper "On the Caccetta-Häggkvist conjecture with forbidden subgraphs" (see [1]), A. Razborov says that Chudnovski and Seymour proved that an out-regular oriented graph of out-degree d >= 2, of independence number 2 and of order at most 3d contains a directed triangle, which means that Caccetta-Häggkvist conjecture is verified by such an oriented graph. He says also that to the best of his knowledge, the question is still open without the restriction of out-regularity. In this paper, we give a complete answer, by proving that for d >= 2, any oriented graph of minimum out-degree d >= 2, of independence number 2 and of order at most 3d contains a directed triangle. Additionally, we prove that any oriented graph of minimum out-degree d >= 1, of independence number 2 and of order at most 4d contains a directed cycle of length at most 4. A simple observation on the girth of a non-acyclic oriented graph of independence number 2, allows us to state that the Caccetta-Häggkvist conjecture is true for oriented graphs of minimum out-degree at least 1 and of independence number 2.
References
[1] A. Razborov, On the Caccetta-Häggkvist conjecture with forbidden subgraphs, submitted to Journ. of Graph Theory (arXiv :1107.2247v1, 2011)

Cedric Chauve Simon Fraser University, Canada
Propriété des Uns Consécutifs : problèmes algorithmiques motivés par l'assemblage de génomes.
Travail en cours et en collaboration avec Eric Tannier, Jano Manuch, Murray Patterson, Roland Wittler, Ashok Rajaraman, Annie Chateau.

La Propriété des Uns Consécutifs se définit comme suit : une matrice binaire satisfait cette propriété si on peut ordonner ses colonnes de sorte que pour chaque ligne, les entrées 1 soient consécutives. En termes d'hypergraphes, cette propriété correspond à une notion de "bandwidth" 0 (on veut ordonner les sommets d'un hypergraphe de sorte que chaque arête corresponde à un intervalle de sommets) ou encore à une notion de couverture d'un hypergraphe par des chemins.
La Propriété des Uns Consécutifs est un concept qui a été très utilisé dans les années 80 pour la construction de cartes physiques de génomes (les colonnes d'une matrice binaire représentant des marqueurs génomiques et les lignes des ensembles de marqueurs supposé consécutifs le long d'un chromosome).
Dans cet exposé, nous allons discuter de problèmes algorithmiques pour une généralisation des Uns Consécutifs, les Uns Consécutifs avec Multiplicité : à chaque colonne de la matrice considérée on associe un entier positif bornant le nombre d'occurrence possibles de cette colonne. Cette variante est motivée par l'importance des régions répétées dans le génomes qui en rendent l'assemblage difficile.
Nous discuterons de deux types de problèmes : décider si une matrice binaire donnée satisfait la Propriété des Uns Consécutifs avec Multiplicité, et si la réponse est non, supprimer un nombre minimum de lignes pour obtenir une sous-matrice qui la satisfait (un problème de suppressiond d'arêtes donc).
L'exposé comprendra un survol assez complet des résultats existants, ainsi que quelques résultats récents positifs (algorithmes en temps polynomial)

David Auger Université de Versailles-Saint-Quentin-en-Yvelines
Simple Stochastic Games : a state of the art	Les transparents de l'exposé

Simple Stochastic Games (SSG for short) were introduced by Anne Condon in 1989 to study computational complexity issues related to alternating Turing machines. The algorithmic problem of computing the value, or equivalently the optimal strategies, of SSGs is one of the few problems known to belong to the NP inter co-NP complexity class for which we do not know a polynomial time algorithm. The question of whether it lies in P has been opened for more than twenty years now. In this talk, we will present these games, as well as other related classes of games, and the state of the art concerning their algorithmic issues.

Rémy Belmonte University of Bergen, Norway
Induced immersions	Les transparents de l'exposé
Joint work with Pim van't Hof and Marcin Kaminski

A graph G contains a multigraph H as an induced immersion if H can be obtained from G by a sequence of vertex deletions and lifts. We present a polynomial-time algorithm that decides for any fixed multigraph H whether an input graph G contains H as an induced immersion. We also show that for every multigraph H with maximum degree at most 2, there exists a constant c_H such that every graph with treewidth more than c_H contains H as an induced immersion.

Stefan Felsner Technische Universität Berlin, Allemagne
Torus Squarings	Les transparents de l'exposé
joint work with E. Fusy

A squaring is a tiling into squares of different sizes. In a seminal paper Brooks, Smith, Stone and Tutte (1940) discussed squarings related to segment contact representations of planar quadrangulations. Regarding the squares of a squaring as vertices and edges as being defined by contacts we obtain the square dual graph. Schramm (1993) showed that 5-connected inner triangulations of a 4-gon can be represented as square duals. In this talk we review the plane situation and present some results concerning squarings of the torus and the graphs represented by them.

Guillaume Guégan LIRMM, Montpellier
Les matroïdes orientés comme graphes signés	Les transparents de l'exposé

Un matroïde orienté peut être vu comme la donnée des bases d'un matroïde et d'une signature de celles-ci, signature devant vérifier une axiomatique non triviale.
Pendant mon stage de M2 je me suis posé la question suivante : comment décorer (orienter, colorier) un graphe des bases (objet bien caractérisé pour les matroïdes non-orientés) afin de faire apparaître les caractéristiques d'un matroïde orienté ? J'y répondrai dans cet exposé en établissant une bijection entre matroïdes orientés uniformes (modulo une relation d'équivalence) et une famille de bicolorations des graphes des bases. Je traduirai ensuite plusieurs notions de la théorie des matro??des orientés ? dualité, réétiquetage, changement de signe, existence de mutation ? en notions sur les graphes signés : inversions de signes, isomorphismes, flips autorisés.

Alessandro Maddaloni University of Southern Denmark
Fixed parameter tractability and kernels for feedback set problems on generalization of tournaments	Les transparents de l'exposé
Joint work with Jørgen Bang-Jensen and Saket Saurabh

We focus on the parametrized version of the directed feedback vertex (arc) set prob- lem: given a directed graph D and a positive integer k, decide whether there exists a set of at most k vertices (arcs) of D, whose removal makes the digraph acyclic.
We discuss the existence of polynomial kernels for these parametrized problems on digraphs with particular decomposition properties or bounded independence num- ber, including locally semicomplete digraphs and quasi-transitive digraphs. Our results generalize known results on tournaments.
Finally we present a subexponential time algorithm for feedback arc set on locally semicomplete digraphs.

Boris Albar LIRMM, Montpellier
Autour de la conjecture d'Hadwiger	Les transparents de l'exposé

La conjecture d'Hadwiger affirme que la classe des graphes sans mineur K_t est (t-1)-coloriable. La conjecture a été prouvée pour t <= 6. Nous nous intéresserons principalement au cas t = 7. Nous donnerons un aperçu des problèmes ouverts et des techniques utilisés pour prouver certains résultats partiels, notamment le résultat de Kawarabayashi et Toft montrant que les graphes sans mineur K_7 et K_{4,4} sont 6 coloriables. Nous prouverons aussi que les graphes sans K_7 mineur sont 8 coloriables.

Alexander Grigoriev Maastricht University, Pays-Bas
The Valve Location Problem in Simple Network Topologies
Joint work with: Hans L. Bodlaender; Nadejda V. Grigorieva; Albert Hendriks

To control possible spills in liquid or gas transporting pipe systems, the systems are usually equipped with shutoff valves. In case of an accidental leak these valves separate the system into a number of pieces limiting the spill effect. In this paper, we consider the problem, for a given edge-weighted network representing a pipe system and for a given number of valves, to place the valves in the network in such a way that the maximum possible spill, i.e. the maximum total weight of a piece, is minimized. We show that the problem is NP-hard even if restricted to any of the following settings: (i) for series-parallel graphs and hence for graphs of treewidth two; (ii) if all edge weights equal one. If the network is a simple path, a cycle, or a tree, the problem can be solved in polynomial time. We also give a pseudo-polynomial time algorithm and a fully polynomial approximation scheme for networks of bounded treewidth.

Alexandre Pinlou LIRMM, Montpellier
Homomorphismes de graphes signés

Un graphe signé (G,S) est un graphe G avec une assignation de signes + et - sur toutes ses arêtes (S est l'ensemble d'arêtes négatives). De plus, deux graphes (G,S1) et (G,S2) sont considérés comme équivalents si la différence symétrique de S1 et S2 est une coupe. B. Guenin a introduit la notion d'homomorphismes de graphes signés : on dit que (G1,S1) admet un homomorphisme vers (G2,S2) s'il existe un graphe signé (G1,S1') équivalent à (G1,S1) et une fonction f : V(G1) -> V(G2) telle que (1) si xy est une arête de G1 alors f(x)f(y) est une arête de G2 et (2) xy appartient à S1' ssi f(x)f(y) appartient à S2. Cette notion d'homomorphisme permet de définir le nombre chromatique signé de manière analogue au nombre chromatique classique.

Dans cet exposé, je vous commencerai par vous présenter des propriétés des graphes signés. Je montrerai entre autres des bornes supérieures pour le nombre chromatique signé de certaines classes de graphes closes par mineurs (graphes planaires extérieurs, graphes planaires, k-arbres partiels, ...).

Mickael Montassier LIRMM, Montpellier
Limits of near-coloring of sparse graphs	Les transparents de l'exposé
Joint work with Paul Dorbec, Tomá? Kaiser, André Raspaud

Let a, b, d be non negative integers. A graph G is (d, a, b)*-colorable if its vertex set can be partitioned into a + b sets I1, . . . , Ia,O1, . . . ,Ob such that the graph G[Ii] induced by Ii has maximum degree at most d for 1 ≤ i ≤ a, while the graph G[Oi] induced by Oi is an edgeless graph for 1 ≤ i ≤ b. In this paper, we give two real valued functions f and g such that any graph with maximum average degree at most f(d, a, b) is (d, a, b)*-colorable, and there exist non (d, a, b)*-colorable graphs with average degree at most g(d, a, b). Both these functions converge (by lower values) to 2a+b when d tends to infinity. Counterintuitively, this implies that allowing a color to be d-improper even for a large degree d allows to extend the maximum average degree of the family of colorable graphs only by 1. In other words, using a color of type Ii (even with a very large degree d) is somehow less powerful than using two colors of type Oi (two stable sets).

Michael Rao LIP, Lyon
Quelques petits résultats et encore beaucoup de conjectures sur la suite de Kolakoski/Oldenburger	Les transparents de l'exposé

La suite de Kolakoski, introduite - comme son nom ne le dit pas - par R. Oldenburger en 1939, est une suite auto-descriptive simple. Il s'agit de la suite 'w' sur {1,2} qui est égale à son propre "run-length-encoding" RLE(w). La ième lettre de RLE(w) est la taille du ième bloc de 'w', un bloc étant une répétition d'une même lettre. Cette suite commence donc par 12211212212211...

Malgré sa définition simple, beaucoup de conjectures concernant cette suite sont ouvertes depuis une trentaine d'années. Il y a notamment la conjecture que la densité de 1 dans 'w' est 0.5. Concernant cette conjecture, la meilleure borne supérieure de 0.50084 a été donnée par V. Chvátal en 1993.

Dans cet exposé, on verra cette suite comme un point fixe d'un transducteur. En prenant les puissances de ce transducteur, on obtiendra une nouvelle borne sur la densité. Cela nous permet également d'avoir un algorithme qui a permis d'explorer les 10^19 premières lettres de la suite. On finira par quelques nouvelles conjectures et questions sur cette suite.

Jørgen Bang-Jensen University of Southern Denmark
Flows, graphs, (arc-)disjoint paths and flows

Flows in networks constitute probably the most important application of graph theory with litterally hundreds of practical applications. In this talk we will introduce flows and the fundamental max-flow min-cut theorem and show how this basic result has important applications as a proof techniques in graph theory. Then we will go on to the (arc)-disjoint paths problem and discuss the complexity of this problem in both graphs and digraphs. In the last part of the talk we will introduce a common generalization of flows and disjoint paths, the (arc-)disjoint flow problem.

Pascal Ochem LIRMM, Montpellier
Bornes inférieures pour les nombres parfaits impairs	Les transparents de l'exposé
Travail en commun avec Michael Rao.

Un nombre est parfait si il est égal à la somme de ses diviseurs propres. On rappelle les résultats connus sur les nombres parfaits. On montre qu'un nombre parfait impair est supérieur à 10^1600, et on donne des bornes inférieures sur le nombre de ses facteurs premiers.

Nicolas Bousquet LIRMM, Montpellier
Séparer les cliques des stables	Les transparents de l'exposé

On considère un graphe G. On donne à Alice une clique C et à Bob un ensemble stable S du graphe. Alice et Bob désirent déterminer si C et S s'intersectent en échangeant la quantité minimum d'informations. Autrement dit, on veut minimiser, sur l'ensemble des protocoles possibles, le nombre maximum de bits échangés.
Yannakakis a montré que déterminer le nombre minimum de bits échangés pour un protocole non déterministe correspond exactement à séparer les cliques et les stables dans le graphe. Huang et Sudakov ont montré que cette conjecture était liée à une conjecture d'Alon, Saks et Seymour.
Nous montrerons que ces problèmes sont en fait équivalents. Nous montrerons également qu'il est équivalent à des problèmes de satisfaction de contraintes. Nous nous intéresserons ensuite plus particulièrement au problème de séparation des cliques et des stables pour des classes de graphes particulières.

Dimitrios M. Thilikos LIRMM, Montpellier
Exclusion theorems for partial orderings on graphs

Some of the most important results in graph theory are related to the description of the structure of graphs not ``containing'' some specific graph. Several interpretations of the word ``contained'', in terms of different partial orderings in graphs, provide different such theorems. We give a short presentation of the history of this type of results, the main achievements, their algorithmic consequences, and the current challenges on this area.

Benjamin Lévêque LIRMM, Montpellier
Toroidal maps : Schnyder woods, orthogonal surfaces and straight-line representations	Les transparents de l'exposé

A Schnyder wood is an orientation and coloring of the edges of a planar map satisfying a simple local property. We propose a generalization of Schnyder woods to graphs embedded on the torus with application to graph drawing. We prove several properties on this new object. Among all we prove that a graph embedded on the torus admits such a Schnyder wood if and only if it is an essentially 3-connected toroidal map. We show that these Schnyder woods can be used to embed the universal cover of an essentially 3-connected toroidal map on an infinite and periodic orthogonal surface. Finally we use this embedding to obtain a straight-line flat torus representation of any toroidal map in a polynomial size grid.

Rémi Watrigant LIRMM, Montpellier
The k-Sparsest Subgraph Problem in (Proper) Interval Graphs	Les transparents de l'exposé

Given a graph G=(V, E) and an integer k, the k-Sparsest Subgraph (k-SS) problem asks for a set of k vertices in G which induces the minimum number of edges. As a generalization of the classical Independent Set problem, k-SS is W[1]-hard as well as inapproximable in general graphs. In this talk we provide an FPT algorithm in interval graphs and a Polynomial-Time Approximation Scheme in proper interval graphs, both using dynamic programming.

Kevin Sol LIRMM, Montpellier
Une méthode combinatoire pour l'étude morphométrique 3D basée sur des points de repère, application à l'étude de crânes	Les transparents de l'exposé
En collaboration avec Emeric Gioan et Gérard Subsol.

La morphométrie est l'étude et l'analyse de la géométrie d'objets. Elle permet de décrire quantitativement les variations de formes à partir de points de repère (landmarks en anglais). Nous proposons une nouvelle méthode combinatoire pour analyser, classifier et caractériser les formes 3D des configurations de landmarks. Dans cette méthode nous commençons par coder les configurations de landmarks à l'aide de matroïdes orientés, avant de réaliser une classification des matroïdes orientés et obtenir une caractérisation de ces classes. Lors de l'exposé, nous présenterons comment coder de façon combinatoire un modèle 3D, puis nous étudierons si les méthodes habituelles de classification (k-means, arbres de décision) peuvent servir à classer ces modèles et à caractériser ces classes. Nous présenterons par la suite notre méthode de classification supervisée adaptée aux matroïdes orientés nous permettant d'obtenir une caractérisation des différentes classes. Enfin nous terminerons par une application clinique de notre méthode portant sur l'étude de crânes.

Christophe Paul LIRMM, Montpellier
Un algorithme FPT simple exponentiel pour le problème Planar-F deletion

Soit F une famille de graphes. Le problème F-deletion consiste à tester s'il est possible de supprimer un ensemble d'au plus k sommets dans un graphe G pour obtenir un graphe H ne contenant pas de mineurs issus de F. Le cas F={K_2} correspond au problème Vertex Cover et F={K_3} à Feedback Vertex Set. Si la famille F contient au moins un graphe planaire le problème est nommé Planar-F-Deletion. Nous proposons un algorithme FPT en simple exponentiel (i.e. en $c^{O(k)}.n^{O(1)}$) pour Planar-F-deletion. Notre algorithme utilise la compression itérative, des règles de branchement et de réductions de protrusions. Le coeur de notre méthode est le calcul efficace d'une décomposition en protrusions (une décomposition utilisée dans de nombreux résultats). Nous présenterons l'algorithme et parlerons de ces conséquences.