HyperAIHyperAI

Command Palette

Search for a command to run...

6 months ago

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

Gregory Gutin; Anders Yeo

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

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.

Benchmarks

BenchmarkMethodologyMetrics
big-bench-machine-learning-on-38-cloudFb232
account and password : 100

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
Get Started

Hyper 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
(1,1)-Cluster Editing is Polynomial-time Solvable | Papers | HyperAI