1 Présentation du problème étudié

On se propose dans cette présentation d'étudier le problème de la distance d'édition entre
un graphe et l'ensemble des linegraphs. Un linegraph ou graphe des arêtes est un graphe non
orienté obtenu à partir d'un autre graphe non orienté. Connaissant un graphe G = (V, E)
(simple ou non), le linegraph de G est un graphe H simple possédant un nœud ve pour chaque
arête e de G et une arête relie ve et vf si les arêtes e et f sont incidentes au même nœud dans
G. Cette définition peut se généraliser aux hypergraphes, où chaque nœud de H représente une
hyperarête et chaque arête indique si deux hyperarêtes ont une intersection non vide.

La distance d'édition est une mesure classique utilisée pour mesurer la proximité d'un graphe
non orienté à un autre graphe ou une classe de graphes (comme exemple de classe, on peut
citer les graphes planaires, les linegraphs, les graphes sans diamant induit, . . .). La distance est
le nombre minimum de corrections qu'il faut apporter à un graphe pour que le graphe résul-
tat appartienne à la classe en question. Les corrections sont de natures variées. On considère
généralement l'ajout et la suppression d'arêtes ou de nœuds. Ce problème a été abondamment
étudié pour de nombreuses classes, notamment sa complexité paramétrée vis-à-vis de la dis-
tance recherchée [1]. Dans cette étude on s'intéressera à la classe des linegraphs et à l'ajout et la
suppression d'arêtes.

2 Motivation

Dans les vieux immeubles, du fait d'un manque de documentation suffisante, il peut être
difficile de connaître le plan des réseaux encastrés dans les murs (par exemple les réseaux
électriques ou de plomberie). Une solution consiste à déterminer les interactions qui existent entre les liens apparents du réseau. Ces mesures donnent une probabilité que deux arêtes du
réseau soient incidentes au même nœud, ce qui permet de construire le linegraph du réseau. Cependant, les mesures n'étant pas parfaites, le graphe résultat n'est généralement pas un linegraph. Une correction est alors appliquée, en minimisant la distance d'édition à un linegraph.La motivation concernant l'extension aux hypergraphes est à ce jour purement théorique.

3 Caractérisation des linegraphs

Il existe une caractérisation sous forme de couverture en cliques des linegraphs. Un graphe H
est le linegraph d'un graphe simple si et seulement si on peut couvrir les arêtes de H avec des
cliques de sorte qu'un nœud appartienne à au plus deux cliques et chaque arête à au plus une
clique. Cette propriété se généralise au cas où le graphe G n'est pas simple en supprimant la
contrainte sur les arêtes [3]. Elle
se généralise aussi aux hypergraphes (et étend la caractérisation présentée dans [4]) : un graphe
H est un linegraph d'un hypergraphe où les hyperarêtes contiennent au plus p nœuds et où
l'intersection de deux hyperarêtes contient au plus q nœuds si on peut couvrir les arêtes de H
avec des cliques de sorte qu'un nœud appartienne à au plus p cliques et chaque arête à au plus
q cliques. On note Cpq cette classe de graphes. On peut noter que C11 est une classe spéciale
contenant des graphes qui sont un ensemble de cliques disjointes et qui correspondent aux
linegraphs d'une union d'étoiles. Déterminer l'appartenance d'un graphe à Cpq est polynomial
si p ≤ 2 [4, 6] mais NP-Difficile si p = q ≥ 4 ou p = 3 et q = 1 [7].

On s'intéresse au problème (DIST) : Soit p ≥ q, k ∈ N et un graphe simple H, peut-on
transformer H en un graphe de Cpq en ajoutant ou supprimant au plus k arêtes de H ?

On note DISTpq le problème DIST restreint à des valeurs fixées de p et q. En particulier
DIST11 est un problème connu sous le nom de Cluster Editing [5]. En généralisant la preuve
de NP-Complétude de ce problème [5], nous pouvons montrer que DISTpq est NP-Complet
pour toute valeur de p et q. Une première partie de nos contributions concerne la complexité
paramétrée vis-à-vis de k du problème DIST. L'appartenance de DIST11 à la classe FPT est un
résultat classique de recherche arborescente bornée [2] que l'on peut généraliser pour DISTpq
si p ≤ 2. A l'inverse, la NP-Complétude de l'appartenance à C31 et Cpp pour p ≥ 4 permet
de montrer immédiatement que DISTpq pour p ≥ 4 et q ≥ 4 et DISTp1 pour p ≥ 4 sont NP-
Complets même si k = 0. Nous avons étendu ces résultats aux problèmes DISTp2 pour p ≥ 3.
Les complexités de l'appartenance à la classe Cp3 et de DISTp3 pour p ≥ 3 sont ouvertes.

La seconde partie de notre contribution consiste en la preuve que DIST est FPT vis-à-vis
de la largeur arborescente de H et de p. La difficulté de cette preuve réside dans le fait de
montrer que la taille des cliques couvrant le linegraph le plus proche de H ne dépend que de
ces paramètres. Cette propriété permet d'éviter l'explosion combinatoire lors de la recherche.

Références

[1] Christophe Crespelle. Survey on graph algorithms parameterized by edge edit distances.
(749022), 2020.
[2] M Cygan, FV Fomin, L Kowalik, D Lokshtanov, D Marx, Ma Pilipczuk, Mi Pilipczuk, and
S Saurabh. Parameterized Algorithms. Springer, Cham, 2015.
[3] F Harary. Line Graphs. In Graph Theory, chapter 8. Addison Wesley, 1972.
[4] Ramin Javadi, Zeinab Maleki, and Behnaz Omoomi. Local Clique Covering of Graphs.
2012.
[5] Christian Komusiewicz and Johannes Uhlmann. Cluster editing with locally bounded mo-
difications. Discrete Applied Mathematics, 160(15) :2259–2270, 2012.
[6] Philippe G. H. Lehot and Philippe G. H. An Optimal Algorithm to Detect a Line Graph
and Output Its Root Graph. Journal of the ACM, 21(4) :569–575, oct 1974.
[7] Svatopluk Poljak, Vojtěch Rödl, and Daniel Turzík. Complexity of representation of graphs
by set systems. Discrete Applied Mathematics, 3(4) :301–312, 1981.