Largeur de clique

Construction d'un graphe (ici un graphe à distance héréditaire) de largeur de clique 3 par une succession d'unions disjointes, de renommages et de fusions d'étiquettes. Les étiquettes des sommets sont affichées sous forme de couleurs.

En théorie des graphes, la largeur de clique d'un graphe $G$ est l'un des paramètres qui décrit la complexité structurelle du graphe ; il est étroitement lié à largeur arborescente, mais contrairement à celle-ci, elle peut être bornée même pour des graphes denses .

Définition

La largeur de clique d'un graphe $G$ est le nombre minimum d'étiquettes nécessaires pour construire $G$ au moyen des 4 opérations suivantes :

• Création d'un nouveau sommet v d'étiquette i (noté i(v) ou ${\bullet }_i$)
• Union disjointe de deux graphes étiquetés G et H (notée $G\oplus H$)
• Jonction par une arête de chaque sommet étiqueté i à chaque sommet étiqueté j (noté η(i,j)), où $i\ne j$
• Renommage de l'étiquette i en étiquette j (notée ρ (i, j) ou ${\rho }_{i\to j}$).

Dans l’exemple, le graphe final est obtenu par la jonction des trois sommets rouges et des deux sommets verts ; le graphe précédent est l’union disjointe des eux graphes bleu-rouge et vert-bleu, etc. La suite des graphes construits par les opérations est figurée dans l'arbre des opérations.

Les graphes de largeur de clique bornée comprennent les cographes et les graphes à distance héréditaire. Il est NP-difficile de calculer la largeur de clique lorsqu'elle n'est pas bornée, et il est inconnu si elle peut être calculée en temps polynomial lorsqu'elle est bornée ; des algorithmes d'approximation efficaces pour la largeur de clique existent. Sur la base de ces algorithmes et du théorème de Courcelle, de nombreux problèmes d'optimisation de graphes qui sont NP-difficiles pour des graphes arbitraires peuvent être résolus ou approximés rapidement sur les graphes de largeur de clique bornée.

Les séquences de construction sous-jacentes au concept de largeur de clique ont été formulées par Courcelle, Engelfriet et Rozenberg en 1990Modèle:Sfnp et par Wanke en 1994Modèle:Sfnp. Le nom de largeur de clique ("clique-width") a été utilisé pour un concept différent par Chlebíková en 1992Modèle:Sfnp . Depuis 1993, le terme a son sens actuelModèle:Sfnp.

Un exemple

Une suite détaillée d'opérations conduisant à un graphe de largeur de clique 3 est donnée dans la table suivante.

Arbre pour la construction de $C_6$

Opération	Visualisation
$G_1={\bullet }_1$
$G_2={\bullet }_2$
$G_3=G_1\oplus G_2$
$G_4={\eta }_{1,2}(G_3)$
$G_5=G_4\oplus G_4$
$G_6=G_5\oplus {\bullet }_3$
$G_7={\eta }_{1,3}(G_6)$
$G_8={\rho }_{3\to 1}(G_7)$
$G_9=G_8\oplus {\bullet }_3$
$C_{10}={\eta }_{2,3}(G_9)$

L'expression correspondante est :

${\eta }_{2,3}({\rho }_{3\to 1}({\eta }_{1,3}(\eta ({\bullet }_1\oplus {\bullet }_2)\oplus \eta ({\bullet }_1\oplus {\bullet }_2)\oplus {\bullet }_3))\oplus {\bullet }_3)$

Classes particulières de graphes

Les cographes sont exactement les graphes avec une largeur de clique au plus 2Modèle:Sfnp. Chaque graphe à distance héréditaire a une largeur de clique au plus 3. La largeur de clique des graphes d'intervalles unitaires est non bornée (en fonction de leur structure de grille)Modèle:Sfnp. De même, la largeur de clique des graphes de permutation biparti est non bornée (basée sur une structure de grille similaire)Modèle:Sfnp. La caractérisation des cographes comme les graphes sans sous-graphe induit isomorphe à un chemin de quatre sommets sans corde permet de calculer la largeur de clique de nombreuses classes de graphes définies par des sous-graphes induits exclus.

Bornes

Courcelle et Olariu en 2000Modèle:Sfnp et Corneil et Rotics en 2005Modèle:Sfnp ont donné les bornes suivante pour la largeur de clique de certains graphes :

• Si un graphe a une largeur de clique au plus Modèle:Mvar, alors il en est de même pour chaque sous-graphe induit du graphe.
• Le graphe complémentaire d'un graphe de largeur de clique Modèle:Mvar a une largeur de clique d'au plus Modèle:Formule .
• Les graphes de largeur arborescente Modèle:Mvar ont une largeur de clique d'au plus Modèle:Formule . La dépendance exponentielle dans cette borne ne peut être évitée : il existe des graphes dont la largeur de clique est exponentiellement plus grande que leur largeur d'arbre. Inversement, les graphes de largeur de clique bornée peuvent avoir une largeur d'arbre non bornée ; par exemple, les graphes complets à Modèle:Mvar sommets ont une largeur de clique 2 mais une largeur d'arbre Modèle:Formule . Cependant, les graphes de largeur de clique Modèle:Mvar qui n'ont pas de graphe biparti complet Modèle:Formule comme sous-graphe ont une largeur d'arbre d'au plus Modèle:Formule . Par conséquent, pour toute famille de graphes creux, avoir une largeur d'arbre bornée équivaut à avoir une largeur de clique bornéeModèle:Sfnp.
• Un autre paramètre de graphes, le largeur de rang, est borné dans les deux sens par la largeur de la clique : largeur de rang ≤ largeur de la clique ≤ 2 ^{largeur de rang + 1}Modèle:Sfnp.

