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 simple fixed-parameter algorithm solves the problem in O ⁎ (3 k) , and a decade-old algorithm improved this running to O ⁎ (2.74 k) 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 3 k barrier is presented in this paper, with a running time in O ⁎ (2.692 k). This also improves the previously claimed running time. [ABSTRACT FROM AUTHOR]