Correcting a Graph Into a Linegraph Minimizing Hamming Distance Edition Is NP-Complete and FPT by Treewidth

Abstract

Since Beineke's work in 1968 on linegraphs, attention has focused on the classification of graphs as linegraphs.
It is known that every graph $G$ is the linegraph of an hypergraph, and the question is to characterize that root graph.
We introduce the $C_{p,q}$ classes, defined as sets of graphs where each vertex can be covered by at most $p$ cliques, and each edge belongs to at most $q$ cliques.
These classes provide a comprehensive classification of linegraphs through a unified and parameterized approach.
They describe previously known graph classes - such as linegraphs of simple graphs, $p$-uniform hypergraphs and $p$-uniform $1$-linear hypergraphs - while being capable of generalization.
We study the complexity of determining the membership and edit distance of a graph to one of these classes.
We prove the first Fixed Parameter Tractable algorithm with respect to treewidth to compute the edit distance.