Parameterized mixed cluster editing via modular decomposition

In this paper we introduce a natural generalization of the well-known problems Cluster Editing and Bicluster Editing, whose parameterized versions have been intensively investigated in the recent literature. The generalized problem, called Mixed Cluster Editing or $\mathcal{M}$-Cluster Editing, is formulated as follows. Let $\mathcal{M}$ be a family of graphs. Given a graph $G$ and a nonnegative integer $k$, transform $G$, through a sequence of at most $k$ edge editions, into a target graph $G^{\mathrm{\prime }}$ with the following property: $G^{\mathrm{\prime }}$ is a vertex-disjoint union of graphs $G_1,G_2,\dots$ such that every $G_i$ is a member of $\mathcal{M}$. The graph $G^{\mathrm{\prime }}$ is called a mixed cluster graph or ${\cal M}$-clustergraph\mathrm{.}Let${\cal K}$denotethefamilyofcompletegraphs,${\cal KL}$thefamilyofcomplete$l$-partitegraphs($l \geq 2$),and$\L={\cal K} \cup {\cal KL}$\mathrm{.}Inthisworkwefocusonthecase${\cal M} = {\cal L}$. Using modular decomposition techniques previously applied to Cluster/Bicluster Editing, we present a linear-time algorithm to construct a problem kernel for the parameterized version of $\mathcal{L}$-Cluster Editing. Keywords: bicluster graphs, cluster graphs, edge edition problems, edge modification problems, fixed-parameter tractability, NP-complete problems.