On the Parameterized Complexity of the s-Club Cluster Edge Deletion Problem

05/22/2022

∙

by   Fabrizio Montecchiani, et al.

∙

0

∙

share

We study the parameterized complexity of the s-Club Cluster Edge Deletion problem: Given a graph G and two integers s ≥ 2 and k ≥ 1, is it possible to remove at most k edges from G such that each connected component of the resulting graph has diameter at most s? This problem is known to be NP-hard already when s = 2. We prove that it admits a fixed-parameter tractable algorithm when parameterized by s and the treewidth of the input graph.