AlGCo : algorithmique, graphes et combinatoire
Séminaire/Groupe de Travail

Département Informatique - LIRMM



Archives année 2008-2009 Organisateurs : Emeric Gioan, Alexandre Pinlou


Retour à la page d'accueil du séminaire

Sommaire


18 juin                            
Sylvain Guillemot
Permutations à motifs exclus

(travail commun avec Stéphane Vialette)

Etant données deux permutations \sigma, \pi, on dit que \sigma est un motif de \pi ssi il existe une sous-séquence de \pi qui induit un ordre isomorphe à \sigma. Dans un premier temps, on présentera quelques résultats classiques sur certaines classes de permutations closes par motifs (permutations stack-sortable, queue-sortable, séparables...). On s'intéressera ensuite à la complexité paramétrée du problème consistant à décider si une permutation de taille q est un motif d'une permutation de taille n. Le problème général est soluble en temps O(n^q) par recherche exhaustive. On s'intéresse au cas particulier où l'une des permutations est queue-sortable (de manière équivalente, décomposable en deux sous-séquences croissantes). On montre que cette restriction du problème admet des algorithmes plus efficaces que la recherche exhaustive.

11 juin                            
Michel Vasquez
Coloration des graphes de reines


Le problème de coloration de graphes de reines consiste à recouvrir un échiquier de dimension n avec n × n reines de telle sorte que deux reines de couleur identique ne s'attaquent pas. Jusqu'en 2003, le nombre chromatique de ces graphes, X(n), pour n supérieur à 9 et multiple de 2 ou 3, n'est pas connu.
Dans un premier temps je détaillerai un algorithme exact et complet de recherche de n ensembles indépendants qui recouvrent les n × n sommets (cases) de l'échiquier. Cet algorithme résout les instances n = 10 et n = 12 prouvant que X(10)=11 et X(12)=12. C'est l'élagage significatif de l'arbre de recherche par la prise en compte d'une contrainte sur la taille des cliques du sous-graphe des sommets non colorés qui permet d'atteindre ces résultats en quelques secondes.
Dans un deuxième temps, je présenterai une version incomplète de cet algorithme qui postule certaines caractéristiques géométriques que peuvent avoir les colorations minimales de ces graphes. Nous obtenons ainsi les résultats suivants : X(n)=n, pour n appartenant à {12,14,15,16,18,20,21,22,24,26,28,30,32}.
Enfin, à partir d'arithmétique élémentaire je démontrerai qu'il existe une infinité de valeurs de n multiples de 2 et/ou 3 telles que X(n)=n.
La question "X(n) est il égal à n pour tout n > 10 ?" reste ouverte et l'on ne sait toujours pas si X(27) est égal à 27 ou à 28.

4 juin                            
Guyslain Naves
Multiflots entiers et chemins disjoints


Nous nous intéressons aux problèmes d'existence de flots multicommodités. Une commodité est une paire de sommet (origine, destination), et pour chacune de ces paires, nous voulons trouver un flot d'un débit donné, de telle sorte que la somme des flots respectent la capacité des arêtes du graphe. Après un introduction à ce problème, nous rappelerons les principaux résultats du domaine, en particulier les derniers développement, puis montrerons la difficulté du problème de trouver un multiflot entier avec seulement deux commodités dans les graphes planaires. Pour finir, nous regarderons un petit problème de chemins disjoints "à la Mader".



Transparents de l'exposé 14 mai                            
Mike Fellows
The Lost Continent of Polynomial Time: Meta-theorems About FPT Kernelization


Introducing a secondary significant measurement (the parameter) into the analysis of computational complexity, allows (among other things), a meaningful and mathematically precise study of the power of P-time pre-processing, an issue that is impossible to formulate in a natural way in the one-dimensional framework of P vs NP. The 2-dimensional framing of the issue has led to an explosion of results on concrete problems, that have proved to be of practical significance, and has also led to new general methods for establishing upper and lower bounds on the power of P-time pre-processing for parameterized problems. The talk will survey/advertise these new general methods in regards the Lost Continent.

30 avril                            
Jean Daligault
Chercher des arbres orientés avec beaucoup de feuilles


