We study the parameterized complexity of the -Club Cluster Edge Deletion problem: Given a graph and two integers ≥ 2 and ≥ 1, is it possible to remove at most edges from such that each connected component of the resulting graph has diameter at most ? This problem is known to be NP-hard already when = 2. We prove that it admits a fixed-parameter tractable algorithm when parameterized by and the treewidth of the input graph.
which each pair of vertices is at distance at most ≥ 2 in the cluster. (Note that a 1-club is
in fact a clique.) We remark that defining clusters as -clubs proved to be efective in several
application scenarios such as social network analysis and bioinformatics [
Based on the above discussion, we know that it is unlikely that -Club Cluster Edge Deletion lies is FPT when parameterized by , whereas the complexity of the problem parameterized by + is open to the best of our knowledge. In this paper, we instead focus on those scenarios in which the solution size (measured by ) is large, and we still aim for tractable problems based on alternative parameterizations. In this respect, treewidth is a central parameter in the parameterized complexity analysis (see [20, 21]). We prove that -Club Cluster Edge Deletion lies in FPT when parameterized by + tw, where tw is an upper bound for the treewidth of the input graph.
Theorem 1 Let be an -vertex graph of treewidth at most tw. There is an algorithm that solves the -Club Cluster Edge Deletion problem on in (22(tw2 log ) · ) time.
From the technical viewpoint, the main crux of our approach lies in the definition of sufifciently small records that allow to keep track of the distances between pairs of vertices in a (partial) -club. With such records at hand, we then apply a standard DP algorithm over a tree decomposition of the input graph, which still requires a nontrivial amount of technicalities in order to update the records. Our records have similarities, but also several key diferences, with those used in a technique presented by Dondi and Lafond in [22, Thm. 14], which solves a related problem for the restricted case = 2.
For space constraints many technicalities are omitted and we only sketch the proof of Theorem 1. See [23] for the full version of the paper.
Preliminaries and notation. For any ∈ Z+, we use [] as shorthand for the set {1, 2, . . . , }. Let = (, ) be a graph. For any ⊂ , we denote by [ ] the subgraph of induced by the vertices of . The neighborhood of a vertex of is defined as () = { : ∈ }. Given two vertices , ∈ , the distance in between and , denoted by (, ), is the number of edges in any shortest path between and in . The diameter of is the maximum distance in between any two of its vertices. An -club of , with ≥ 1, is a subset ⊆ such that the diameter of [ ] is at most . A partition of is a collection of subsets = {}∈[] such that: (a) ⋃︀
=1 = , and (b) ∩ = ∅ for each , ∈ [] with ̸= .
We denote by the set of all edges of such that , ∈ , for some ∈ []. We study the following problem. -Club Cluster Edge Deletion Input: = (, ), ≥ 1, ≥ 2.
Output: A partition = {}∈[] of such that is an -club for each ∈ [], and | ∖ | ≤ .
In what follows, for a graph = (, ), the pair ( , ) denotes a nice tree-decomposition, such that = {}∈[ℓ] is a collection of subsets of vertices of , called bags, and is a tree whose nodes are in one-to-one correspondence with the elements of . We point the reader to [24, 25] for the required background.
The proof is based on a DP algorithm over a nice tree-decomposition. We first describe the records to be stored at each bag, and we then sketch the algorithm.
Definition of the records. Let = (, ) be an -vertex graph and let ( , ) be a nice tree-decomposition of of width tw. For each ∈ [ℓ], let be the subtree of rooted at the bag ∈ and let = (, ) be the subgraph of induced by the vertices that belong to at least one bag of . A subset of vertices ⊆ is a potential -club, and we let = ∩ and int() = ∖ .
The first item of the record is a table that stores the pairwise distances of the vertices in . Namely, let () be a table having one row and one column for each vertex in , and such that:
⎧⎪0, ()[, ] = ⎨
if = ⎪ ⎩∞, [](, ), if 1 ≤ [](, ) ≤ otherwise.
The second item is a table that stores the distance between pairs of vertices such that one is in and the other is in int(). Two vertices , ′ in int() are equivalent with respect to , if for each vertex ∈ , then either 1 ≤ [](, ) = [](′, ) ≤ , or [](, ) > and [](′, ) > . Namely, let () be a table having one column for each vertex ∈ , and one row for each equivalence class with respect to , denoted by [] . We have: ()[, ] =
∞, {︃[](, ), if 1 ≤ [](, ) ≤ otherwise.
The third (and last) item of the record represents the key diference to extend the result in [ 22] to ≥ 2. Suppose that is a subset of an -club ′ of and that there exist two vertices , ′ ∈ int() whose distance in [] is larger than . Then, any path between and ′ not containing two vertices in has length larger than . Hence, since is a separator of , we have to consider paths in between and ′ going through some pair of vertices in . We formalize this observation. Let , ∈ int() be two vertices such that [](, ) > . A request for , denoted by , is a table having one row and one column for each vertex in . Namely, for each , ∈ , if there exists 2 ≤ ≤ − 2 such that connecting and with a path of length makes the distance between and to be at most , then [, ] = , while [, ] = ⋆ otherwise. Observe that if there exist two requests and ′′ such that [, ] = ′′ [, ] for each pair , ∈ , then and ′ are equivalent with respect to (i.e., , ′ ∈ [] ), and the same holds for and ′. Thus, we avoid storing duplicated requests and we denote by () the set containing all distinct requests for .
If a potential -club is such that = ∅ (recall that ⊆ ), then we call it complete. Consider a partitioning of into potential -clubs and let = {, | ∈ []} be the potential -clubs in that are not complete. Let = {, | ∈ []}, = {(,) | ∈ []}, ℋ = {(,) | ∈ []}, and = {(,) | ∈ []}. A solution of is a tdhuiespntlicenectif=≤ ⟨.̸=T, wo,sℋ,oolru,tio,n̸=s⟩.H,=eorre⟨ℋi,̸=saℋn,iℋn,toe,rger,,c̸=al⟩leadned.dOgbe-sce=oruvn⟨ettehr,aet,qiufa,lℋtoan|,d∖,ar(e⟩naro)e|t, distinct but < , then it sufices to consider only .
Lemma 1 For a bag , there exist (22(tw2 log ) ) distinct solutions.
Sketch of the algorithm. Let be the current bag visited by the algorithm. We compute the set of solutions for based on the solutions computed for its child or children. If the resulting set of solutions is empty, the algorithm halts and returns a negative answer. The running time of the algorithm follows from Lemma 1. We only describe the case in which is an introduce bag. The cases in which is a leaf, a forget, or a join bag are omitted in this extended abstract. is an introduce bag. Let = ∖ {} be the child of . The algorithm exhaustively extends each solution of as follows. It first generates at most new partitions by placing in each ′ ∈ . Also, it generates a partition in which forms a new potential -club = = {}. Consider one of the new partitions generated by the algorithm. In order to build the corresponding new solution for , we distinguish the following two cases. Case A ( = {}). () is trivially defined, () and () are empty. Case B ( = ′ ∪ {}). The next observation immediately follows from the fact that = ′ ∪ {} and int() = int(′).
Observation 1 Suppose that there exist , ∈ ′ such that [′](, ) > [](, ), then any shortest path between and in [] contains vertex . – Computing () from (′).
1. We add a new row and a new column for vertex . 2. For each vertex ∈ ′, let = min∈[]() (′)[, ], and note that = 0 if edge belongs to []. Clearly, it holds that ()[, ] = {︃∞, if ∈ {, ∞}
1 + , otherwise. 3. By Observation 1, for each pair , ∈ ′, the corresponding value of () can be updated as follows:
()[, ] = min{(′)[, ], ()[, ] + ()[, ]}. – Computing () from (′).
1. We add a new column for vertex . 2. For each equivalence class []′ , let = min∈[]() (′)[, ]. Since there is no edge such that ∈ int(), it follows that ()[, ] = {︃∞, if ∈ {, ∞}
1 + , otherwise. 3. By Observation 1, for each pair of vertices ∈ int(′) and ∈ ′, the corresponding value of () can be updated as follows:
()[, ] = min{(′)[, ], ()[, ] + ()[, ]}. – Computing () from (′). Note that the addition of cannot lead to new requests but it may actually yield the update of some request in (′).
1. For each request in (′), we verify whether, as a consequence of the introduction of , there exists a cell [, ] such that ()[, ] ≤ [, ]. If such a cell exists, we say that is fulfilled . We add to () if and only if is not fulfilled. 2. If is not fulfilled, before adding it to (), we update it as follows: a) We add a row and a column for . b) For each pair , ∈ ′, we compute
= min{(()[, ] + ()[, ], ()[, ] + ()[, ]}.
Observe that + ()[, ] > , otherwise the request would have been fulfilled before. c) By definition of request, we have [, ] = − , if < − 1, and [, ] = ⋆, otherwise.
Finally, in both Case A and Case B, we observe that, in order to obtain the edge-counter of the new solution, needs to be increased by the number of edges incident to whose other end-vertex is in but not in . If the resulting edge-counter is greater than , the solution is discarded.
We have shown that the -Club Cluster Edge Deletion problem parameterized by + tw (where tw bounds the treewidth of the input graph) belongs to FPT. On the other hand, we know that the problem parameterized by alone is paraNP-hard. It remains open the complexity of -Club Cluster Edge Deletion parameterized by tw alone. We conclude by remarking that our approach can be slightly modified to solve a related problem, namely -Club Cluster Vertex Deletion, in which we seek for vertices whose removal yields a set of disjoint -clubs. [16] R. Mokken, S. Laan, Close communication and 2-clubs in corporate networks: Europe 2010,
Social Network Analysis and Mining 6 (2016). doi:10.1007/s13278-016-0345-x. [17] H. Liu, P. Zhang, D. Zhu, On editing graphs into 2-club clusters, in: FAW-AAIM, volume 7285 of LNCS, Springer, 2012, pp. 235–246. doi:10.1007/978-3-642-29700-7\_22. [18] F. N. Abu-Khzam, N. Makarem, M. Shehab, An improved fixed-parameter algorithm for 2-club cluster edge deletion, CoRR abs/2107.01133 (2021). URL: https://arxiv.org/abs/2107. 01133. [19] N. Misra, F. Panolan, S. Saurabh, Subexponential algorithm for d-cluster edge deletion: Exception or rule?, J. Comput. Syst. Sci. 113 (2020) 150–162. doi:10.1016/j.jcss.2020. 05.008. [20] R. G. Downey, M. R. Fellows, Parameterized Complexity, Monographs in Computer Science,
Springer, 1999. [21] N. Robertson, P. D. Seymour, Graph minors. II. Algorithmic aspects of tree-width, J.
Algorithms 7 (1986) 309–322. [22] R. Dondi, M. Lafond, On the tractability of covering a graph with 2-clubs, in: L. A.
Gasieniec, J. Jansson, C. Levcopoulos (Eds.), FCT 2019, volume 11651 of LNCS, Springer, 2019, pp. 243–257. doi:10.1007/978-3-030-25027-0\_17. [23] F. Montecchiani, G. Ortali, T. Piselli, A. Tappini, On the parameterized complexity of the -club cluster edge deletion problem, CoRR abs/2205.10834 (2022). doi:10.48550/arXiv. 2205.10834. [24] H. L. Bodlaender, T. Kloks, Eficient and constructive algorithms for the pathwidth and treewidth of graphs, J. Algorithms 21 (1996) 358–402. doi:10.1006/jagm.1996.0049. [25] T. Kloks, Treewidth, Computations and Approximations, volume 842 of LNCS, Springer, 1994.