Complexité du problème de distance d’édition minimum à un line-digraphe
Time: 14:00 -- Location: LRI, 445
summary: La distance d'édition est une mesure classique utilisée pour évaluer la proximité entre un graphe donné et un autre graphe
ou une classe de graphes. Cette distance représente le nombre minimum de modifications requises pour transformer le graphe initial
en un graphe appartenant à la classe voulue. Une étude a été menée sur la classe des line-graphes pour son application possible
dans la reconstitution d'information sur les topologies de réseaux électriques. Nous nous concentrons ici sur la version orientée
du problème, la classe des line-digraphes.
Nous avons montré que le problème de décision associé au problème d'édition est polynomial pour la complétion (seul l'ajout d'arc
est autorisé). Nous avons aussi montré que le problème est NP-complet pour la suppression (uniquement des retraits d'arc). La
difficulté du problème est liée à la présence d'un sous-graphe partiel particulier, le Z, un graphe à quatre sommets et trois arcs
liés ainsi : (u, v), (w, v) et (w, x). En particulier, le problème reste NP-Complet même si le graphe est une union de Z et il est
FPT lorsqu'il est paramétré par le nombre de Z présents dans le digraphe.