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

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.