Parameterized Algorithms for Balanced Cluster Edge Modification Problems
<|reference_start|>Parameterized Algorithms for Balanced Cluster Edge Modification Problems: We study {\sc Cluster Edge Modification} problems with constraints on the size of the clusters. A graph $G$ is a cluster graph if every connected component of $G$ is a clique. In a typical {\sc Cluster Edge Modification} problem such as the widely studied {\sc Cluster Editing}, we are given a graph $G$ and a non-negative integer $k$ as input, and we have to decide if we can turn $G$ into a cluster graph by way of at most $k$ edge modifications -- that is, by adding or deleting edges. In this paper, we study the parameterized complexity of such problems, but with an additional constraint: The size difference between any two connected components of the resulting cluster graph should not exceed a given threshold. Depending on which modifications are permissible -- only adding edges, only deleting edges, both adding and deleting edges -- we have three different computational problems. We show that all three problems, when parameterized by $k$, admit single-exponential time FPT algorithms and polynomial kernels. Our problems may be thought of as the size-constrained or balanced counterparts of the typical {\sc Cluster Edge Modification} problems, similar to the well-studied size-constrained or balanced counterparts of other clustering problems such as {\sc $k$-Means Clustering}.<|reference_end|>
@article{madathil2024parameterized,
    title={Parameterized Algorithms for Balanced Cluster Edge Modification Problems},
    author={Jayakrishnan Madathil, Kitty Meeks},
    journal={arXiv preprint arXiv:2403.03830},
    year={2024},
    archivePrefix={arXiv},
    eprint={2403.03830},
    primaryClass={cs.DS cs.DM}
}