Par ailleurs, si un graphe Modèle:Mvar a une largeur de clique Modèle:Mvar, alors la puissance Modèle:Formule a une largeur de clique d'au plus Modèle:FormuleModèle:Sfnp. Bien qu'il y ait un écart exponentiel des bornes entre la largeur de clique et la largeur d'arbre et la largeur de clique des puissances de graphe, ces bornes ne se combinent pas : si un graphe Modèle:Mvar a une largeur d'arbre Modèle:Mvar, alors Modèle:Formule a une largeur de clique au plus égale à Modèle:Formule, qui est simplement exponentielle en la largeur de l'arbreModèle:Sfnp.

Complexité de calcul

De nombreux problèmes d'optimisation qui sont NP-difficiles pour des classes de graphes générales peuvent être résolus efficacement par programmation dynamique sur des graphes de largeur de clique bornée, lorsqu'une séquence de construction pour ces graphes est connueModèle:SfnpModèle:,Modèle:Sfnp. En particulier, chaque propriété de graphe qui peut être exprimée dans la logique monadique du second ordre MSO₁ (une forme de logique permettant la quantification sur des ensembles de sommets) admet un algorithme en temps linéaire pour les graphes de largeur de clique bornée, par une des formes du théorème de CourcelleModèle:Sfnp. Des résultats sur les bornes pour des propriétés de classes de graphes ont été données par Bergougnoux et KantéModèle:Sfnp. Des classes de graphes fermés par passage au sous-graphe induits sont présentés dans un article de synthèse de Konrad K. Dabrowski Matthew Johnson et Daniël PaulusmaModèle:Sfnp.

Des colorations de graphes optimales ou des cycles hamiltoniens pour les graphes de largeur de clique bornée se calculent en temps polynomial, lorsqu'une séquence de construction est donnée, mais l'exposant du polynôme augmente avec la largeur de clique, et les preuves de la théorie de la complexité montrent que cette dépendance est inévitableModèle:Sfnp. Les graphes de largeur de clique bornée ont la propriété que leur nombre chromatique est au plus une fonction de la taille de leur plus grande cliqueModèle:Sfnp.

Les graphes de largeur de clique 3 peuvent être reconnus, et une séquence de construction peut être construite, en temps polynomial à l'aide d'un algorithme basé sur la Modèle:LienModèle:Sfnp. Pour les graphes de largeur de clique non bornée, il est NP-difficile de calculer exactement la largeur de clique, et aussi NP-difficile d'obtenir une approximation avec une erreur additive sous-linéaireModèle:Sfnp. Cependant, quand la largeur de clique est bornée, il est possible d'obtenir une séquence de construction de largeur bornée (exponentiellement plus grande que la largeur de clique réelle) en temps polynomial. Il est ouvert si la largeur exacte de la clique, ou une approximation plus stricte de celle-ci, peut être calculée en temps traitable à paramètres fixes, ou si elle peut être calculée en temps polynomial pour chaque borne fixe de la largeur de la clique, ou même si les graphes de largeur de clique quatre peuvent être reconnu en temps polynomialModèle:Sfnp.

Liens avec la largeur arborescente

La théorie des graphes de largeur de clique bornée est similaire à celle des graphes de largeur arborescente bornée, mais contrairement à la largeur arborescente, elle s'applique aussi à des graphes denses. Si une famille de graphes a une largeur de clique bornée, alors soit elle a une largeur arborescente bornée, soit chaque graphe biparti complet est un sous-graphe d'un graphe de la familleModèle:Sfnp. La largeur arborescente et la largeur de clique sont également reliés par la théorie des line graphs : une famille de graphes a une largeur d'arbre bornée si et seulement si leurs line-graphs ont une largeur de clique bornéeModèle:Sfnp.

Si on note $cw(G)$ la largeur de clique et $tw(G)$ la largeur arborescente de $G$, on a l'inégalitéModèle:Sfnp :

$cw(G)\le 3\cdot 2^{tw(G)-1}$.

On ne peut pas majorer la largeur d'arborescene par une expression en la largeur de clique, comme on peut voir sur les graphes complets : Le graphe complet $K_n$ a l largeur arborescente $n-1$ et une largeur de clique au plus 2. On a donc pour $n\ge 4$ :

$cw(K_n)<tw(K_n)$.

Si $G$ n'a pas de graphe biparti complet Modèle:Formule comme sous-graphe, alorsModèle:Sfnp :

$tw(G)\le 3\cdot (t-1)\cdot cw(G)-1$.

Bibliographie

• Modèle:Article

• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Article. — Une version préliminaire a été présentée à Graph grammars and their application to computer science (Brème, 1990), Modèle:MR.
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Chapitre
• Modèle:Article
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Chapitre.
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.