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. The same result easily transfers to the case in which we can remove at most k vertices, rather than k edges, from G such that each connected component of the resulting graph has diameter at most s, namely to s-CLUB CLUSTER VERTEX DELETION.
On the Parameterized Complexity of s-club Cluster Deletion Problems
Montecchiani, F
;Ortali, G
;Piselli, T
;Tappini, A
2023
Abstract
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. The same result easily transfers to the case in which we can remove at most k vertices, rather than k edges, from G such that each connected component of the resulting graph has diameter at most s, namely to s-CLUB CLUSTER VERTEX DELETION.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
