An improved fixed-parameter algorithm for 2-Club Cluster Edge Deletion

A 2-club is a graph of diameter at most two. In the decision version of the 2-Club Cluster Edge Deletion problem, an undirected graph G is given along with an integer k≥0 as parameter, and the question is whether G can be transformed into a disjoint union of 2-clubs by deleting at most k edges. A si...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2023-05, Vol.958, p.113864, Article 113864
Main Authors: Abu-Khzam, Faisal N., Makarem, Norma, Shehab, Maryam
Format: Article
Language:English
Subjects:
2-Club Cluster Edge Deletion
Cluster Editing
Correlation clustering
Fixed-parameter tractability
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A 2-club is a graph of diameter at most two. In the decision version of the 2-Club Cluster Edge Deletion problem, an undirected graph G is given along with an integer k≥0 as parameter, and the question is whether G can be transformed into a disjoint union of 2-clubs by deleting at most k edges. A simple fixed-parameter algorithm solves the problem in O⁎(3k), and a decade-old algorithm improved this running to O⁎(2.74k) time via a more sophisticated case analysis. Unfortunately, this latter algorithm is shown to have a flawed branching scenario. A fixed-parameter algorithm that breaks the 3k barrier is presented in this paper, with a running time in O⁎(2.692k). This also improves the previously claimed running time.
ISSN:0304-3975
DOI:10.1016/j.tcs.2023.113864