Clique-width (largeur de clique).

Tout comme la tree-width (largeur arborescente) étudiée en cours, la clique-width (largeur de clique) est un paramètre lié à une décomposition/construction particulière, qui permet en autre lorsqu'elle est bornée de résoudre efficacement des problèmes d'optimisation par programmation dynamique.

L'objectif de ce sujet est de présenter une introduction à la clique-width et son intérêt algorithmique. La liste ci-dessous donne des exemples de questions qui peuvent se poser :

• Présenter la définition de la clique-width avec le type de construction qui lui est associée.
• Y a-t-il des liens entre la clique-width et d'autres paramètres classiques d'un graphe ?
• Y a-t-il des exemples de graphes de clique-width bornée mais de tree-width non-bornée ? et inversement ?
• Parmi les classes vue en cours, y en a-t-il de clique-width bornée ?
• Qui sont les graphes de clique-width 1 ? de clique-width 2 ?
• Il existe un théorème équivalent à celui pour la tree-width qui dit que les problèmes s'exprimant dans la logique MSOL ou LinEMSOL (ce qui comprend des classiques comme la clique max ou la 3-coloration) se résolvent en temps O(n) si la clique-width est bornée. Sur un exemple précis (p.ex. clique max), illustrer ce théorème pour les graphes de clique width ≤ k.
  

Quelques références (pas exhaustif).

• Linear Time Solvable Optimization Problems on Graphs of Bounded Clique Width, article de B. Courcelle, J. Makowski et U. Rotics, Theory Comput. Syst. 33 (2000). Un peu noyées entre différents résultats, les sections intéressantes ici sont surtout 2.1, 2.2, 4.1, 4.3, 4.4.
  
• Un morceau de Autour de la décomposition en coupes, thèse de J.-M. Lanlignel (2001), qui présente la clique-width.
  

Retour à la page des sujets.