Largeur de clique

En théorie des graphes, la largeur de clique d'un graphe 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 .

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.

Définition

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

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

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 1990[1] et par Wanke en 1994[2]. Le nom de largeur de clique ("clique-width") a été utilisé pour un concept différent par Chlebíková en 1992[3] . Depuis 1993, le terme a son sens actuel[4].

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
OpérationVisualisation

L'expression correspondante est :


Classes particulières de graphes

Les cographes sont exactement les graphes avec une largeur de clique au plus 2[5]. 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)[6]. De même, la largeur de clique des graphes de permutation biparti est non bornée (basée sur une structure de grille similaire)[7]. 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 2000[5] et Corneil et Rotics en 2005[8] ont donné les bornes suivante pour la largeur de clique de certains graphes :

  • Si un graphe a une largeur de clique au plus k, alors il en est de même pour chaque sous-graphe induit du graphe[9].
  • Le graphe complémentaire d'un graphe de largeur de clique k a une largeur de clique d'au plus 2k[10] .
  • Les graphes de largeur arborescente w ont une largeur de clique d'au plus 3 · 2w 1 . 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[11]. Inversement, les graphes de largeur de clique bornée peuvent avoir une largeur d'arbre non bornée ; par exemple, les graphes complets à n sommets ont une largeur de clique 2 mais une largeur d'arbre n 1 . Cependant, les graphes de largeur de clique k qui n'ont pas de graphe biparti complet Kt,t comme sous-graphe ont une largeur d'arbre d'au plus 3k(t 1) 1 . Par conséquent, pour toute famille de graphes creux, avoir une largeur d'arbre bornée équivaut à avoir une largeur de clique bornée[12].
  • 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[13].

Par ailleurs, si un graphe G a une largeur de clique k, alors la puissance Gm a une largeur de clique d'au plus 2kmk[14]. 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 G a une largeur d'arbre w, alors Gm a une largeur de clique au plus égale à 2(m + 1)w + 1 2, qui est simplement exponentielle en la largeur de l'arbre[15].

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 connue[16],[17]. En particulier, chaque propriété de graphe qui peut être exprimée dans la logique monadique du second ordre MSO1 (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 Courcelle[17]. Des résultats sur les bornes pour des propriétés de classes de graphes ont été données par Bergougnoux et Kanté[18]. 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 Paulusma[19].

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évitable[20]. 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 clique[21].

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 décomposition fractionnée (en)[22]. 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éaire[23]. 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[24]. 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 polynomial[23].

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 famille[12]. 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ée[25].

Si on note la largeur de clique et la largeur arborescente de , on a l'inégalité[26] :

.

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 a l largeur arborescente et une largeur de clique au plus 2. On a donc pour  :

.

Si n'a pas de graphe biparti complet comme sous-graphe, alors[12] :

.

Notes et références

Bibliographie

  • Benjamin Bergougnoux et Mamadou Kanté, « Fast exact algorithms for some connectivity problems parameterized by clique-width », Theoretical Computer Science, vol. 782, , p. 30-53 (DOI 10.1016/j.tcs.2019.02.030, lire en ligne)
  • Portail des mathématiques
  • Portail de l'informatique théorique
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.