(1,1)-cluster editing is polynomial-time solvable

DOI10.1016/J.DAM.2023.07.002MaRDI QIDQ6048436zbMATH OpenOpenAlexFDO

Authors G. Gutin, A. Yeo

Publication date 14 September 2023

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2210.07722

zbMATH Keywords

cluster editingpolynomial algorithm

Mathematics Subject Classification ID

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

Abstract: A graph $H$ is a clique graph if $H$ is a vertex-disjoin union of cliques. Abu-Khzam (2017) 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)ightarrow0,1,dots,a$ and $d^{\ast }:V(G)ightarrow0,1,dots,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 $vinV(G)$ and adding at most $a^{\ast }(v)$ edges incident to every $vinV(G)$. Results by Komusiewicz and Uhlmann (2012) and Abu-Khzam (2017) 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 (2017) conjectured that $(1,1)$-{Cluster Editing} is in P. We resolve Abu-Khzam's conjecture in affirmative by (i) providing a serious 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.

Recommendations

• A more effective linear kernelization for cluster editing
• A More Effective Linear Kernelization for Cluster Editing
• On the clique editing problem
• Alternative parameterizations for cluster editing
• Cluster editing with locally bounded modifications

Cites work

• A 2k kernel for the cluster editing problem
• A golden ratio parameterized algorithm for cluster editing
• A more effective linear kernelization for cluster editing
• Cluster editing with locally bounded modifications
• Cluster editing: kernelization based on edge cuts
• Cluster graph modification problems
• Exact algorithms for cluster editing: Evaluation and experiments
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Going weighted: parameterized algorithms for cluster editing
• Graph-modeled data clustering: Exact algorithms for clique generation
• NP-hard problems in hierarchical-tree clustering
• On the complexity of multi-parameterized cluster editing

Cited in

(1)

• Graph-Theoretic Concepts in Computer Science

This page was built for publication: \((1,1)\)-cluster editing is polynomial-time solvable

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6048436)