Algorithmique Combinatoire (LIRMM)

Mon exposer va consister à démontrer la NP-complétude des 3 problèmes suivants (ou juste de 2, ou juste de 1 suivant le temps de réceptivité de mon auditoire)~:

• Problème : LCS
  Données : Un langage fini non vide W et un entier k.
  Question : Existe-t'il un sous-mot de longueur k commun à tous les mots du langage W ?
  
• Problème : Center String
  Données : Un langage fini non vide W et un entier k.
  Question : Existe-t'il un mot fini s tel que pour tout w dans W, on ait lev(s, w) < k (où lev désigne la distance d'édition) ?
  
• Problème : Median String
  Données : Une liste de mots finis w_1, ..., w_n et un entier K.
  Question : Existe-t'il un mot fini s vérifiant lev(s, w_1) + ... + lev(s, w_n) < K ?
  

D'après le livre de V.V. Vazirani, Approximation Algorithms

Comment peut-on établir une garantie d'approximation pour un algorithme sans connaître la solution optimale au problème concerné (problème NP-dur) ? Une solution classique consiste à rechercher une borne inférieure calculable en temps polynomial.

Nous aborderons 3 problèmes utilisant des techniques algorithmiques différentes :

1. vertex cover : algorithme glouton
2. set cover : décomposition en niveaux
3. k-center : utilisation d'un paramètre d'élagage

Un couplage induit de G est un sous-graphe de G de la forme c.K2 (2c sommets de degré 1 et c arrêtes). Il s'agit de maximiser c. Selon la classe de graphes considéré, le problème est P ou NP. Pour convaincre tous mes auditeurs potentiels de l'intérêt de la chose, une liste de problèmes pratiques (?), dont il s'agit de déterminer si la solution est P ou NP, est accessible par un click.

D'après l'article de M. Chrobak et D. Eppstein, Planar Orientations with Low Out-Degree and Compaction of Adjacency Matrices

Nash-Williams a montré que les arêtes d'un graphe planaire peuvent être partitionnées en 3 forêts. Cet article présente 3 algorithmes pour calculer une telle partition. Le premier nécessite un plongement du graphe dans le plan, le second s'en passe. Tout deux ont une complexité linéaire. Le troisième est un algorithme parallèle pour ce problème.

Un résumé des résultats présentés est disponible (attention : ce texte n'est pas complètement stable).

Un circuit intégré peut etre vu comme un graphe. Pour tester la correction d'un circuit intégré, il est nécessaire de pouvoir réinitialiser l'ensemble de ce circuit. Pour cela, nous sommes ramener à calculer un coupe cycle dans un graphe. Le problème du calcul d'un coupe cylce minimum est approximable. Nous présenterons un algorithme probabiliste glouton pour ce problème.

D'après l'article Algorithms and Complexity of Sandwich problems in Graphs de Golumbic, Kaplan et Shamir.

Soient G₁ et G₂ deux graphes définis sur le même ensemble V de sommets tels que E₁ est inclus dans E₂. Le "sandwich problem" pour la propriété P consiste à tester s'il existe un graphe G=(V,E) tel que E₁ inclus dans E et E inclus dans E₂. L'article fait une synthèse sur les propriétés pour lesquelles ce problème est polynomial, NP-Complet.

Un étiquetage des distances pour un graphe est une affectation d'étiquettes à chaque sommet du graphe de telle sorte que la distance entre 2 sommets quelconques puissent être calculée ou approximée en n'utilisant que leurs étiquettes.
Une famille de graphes possède un étiquetage implicite des distances si le nombre de graphes à n sommets de la famille est 2^f(n) et que la taille des étiquettes utilisées est en O(f(n)/n). La famille des graphes d'intervalles est la seule famille connue possédant un étiquetage implicite des distances. De manière surprenante cet étiquetage fait appel à une représentation des graphes de permutation.

L`exposé sera un résumé de deux articles sur le Codage du graphe du Web .

• The Link Database: Fast Access to Graphs of the Web, K. Randall et al. Data Compression Conference 2002.
• Efficient and Simple Encodings for the Web Graph, J.L. Guillaume. INRIA. 2002.

L'exposé sera une présentation du chapitre d'introduction du livre Intersection Graph Theory de T. McKee et FR. McMorris. Nous présenterons des propriétés générales sur les graphes d'intersections ainsi que quelques problèmes ouverts.
Un résumé des résultats présentés est disponible (attention : ce texte n'est pas complètement stable).