Summary: In the \(\Pi \)-Cluster Editing problem, one is given an undirected graph \(G\), a density measure \(\Pi \), and an integer \(k\geq 0\), and needs to decide whether it is possible to transform \(G\) by editing (deleting and inserting) at most \(k\) edges into a dense cluster graph. Herein, a dense cluster graph is a graph in which every connected component \(K=(V _{K },E _{K })\) satisfies \(\Pi \). The well-studied Cluster Editing problem is a special case of this problem with \(\Pi :=\text{``being a clique''}\).
In this work, we consider three other density measures that generalize cliques: (1) having at most \(s\) missing edges (\(s\)-defective cliques), (2) having average degree at least \(|V _{K }| - s\) (average-\(s\)-plexes), and (3) having average degree at least \(\mu \cdot (|V _{K }| - 1)\) (\(\mu\)-cliques), where \(s\) and \(\mu \) are a fixed integer and a fixed rational number, respectively. We first show that the \(\Pi \)-Cluster Editing problem is NP-complete for all three density measures. Then, we study the fixed-parameter tractability of the three clustering problems, showing that the first two problems are fixed-parameter tractable with respect to the parameter \((s,k)\) and that the third problem is W[1]-hard with respect to the parameter \(k\) for \(0<\mu <1\).