דקל צור

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.104^k) and O^⁎(2.562^k), respectively. Our algorithms were obtained using automated generation of branching rules. Our results improve the previous O^⁎(3.303^k)-time algorithm for 2-CLUB CLUSTER VERTEX DELETION [Liu et al., FAW-AAIM 2012] and the O^⁎(2.695^k)-time algorithm for 2-CLUB CLUSTER EDGE DELETION [Abu-Khzam et al., TCS 2023].