×

\((1,1)\)-cluster editing is polynomial-time solvable. (English) Zbl 1521.05199

Summary: A graph \(H\) is a clique graph if \(H\) is a vertex-disjoin union of cliques. F. N. Abu-Khzam [J. Discrete Algorithms 45, 26–34 (2017; Zbl 1419.68056)] introduced the \(( a , d )\)-Cluster Editing problem, where for fixed natural numbers \(a , d\), given a graph \(G\) and vertex-weights \(a^\ast : V ( G ) \to \{ 0 , 1 , \ldots , a \}\) and \(d^\ast : V ( G ) \to \{ 0 , 1 , \ldots , d \}\), we are to decide whether \(G\) can be turned into a cluster graph by deleting at most \(d^\ast ( v )\) edges incident to every \(v \in V ( G )\) and adding at most \(a^\ast ( v )\) edges incident to every \(v \in V ( G )\). Results by C. Komusiewicz and J. Uhlmann [Discrete Appl. Math. 160, No. 15, 2259–2270 (2012; Zbl 1252.05178)] and Abu-Khzam [loc. cit.] provided a dichotomy of complexity (in P or NP-complete) of \(( a , d )\)-Cluster Editing for all pairs \(a\), \(d\) apart from \(a = d = 1 .\) Abu-Khzam [loc. cit.] conjectured that \(( 1 , 1 )\)-Cluster Editing is in P. We resolve Abu-Khzam’s conjecture in affirmative by (i) providing a series of five polynomial-time reductions to \(C_3\)-free and \(C_4\)-free graphs of maximum degree at most 3, and (ii) designing a polynomial-time algorithm for solving \(( 1 , 1 )\)-Cluster Editing on \(C_3\)-free and \(C_4\)-free graphs of maximum degree at most 3.

MSC:

05C85 Graph algorithms (graph-theoretic aspects)
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
68R10 Graph theory (including graph drawing) in computer science
68Q25 Analysis of algorithms and problem complexity

References:

[1] Abu-Khzam, Faisal N., On the complexity of multi-parameterized cluster editing, J. Discrete Algorithms, 45, 26-34 (2017) · Zbl 1419.68056
[2] Barr, Joseph R.; Shaw, Peter; Abu-Khzam, Faisal N.; Chen, Jikang, Combinatorial text classification: the effect of multi-parameterized correlation clustering, (First International Conference on Graph Computing. First International Conference on Graph Computing, GC 2019, Laguna Hills, CA, USA, September 25-27, 2019 (2019), IEEE), 29-36
[3] Barr, J. R.; Shaw, P.; Abu-Khzam, F. N.; Thatcher, T.; Yu, S., Vulnerability rating of source code with token embedding and combinatorial algorithms, Int. J. Semant. Comput., 14, 4, 501-516 (2020)
[4] Böcker, Sebastian, A golden ratio parameterized algorithm for cluster editing, J. Discrete Algorithms, 16, 79-89 (2012) · Zbl 1257.05164
[5] Böcker, Sebastian; Briesemeister, Sebastian; Bui, Quang Bao Anh; Truß, Anke, Going weighted: Parameterized algorithms for cluster editing, Theoret. Comput. Sci., 410, 52, 5467-5480 (2009) · Zbl 1178.68373
[6] Böcker, Sebastian; Briesemeister, Sebastian; Klau, Gunnar W., Exact algorithms for cluster editing: Evaluation and experiments, Algorithmica, 60, 2, 316-334 (2011) · Zbl 1215.68169
[7] Cai, Liming, Fixed-parameter tractability of graph modification problems for hereditary properties, Inform. Process. Lett., 58, 4, 171-176 (1996) · Zbl 0875.68702
[8] Cao, Yixin; Chen, Jianer, Cluster editing: Kernelization based on edge cuts, Algorithmica, 64, 1, 152-169 (2012) · Zbl 1253.68144
[9] Chen, Jianer; Meng, Jie, A \(2 k\) kernel for the cluster editing problem, J. Comput. System Sci., 78, 1, 211-220 (2012) · Zbl 1238.68062
[10] Gramm, J.; Guo, J.; Hüffner, F.; Niedermeier, R., Graph-modeled data clustering: exact algorithms for clique generation, Theory Comput. Syst., 38, 4, 373-392 (2005) · Zbl 1084.68117
[11] Guo, J., A more effective linear kernelization for cluster editing, Theoret. Comput. Sci., 410, 718-726 (2009) · Zbl 1162.68025
[12] Komusiewicz, Christian; Uhlmann, Johannes, Cluster editing with locally bounded modifications, Discrete Appl. Math., 160, 15, 2259-2270 (2012) · Zbl 1252.05178
[13] Krivanek, M.; Moravek, J., NP-hard problems in hierarchical-tree clustering, Acta Inform., 23, 3, 311-323 (1986) · Zbl 0644.68055
[14] Shamir, Ron; Sharan, Roded; Tsur, Dekel, Cluster graph modification problems, Discrete Appl. Math., 144, 1-2, 173-182 (2004) · Zbl 1068.68107
[15] Shaw, Peter; Barr, Joseph R.; Abu-Khzam, Faisal N., Anomaly detection via correlation clustering, (16th IEEE International Conference on Semantic Computing. 16th IEEE International Conference on Semantic Computing, ICSC 2022, Laguna Hills, CA, USA, January 26-28, 2022 (2022), IEEE), 307-313
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.