The complexity of cluster vertex splitting and company

作     者：Firbas, Alexander Dobler, Alexander Holzer, Fabian Schafellner, Jakob Sorge, Manuel Villedieu, Anais Wissmann, Monika 

作者机构：TU Wien Vienna Austria 

出 版 物：《DISCRETE APPLIED MATHEMATICS》 (Discrete Appl Math)

年 卷 期：2025年第365卷

页      面：190-207页

核心收录：

学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学] 

基　　金：Vienna Science and Technology Fund, WWTF Alexander von Humboldt-Stiftung, AvH 

主　　题：Parameterized algorithms Data reduction Compact letter display Computational complexity 

摘      要：Clustering a graph when the clusters can overlap can be seen from three different angles: We may look for cliques that cover the edges of the graph with bounded overlap, we may look to add or delete few edges to uncover the cluster structure, or we may split vertices to separate the clusters from each other. Splitting a vertex v means to remove it and to add two new copies of v and to make each previous neighbor of v adjacent with at least one of the copies. In this work, we study underlying computational problems regarding the three angles to overlapping clusterings, in particular when the overlap is small. We show that the above-mentioned covering problem is NP-complete. We then make structural observations that show that the covering viewpoint and the vertex- splitting viewpoint are equivalent, yielding NP-hardness for the vertex-splitting problem. On the positive side, we show that splitting at most k vertices to obtain a cluster graph has a problem kernel with O ( k ) vertices. Finally, we observe that combining our hardness results with structural observations and a so-called critical-clique lemma yields a simple alternative NP-hardness proof for the CLUSTER EDITING WITH VERTEX SPLITTING problem, where we add or delete edges and split vertices to obtain a cluster graph. (c) 2025 The Authors. Published by Elsevier B.V. This is an open access article under the CC BY license (http://***/licenses/by/4.0/).