Je ferai une petite overview sur le problème consistant à trouver un arbre avec beaucoup de feuilles dans les graphes orientés. C'est un problème très étudié et très appliqué en non-orienté, mais d'étude plus récente en orienté. Je présenterai les résultats de deux papiers, avec Gregory Gutin, EunJung Kim et Anders Yeo, et avec Stéphan Thomassé : un algorithme paramétré rapide (en c^k avec c<4), un noyau quadratique pour la version enracinée, et un algorithme d'approximation à facteur constant.


23 avril                            
Jorge Ramirez Alfonsin (Equipe Combinatoire Paris 6)
Matroides : arrangements, polytopes et noeuds

Séminaire commun ARITH/AlGCo

Les matroïdes, introduits par H. Whitney en 1935, constituent aujourd’hui l’un des outils fondamentaux de la combinatoire structurelle. Dans cet exposé, je présenterai plusieurs résultats obtenus en utilisant la théorie des matroïdes, liés aux problèmes géométriques (concernant les polytopes et les arrangements d’hyperplans) et topologiques (relatifs aux noeuds).


9 avril                            
Daniel Gonçalves
Les forêts de Schnyder et leur applications (la suite)

Résumé en images de l'exposé précédent : ici

Il y a 20 ans W. Schnyder donnait une caractérisation surprenante des graphes planaires G=(V,E) en terme de dimension de la relation d'incidence (définie sur V ∪ E). Dans cet exposé nous expliciterons cette caractérisation et nous explorerons les différentes structures combinatoires qui en découlent (forêts de Schnyder, étiquetage des angles à la Schnyder, 3-orientations)". Nous verrons ensuite l'usage qu'il a été fait de ces structures pour faire des dessins compactes, des codages quasi-optimaux et des générateur aléatoires de graphes planaires.


26 mars                            
Serge Gaspers (postdoc AlGco)
Analyse des algorithmes de branchement


Exposé n°2 d'une petite série sur les Algorithmes Exponentiels. Résumé et transparents du n°1 : ICI.

Les algorithmes de branchements sont souvent utilisés pour résoudre des problèmes NP-durs de manière exacte. On les trouve dans la littérature sous différentes appelations: Branch-and-Reduce, Branch-and-Bound, Branch-and-Search, Branching, Pruning the Search Tree, Backtracking, DPLL, et Splitting algorithms.
Ce sont des algorithmes récursifs qui réduisent une instance d'un problème à des sous-instances plus petites, résolvent le problème pour ces sous-instances récursivement et combinent leurs solutions pour obtenir une solution pour l'instance de départ.
Nous nous intéressons ici à analyser le temps d'exécution au pire des cas de ces algorithmes. Contrairement à d'autres techniques de conception d'algorithmes exponentiels, comme la programmation dynamique et la technique d'inclusion-exculsion, il est beaucoup moins clair comment borner le temps d'exécution d'algorithmes de branchement. Leur analyse est un facteur très important et non trivial dans leur conception ; la conception et l'analyse s'influencent mutuellement.
Dans cet exposé, nous allons voir comment analyser ce genre d'algorithmes. Commençant par une analyse triviale, nous allons l'améliorer pas à pas pour aboutir finalement aux techniques d'analyse de pointe de nos jours.
A la fin, je vais aussi présenter un exemple d'algorithme paramétré analysé avec ces techniques.

Transparents de l'exposé

05 février                            
Daniel Gonçalves
Les forêts de Schnyder et leur applications


Il y a 20 ans W. Schnyder donnait une caractérisation surprenante des graphes planaires G=(V,E) en terme de dimension de la relation d'incidence (définie sur V ∪ E). Dans cet exposé nous expliciterons cette caractérisation et nous explorerons les différentes structures combinatoires qui en découlent (forêts de Schnyder, étiquetage des angles à la Schnyder, 3-orientations)". Nous verrons ensuite l'usage qu'il a été fait de ces structures pour faire des dessins compactes, des codages quasi-optimaux et des générateur aléatoires de graphes planaires.

Résumé en images

29 janvier                            
Igor Razgon
Fixed-Parameter Tractability of 2-CNF Deletion problem


