We study the parameterized complexity of the s-CLUB CLUSTER EDGE DELETION (s-CLUB CLUSTER VERTEX DELETION) problem: Given a graph G and two integers s &gt; 2 and k &gt; 1, is it possible to remove at most k edges (vertices) from G such that each connected component of the resulting graph has diameter at most s? Both s-CLUB CLUSTER EDGE DELETION and s -CLUB CLUSTER VERTEX DELETION problems are known to be NP-hard already when s = 2. We prove that they admit a fixed-parameter tractable algorithm when parameterized by s and the treewidth of the input graph. The proof is based on a unified algorithm that solves the more general problem in which both edges and vertices can be removed from the input graph to obtain a set of disjoint components with bounded diameter. Our approach can also be exploited to solve a related problem, namely s-CLUB COVER, which asks whether it is possible to cover the vertices of a graph with at most d different s-clubs, for some fixed d &gt; 1 and s &gt; 2.&amp; COPY; 2023 Elsevier B.V. All rights reserved.

### On the parameterized complexity of s-club cluster deletion problems

#### Abstract

We study the parameterized complexity of the s-CLUB CLUSTER EDGE DELETION (s-CLUB CLUSTER VERTEX DELETION) problem: Given a graph G and two integers s > 2 and k > 1, is it possible to remove at most k edges (vertices) from G such that each connected component of the resulting graph has diameter at most s? Both s-CLUB CLUSTER EDGE DELETION and s -CLUB CLUSTER VERTEX DELETION problems are known to be NP-hard already when s = 2. We prove that they admit a fixed-parameter tractable algorithm when parameterized by s and the treewidth of the input graph. The proof is based on a unified algorithm that solves the more general problem in which both edges and vertices can be removed from the input graph to obtain a set of disjoint components with bounded diameter. Our approach can also be exploited to solve a related problem, namely s-CLUB COVER, which asks whether it is possible to cover the vertices of a graph with at most d different s-clubs, for some fixed d > 1 and s > 2.& COPY; 2023 Elsevier B.V. All rights reserved.
##### Scheda breve Scheda completa Scheda completa (DC)
2023
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: `https://hdl.handle.net/11391/1566916`
• ND
• 1
• 0