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

DOI10.1016/J.TCS.2023.113864arXiv2107.01133OpenAlexW3178869403MaRDI QIDQ6038703FDOQ6038703

Authors: Faisal N. Abu-Khzam, Norma Makarem, Maryam Shehab 

Publication date: 2 May 2023

Published in: Theoretical Computer Science (Search for Journal in Brave)

Abstract: 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 $kgeq0$ 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 $mathcal{O}^{\ast }(3^k)$, and a decade-old algorithm was claimed to have an improved running time of $mathcal{O}^{\ast }(2.74^k)$ 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 $mathcal{O}^{\ast }(2.695^k)$.

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

Recommendations

• On Editing Graphs into 2-Club Clusters
• On the parameterized complexity of \(s\)-club cluster deletion problems
• Subexponential algorithm for \(d\)-cluster edge deletion: exception or rule?
• Parameterized Algorithmics and Computational Experiments for Finding 2-Clubs
• On 2-clubs in graph-based data clustering: theory and algorithm engineering

zbMATH Keywords

fixed-parameter tractabilitycorrelation clusteringcluster editing2-club cluster edge deletion

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Automated generation of search tree algorithms for hard graphs modification problems
• Cluster editing
• Cluster editing with locally bounded modifications
• Fixed-parameter algorithms for cluster vertex deletion
• Managing and mining graph data
• Cluster graph modification problems
• A more effective linear kernelization for cluster editing
• Title not available (Why is that?)
• The Cluster Editing Problem: Implementations and Experiments
• Exact algorithms for cluster editing: Evaluation and experiments
• Generalized graph clustering: recognizing \((p,q)\)-cluster graphs
• Cluster editing with vertex splitting
• On 2-clubs in graph-based data clustering: theory and algorithm engineering
• On Editing Graphs into 2-Club Clusters
• Subexponential algorithm for \(d\)-cluster edge deletion: exception or rule?
• On the complexity of multi-parameterized cluster editing

Cited In (3)

• Algorithms for 2-club cluster deletion problems using automated generation of branching rules
• On the parameterized complexity of s-club cluster deletion problems
• On the parameterized complexity of \(s\)-club cluster deletion problems

This page was built for publication: An improved fixed-parameter algorithm for 2-Club Cluster Edge Deletion

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