Algorithms for 2-club cluster deletion problems using automated generation of branching rules

In the 2-CLUB CLUSTER VERTEX DELETION (resp., 2-CLUB CLUSTER EDGE DELETION) problem the input is a graph G and an integer k, and the goal is to decide whether there is a set of at most k vertices (resp., edges) whose removal from G results in a graph in which the diameter of every connected component is at most 2. In this paper we give algorithms for 2-CLUB CLUSTER VERTEX DELETION and 2-CLUB CLUSTER EDGE DELETION whose running times are O*(3.104k) and O*(2.562k), respectively. Our algorithms were obtained using automated generation of branching rules. Our results improve the previous O*(3.303k)-time algorithm for 2-CLUB CLUSTER VERTEX DELETION [Liu et al., FAW-AAIM 2012] and the O*(2.695k)-time algorithm for 2-CLUB CLUSTER EDGE DELETION [Abu-Khzam et al., TCS 2023].

Automated summary

This paper proposes algorithms for 2-CLUB CLUSTER VERTEX DELETION and 2-CLUB CLUSTER EDGE DELETION problems. The algorithms have running times of O*(3.104k) and O*(2.562k) respectively, and were obtained using automated generation of branching rules. These results improve upon previous algorithms for the same problems.