
arXiv: 2107.01133
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\geq 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 $\mathcal{O}^*(3^k)$, and a decade-old algorithm was claimed to have an improved running time of $\mathcal{O}^*(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}^*(2.695^k)$.
FOS: Computer and information sciences, Parameterized complexity, tractability and kernelization, Computational Complexity (cs.CC), correlation clustering, Computer Science - Computational Complexity, Graph theory (including graph drawing) in computer science, Graph algorithms (graph-theoretic aspects), cluster editing, fixed-parameter tractability, Computer Science - Data Structures and Algorithms, 2-club cluster edge deletion, Data Structures and Algorithms (cs.DS)
FOS: Computer and information sciences, Parameterized complexity, tractability and kernelization, Computational Complexity (cs.CC), correlation clustering, Computer Science - Computational Complexity, Graph theory (including graph drawing) in computer science, Graph algorithms (graph-theoretic aspects), cluster editing, fixed-parameter tractability, Computer Science - Data Structures and Algorithms, 2-club cluster edge deletion, Data Structures and Algorithms (cs.DS)
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 2 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
