HyperAIHyperAI

Command Palette

Search for a command to run...

(1,1)-Cluster Editing is Polynomial-time Solvable

Gregory Gutin; Anders Yeo

Abstract

A graph HHH is a clique graph if HHH is a vertex-disjoin union of cliques. Abu-Khzam (2017) introduced the (a,d)(a,d)(a,d)-{Cluster Editing} problem, where for fixed natural numbers a,da,da,d, given a graph GGG and vertex-weights a: V(G)0,1,,aa^:\ V(G)\rightarrow {0,1,\dots, a}a: V(G)0,1,,a and d: V(G)0,1,,dd^{}:\ V(G)\rightarrow {0,1,\dots, d}d: V(G)0,1,,d, we are to decide whether GGG can be turned into a cluster graph by deleting at most d(v)d^(v)d(v) edges incident to every vV(G)v\in V(G)vV(G) and adding at most a(v)a^(v)a(v) edges incident to every vV(G)v\in V(G)vV(G). Results by Komusiewicz and Uhlmann (2012) and Abu-Khzam (2017) provided a dichotomy of complexity (in P or NP-complete) of (a,d)(a,d)(a,d)-{Cluster Editing} for all pairs a,da,da,d apart from a=d=1.a=d=1.a=d=1. Abu-Khzam (2017) conjectured that (1,1)(1,1)(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 C3C_3C3-free and C4C_4C4-free graphs of maximum degree at most 3, and (ii) designing a polynomial-time algorithm for solving (1,1)(1,1)(1,1)-{Cluster Editing} on C3C_3C3-free and C4C_4C4-free graphs of maximum degree at most 3.


Build AI with AI

From idea to launch — accelerate your AI development with free AI co-coding, out-of-the-box environment and best price of GPUs.

AI Co-coding
Ready-to-use GPUs
Best Pricing

HyperAI Newsletters

Subscribe to our latest updates
We will deliver the latest updates of the week to your inbox at nine o'clock every Monday morning
Powered by MailChimp