Fixed-parameter algorithms provide an alternative methodology of coping with NP-hardness that allows to solve hard optimization problems exactly and in a low-polynomial time. The necessary condition for design a fixed-parameter algorithm is the presence of a parameter associated with the given problem. The time complexity of a fixed-parameter algorithm can be represented in a form $O(f(k)*n^c)$, where $k$ is the parameter, $f(k)$ is an exponential function on the parameter, $c$ is a constant usually not greater than 3. Thus a fixed-parameter algorithm is exponential in the parameter but polynomial in the input size. The low-polynomial time is achieved for small values of $k$.
The design of fixed-parameter algorithms was inspired by observation that in areas like bioinformatics and network design many hard problems are associated with natural parameters that in practice are very small.
Problems that admit fixed-parameter algorithms are called fixed-parameter tractable (FPT) and the area of Theoretical Computer Science studying various aspects of fixed-parameter tractability and intractability is called Parameterized Complexity. One of the key question investigated in the area is classification of problems i.e. telling whether a particular problem is FPT. The community identified a number of most challenging open questions related to classification of problems. One of such questions is understanding whether the following problem is FPT: given a 2-CNF formula, is it possible to remove at most $k$ clauses so that the resulting formula becomes satisfiable? This problem is called 2-CNF deletion. It attracted attention of researchers due to a large number of potential applications of this problem. Despite a number of attempts to solve the problem, the status of fixed-parameter tractability of the problem remained unresolved for more than 10 years. The fixed-parameter tractability of the problem has been confirmed in Razgon, O'Sullivan "Almost 2-SAT is fixed-parameter tractable", ICALP 2008.
In this talk I will briefly introduce the are of parameterized complexity and overview main ideas of the fixed-parameter algorithm for the 2-CNF deletion problem. The talk is designed for the audience completely unfamiliar with the area of Parameterized Complexity.

Transparents de l'exposé

22 janvier                            
Serge Gaspers (postdoc AlGco)
Introduction aux Algorithmes Exponentiels


Exposé n°1 d'une petite série sur les Algorithmes Exponentiels.

Cet exposé est le premier d'une petite série d'exposés sur les algorithmes exponentiels. Chaque problème NP-complet peut être résolu par une recherche exhaustive, mais certains de ces problèmes admettent des algorithmes beaucoup plus rapides, bien que leur temps d'exécution est toujours exponentiel. Après une introduction du domaine des algorithmes exponentiels, je vais présenter les principales techniques utilisées dans la conception d'algorithmes exponentiels : programmation dynamique, brancher et réduire, mémorisation, algorithmes basés sur des décompositions arborescentes, combinaison entre techniques, inclusion-exclusion, et la compression itérative. Ces techniques vont être illustrés par des algorithmes pour les problèmes suivants : Voyageur de Commerce, Ensemble Stable, Coloration, et Hitting Set.

Transparents de l'exposé

11 décembre                            
Nicolas Trotignon (LIAFA)
4-dans-un-arbre pour les graphes sans triangles


Quelques problèmes de détection de sous-graphes induits seront présentés. L'algorithme le plus général permettant d'attaquer ce type de problème est "three-in-a-tree'' de Chudnovsky et Seymour. Three-in-a-tree decide en temps O(n^4) si trois sommets donnés d'un graphe appartiennent à un arbre induit. En collaboration avec N. Derhy et C. Picouleau, nous avons étudié "four-in-a-tree" pour les graphes sans triangles. Nous donnons une réponse structurelle à la question suivante : à quoi ressemble un graphe sans triangles dont aucun arbre induit ne couvre quatre sommets donnés ? Notre resultat principal affirme qu'un tel graphe doit avoir la "même structure", dans un sens précisément défini, qu'un carré ou qu'un cube. Nous donnons un algorithme en temps O(nm) qui, étant donné un graphe sans triangles G et quatre de ses sommets, retourne ou bien un arbre induit qui contient les sommets, ou bien une partition de V(G) certifiant qu'un tel arbre n'existe pas. Nous prouvons que le problème consistant à décider s'il existe un arbre T couvrant les quatre sommets et dont les quatre branches se rejoignent en un seul sommet est NP-complet.

4 décembre                            
Florian Huc (Sophia-Antipolis)
Mixing digraphs


