Misra, NeeldharaNeeldharaMisraPanolan, FahadFahadPanolanSaurabh, SaketSaketSaurabh2025-08-312025-08-312020-11-0110.1016/j.jcss.2020.05.0082-s2.0-85085270454http://repository.iitgn.ac.in/handle/IITG2025/23947We study the question of finding a set of at most k edges, whose removal makes the input n-vertex graph a disjoint union of s-clubs (graphs of diameter s). Komusiewicz and Uhlmann [DAM 2012] showed that CLUSTER EDGE DELETION (i.e., for the case of 1-clubs (cliques)), cannot be solved in time 2^o(k)n^O(1) unless the Exponential Time Hypothesis (ETH) fails. But, Fomin et al. [JCSS 2014] showed that if the number of cliques in the output graph is restricted to d, then the problem (d-CLUSTER EDGE DELETION) can be solved in time O(2^O(dk)+m+n). We show that assuming ETH, there is no algorithm solving 2-CLUB CLUSTER EDGE DELETION in time 2^o(k)n^O(1). Further, we show that the same lower bound holds in the case of s-CLUB d-CLUSTER EDGE DELETION for any s≥2 and d≥2.trueCluster edge deletion | ETH-hardness | Parameterized subexponential time algorithms | s-ClubsArticle10902724150-162November 20209arJournal6WOS:000539435200008