2021/07/02 by Faisal N. Abu-Khzam, Abu-Khzam, Faisal N., Norma Makarem +3
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Interconnection Networks and Systems #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2107.01133
openalex publication_date 2021/07/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A 2-club is a graph of diameter at most two. In the decision version of the parametrized \sc 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 was claimed to have an improved running time of O^*(2.74k) via a sophisticated case analysis. Unfortunately, this latter algorithm suffers from a flawed branching scenario. In this paper, an improved fixed-parameter algorithm is presented with a running time in O^*(2.695k).