Le théorème de Turan indique que le nombre maximum d'arêtes d'un graphe sans K_k est (1-1/(k-1))n^2/2. Dans le cas des graphes orientés (sans deux cycles), ce théorème ne se généralise pas de manière satisfaisante. En effet, un graphe orienté acyclique peut avoir un nombre d'arcs maximum sans contenir aucun sous-digraphe ayant un cycle. Seulement un tel graphe orienté a une orientation fortement biaisée. Nous avons introduit un paramètre pour savoir si seul de tels graphes orientés peuvent éviter des sous-graphes tout en ayant un grand nombre d'arcs. Ce paramètre sera présenté ainsi que les premiers résultats le concernant.

20 novembre                            
Frédéric Koriche
Autour de #P: Problèmes d'apprentissage et de raisonnement qui utilisent le comptage.


Depuis sa découverte par Leslie Valiant (mon maître absolu) , la classe #P a fait l'objet de nombreuses recherches en algorithmique combinatoire et en intelligence artificielle. Informellement, #P est la classe des problèmes de comptage qui ont un certificat de décision polynomial. Dans cet exposé, nous commencerons par mettre en évidence cette classe en présentant des problèmes importants en raisonnement et d'apprentissage, comme l'inférence dans un réseau bayésien ou la classification par gradient exponentiel, qui sont fondamentalement liés à la classe #P. Nous présenterons ensuite certaines sous-classes de problèmes qui peuvent être démontrées polynomiales ou FPT. Nous terminerons par quelques conjectures en reliant ces problèmes d'apprentissage et de raisonnement avec des résultats prometteurs obtenus par les algorithmes « randomisés » (classes FPRAS).

13 novembre                            
Philippe Gambette
Décomposition et reconstruction de réseaux phylogénétiques de niveau k depuis des triplets


Pour représenter l'Evolution, un modèle plus complexe que celui de l'arbre phylogénétique a été introduit : le réseau phylogénétique. En particulier, les réseaux phylogénétiques explicites sont des graphes orientés acycliques enracinés de degré maximum 3, dont les noeuds de degré entrant 2 représentent des événements d'hybridation, recombinaison, ou des transferts horizontaux de gènes entre espèces. Leur structure générale étant arborée, la hiérarchie des réseaux de niveau k, basée sur leur décomposition en composantes biconnexes, a récemment été introduite. Je montrerai comment formaliser cette décomposition à partir de générateurs, puis présenterai des méthodes de reconstruction d'arbre phylogénétique et de réseau de niveau k à partir de leur ensemble de triplets, c'est à dire des arbres à trois feuilles qu'ils contiennent.

16 octobre                            
Mike Fellows
The Main Subprograms and Developing Directions in Parameterized Algorithms and Complexity


In 2008 The Computer Journal published a double special issues of sixteen surveys of various aspects and applications areas of parameterized complexity and algorithmics; this shows something about how the field has developed over the last ten years. The talk will be based on the Foreword to these volumes, that attempted to summarize the main subprograms that have emerged in this field, and will focus on the main open problems and research horizons.

9 octobre                            
Christophe paul
Clique multicolorée et réductions paramétriques


Nous montrerons comment le problème de clique multicolorée, qui consiste à trouver une clique transversal à un ensemble de couleurs, peut être utilisé pour prouver que la difficulté de certains problèmes paramétrisée par la tree-width ou la path-width.

2 octobre                            
Anthony Perez
Noyaux polynomiaux pour Closest 3-leaf power


Dans cet exposé, nous nous intéresserons à des problèmes d'édition de graphes et à l'existence de noyaux pour ces problèmes. En particulier, nous nous intéresserons aux p-leaf powers : un graphe G = (V,E) est un p-leaf power ssi il existe un arbre T dont les feuilles sont V et tel qu'on ait (u,v) dans E ssi d_T(u,v) <= p. Plus exactement, le problème du closest p-leaf power (demandant s'il est possible d'éditer un graphe G en au plus k modifications d'arêtes pour le transformer en p-leaf power) sera étudié. L'appartenance à FPT pour ce problème (p=3,4) a été prouvée par Dom et al., impliquant l'existence de noyaux exponentiels. Nous prouvons l'existence d'un noyau cubique pour les problèmes closest 3-leaf power, 3-leaf power completion et 3-leaf power edge-deletion.

25 septembre                            
Eunjung Kim (Royal Holloway, Londres)
FPT algorithm for Minimum Leaf Out-branching Problem


