Le problème étudié est celui de la distance d'édition d'un graphe à l'ensemble des linegraphs. Le linegraph (ou graphe des arêtes en français) d'un graphe G = (V,E) non orienté est le graphe contenant un noeud par arête de G et on relie deux noeuds si les arêtes correspondantes sont incidentes au même noeud dans G. Dans ce problème, on appelle distance d'édition, entre deux graphes G1 et G2 non orientés, le nombre d'arêtes qu'il faut enlever de G1 et/ou ajouter à G1 pour obtenir G2. Puisqu'on ne peut ajouter ou retirer de noeuds, les deux graphes ont nécessairement le même nombre de noeuds. Connaissant un graphe G non orienté, l'objectif est de trouver le linegraph le plus proche de G en terme de distance d'édition. Par exemple, sur le graphe de droite, une distance d'édition pour obtenir un linegraph est 2. Une arête a été ajoutée (en pointillé) et une autre enlevée (marquée d'une croix). Le graphe dont est issu ce linegraph est une étoile de taille 4 plus une arête incidente à une des feuilles de l'étoile. On peut noter que cette solution n'est pas optimale. Une telle solution consiste à supprimer l'arête centrale entre les deux noeuds du bas.
Nous avons démontré que ce problème est NP-Complet, même si on ne s'autorise qu'à retirer ou qu'à ajouter des arêtes. Une heuristique a également été créée pour le cas général. Cette heuristique essaie de construire un linergraph avec les arêtes de G. Si G est un linegraph, l'algorithme le reconnait et renvoie une distance nulle. Sinon, l'heuristique ajoute ou retire des arêtes pour transformer G en linegraph, en étant guidée par la solution partielle produite à l'étape précédente. Nous avons démontré que le problème est FPT vis-à-vis de la largeur arborescente et nous avons généralisé ce résultat à des linegraphs d'hypergraphes.