Given a digraph D, the Minimum Leaf Out-Branching problem (MinLOB) is the problem of finding in D an out-branching with the minimum possible number of leaves, i.e., vertices of out-degree 0. We prove that MinLOB is polynomial-time solvable for acyclic digraphs. In general, MinLOB is NP-hard and we consider three parameterizations of MinLOB. We prove that two of them are NP-complete for every value of the parameter, but the third one is fixed-parameter tractable (FPT). The FPT parametrization is as follows: given a digraph D of order n and a positive integral parameter k, check whether D contains an out-branching with at most n-k leaves (and find such an out-branching if it exists). We find a problem kernel of order O(k2) and construct an algorithm of running time O(2^{O(k log k)}+n6), which is an "additive" FPT algorithm. We also consider transformations from two related problems, the minimum path covering and the maximum internal out-tree problems into MinLOB, which imply that some parameterizations of the two problems are FPT as well.

18 septembre                            
Jean Daligault
Un Noyau Polynomial pour Multicut In Trees


Je présenterai les notions d'algorithme FPT et de noyau (kernel en anglais), et je montrerai les règles de réduction que nous utilisons pour le problème Multicut In Trees : étant donné un arbre, un ensemble de requêtes (i.e. de chemins de l'arbre), et un entier k, existe-t-il un ensemble de k aretes qui coupent toutes les requêtes.

9 septembre                            
Pavol Hell
Graphs and Polymorphisms


Polymorphisms are useful in logic and algebra, and seem the right tool for solving constraint satisfaction problems. I will illustrate their use in graph theory by characterizing interesting old and new graph classes.

9 septembre                            
Thomas Erlebach
Domination in geometric intersection graphs

This is joint work with Erik Jan van Leeuwen.

Dominating set problems in geometric intersection graphs can be motivated by routing backbone construction problems in wireless ad-hoc networks. For intersection graphs of disks and other fat objects, existing approximation techniques do not seem to be able to handle the dominating set problem except in the special case of unit-size objects. We present approximation algorithms and inapproximability results that shed new light on the approximability of the dominating set problem in geometric intersection graphs. On the one hand, we show that for intersection graphs of arbitrary fat objects, the dominating set problem is as hard to approximate as for general graphs. For intersection graphs of arbitrary rectangles, we prove APX-hardness. On the other hand, we present a new general technique for deriving approximation algorithms for various geometric intersection graphs, yielding constant-factor approximation algorithms for $r$-regular polygons, where $r$ is an arbitrary constant, and for rectangles with bounded aspect ratio. For arbitrary fat objects with bounded ply, we get a $(3+\epsilon)$-approximation algorithm.

9 septembre                            
Michel Habib
Some new and old results on simplicial elimination scheme on chordal and interval graphs


In this talk we study again these central objects which appear to be important for the structural analysis of chordal graphs. We provide some new properties of maximal clique trees, which lead to interesting algorithmic problems.
Finally we describe and prove in this context an old algorithm M.H, C. Paul R. McConnell (2000) for interval graph recognition.

9 septembre                            
Binh-Minh Bui Xuan
Représentation arborescente de familles d'ensembles et applications en décomposition de graphes et en algorithmique de graphes

Soutenance de thèse.

Cette thèse développe certains aspects autour de trois thèmes généraux, sur la représentation arborescente des familles d'ensembles, les décompositions de graphes, et les algorithmes de graphes. Les thèmes abordés vont de la combinatoire théorique à l'algorithmique en bio-informatique, en passant par plusieurs décompositions de graphes et aussi par l'optimisation combinatoire.
La première moitié du manuscrit développe deux études. D'abord, afin d'estimer le nombre de familles satisfaisant certains axiomes de clôture, de nouveaux outils et techniques pour obtenir des représentations arborescentes de celles-ci ont été développés. Puis, l'étude se poursuit avec une des applications des propriétés ci- dessus : celle concernant les décompositions de graphes.
Enfin, la deuxième moitié du manuscrit est consacrée aux applications des décompositions de graphes dans l'algorithmique de graphes. Trois problèmes algorithmiques seront à l'étude. Dans chacun des trois, il sera montré pourquoi et comment on peut appliquer l'idée de la décomposition de graphes pour résoudre le problème posé de manière efficace. Il est également montré comment appliquer les trois solutions proposées pour résoudre trois autres problèmes d'algorithmique de graphes.