=Paper=
{{Paper
|id=Vol-3284/7682
|storemode=property
|title=On the Parametrized Complexity of the s-Club Cluster Edge Deletion Problem
|pdfUrl=https://ceur-ws.org/Vol-3284/7682.pdf
|volume=Vol-3284
|authors=Fabrizio Montecchiani,Giacomo Ortali,Tommaso Piselli,Alessandra Tappini
|dblpUrl=https://dblp.org/rec/conf/ictcs/MontecchianiOPT22
}}
==On the Parametrized Complexity of the s-Club Cluster Edge Deletion Problem==
<pdf width="1500px">https://ceur-ws.org/Vol-3284/7682.pdf</pdf>
<pre>
On the Parameterized Complexity of the 𝑠-Club
Cluster Edge Deletion Problem
(Short Paper)
Fabrizio Montecchiani, Giacomo Ortali* , Tommaso Piselli and Alessandra Tappini
Università degli Studi di Perugia, Italy


                                         Abstract
                                         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.

                                         Keywords
                                         𝑠-Club Cluster Edge Deletion, Parameterized Complexity, 𝑠-Club, Treewidth




1. Introduction
Graph clustering [1] is a classical task in data mining, with important applications in numerous
fields including computational biology [2], image processing [3], and machine learning [4]. A
prominent graph-theoretic formalization is Cluster Editing (also known as Correlation
Clustering): Given a graph 𝐺 and an integer 𝑘 as input, the goal is to find a sequence of 𝑘
operations, each of which can be an edge insertion or removal, such that the resulting graph is a
so-called cluster graph, i.e., each of its connected components is a clique. If we restrict the editing
operations to be edge removals only, then the problem is known as Cluster Edge Deletion.
Equivalently, we seek for a partition of the vertices of 𝐺 into cliques, such that the inter-
cluster edges (whose end-vertices belong to different cliques) are at most 𝑘. Unfortunately, both
Cluster Editing and Cluster Edge Deletion are well-known to be NP-complete [5, 6]. Indeed,
their parameterized complexity with respect to the natural parameter 𝑘 has been intensively
investigated; in particular, both problems are in FPT [7, 8], but do not allow subexponential-time
parameterized algorithms unless ETH fails [9, 6].
   In many applications, modelling clusters with cliques might be a severe limitation, for instance,
in presence of noise in the data collection process. Consequently, several notions of relaxed
cliques have been introduced and investigated [10, 11]. We focus on the concept of 𝑠-club, in

Proceedings of the 23rd Italian Conference on Theoretical Computer Science, Rome, Italy, September 7-9, 2022
*
 Corresponding author.
" fabrizio.montecchiani@unipg.it (F. Montecchiani); giacomo.ortali@unipg.it (G. Ortali);
tommaso.piselli@studenti.unipg.it (T. Piselli); alessandra.tappini@unipg.it (A. Tappini)
 0000-0002-0543-8912 (F. Montecchiani); 0000-0002-4481-698X (G. Ortali); 0000-0001-9192-2067 (A. Tappini)
                                       © 2022 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
    CEUR
    Workshop
    Proceedings
                  http://ceur-ws.org
                  ISSN 1613-0073
                                       CEUR Workshop Proceedings (CEUR-WS.org)
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 effective in several
application scenarios such as social network analysis and bioinformatics [12, 13, 14, 15, 16]. The
𝑠-Club Cluster Edge Deletion problem can be stated analogously as Cluster Edge Deletion
by replacing cliques with 𝑠-clubs (formal definitions are given later). Unfortunately, 𝑠-Club
Cluster Edge Deletion is NP-complete already for 𝑠 = 2 [17]. Also, 2-Club Cluster Edge
Deletion belongs to FPT parameterized by 𝑘 [18, 17], and it admits no subexponential-time
parameterized algorithm in 𝑘 [19]. More in general, for any 𝑠 ≥ 2, 𝑠-Club Cluster Edge
Deletion cannot be solved in time 2𝑜(𝑘) 𝑛𝑂(1) unless ETH fails [19].
   Based on the above discussion, we know that it is unlikely that 𝑠-Club Cluster Edge Dele-
tion 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
                                                            𝑂(tw2 log 𝑠)
the 𝑠-Club Cluster Edge Deletion problem on 𝐺 in 𝑂(22                      · 𝑛) time.
   From the technical viewpoint, the main crux of our approach lies in the definition of suf-
ficiently 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 differences,
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.


2. Sketch of the Proof of Theorem 1
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:

                                                        if 𝑎 = 𝑏
                                       ⎧
                                       ⎨0,
                                       ⎪
                      𝐷(𝜕𝐶)[𝑎, 𝑏] = 𝑑𝐺[𝐶] (𝑎, 𝑏), 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 difference 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
                                               𝑙             𝑖            𝑗,𝑖        𝑙                       𝑖
tuple 𝑆𝑖𝑙 = ⟨𝜕𝒞𝑖𝑙 , 𝒟𝑖𝑙 , ℋ𝑖𝑙 , 𝒬𝑙𝑖 , 𝑘𝑖𝑙 ⟩. Here 𝑘𝑖𝑙 is an integer, called edge-counter, equal to |𝐸𝑖 ∖𝒫𝑖𝑙 (𝐸𝑖 )|,
hence 𝑘𝑖𝑙 ≤ 𝑘. Two solutions 𝑆𝑖𝑙 = ⟨𝜕𝒞𝑖𝑙 , 𝒟𝑖𝑙 , ℋ𝑖𝑙 , 𝒬𝑙𝑖 , 𝑘𝑖𝑙 ⟩ and 𝑆𝑖𝑔 = ⟨𝜕𝒞𝑖𝑔 , 𝒟𝑖𝑔 , ℋ𝑖𝑔 , 𝒬𝑔𝑖 , 𝑘𝑖𝑔 ⟩ are
distinct if 𝜕𝒞𝑖𝑙 ̸= 𝜕𝒞𝑖𝑔 , or 𝒟𝑖𝑙 ̸= 𝒟𝑖𝑔 , or ℋ𝑖𝑙 ̸= ℋ𝑖𝑔 , or 𝒬𝑙𝑖 ̸= 𝒬𝑔𝑖 . Observe that if 𝑆𝑖𝑙 and 𝑆𝑖𝑔 are not
distinct but 𝑘𝑖𝑙 < 𝑘𝑖𝑔 , then it suffices to consider only 𝑆𝑖𝑙 .

                                                 𝑂(tw2 log 𝑠)
Lemma 1 For a bag 𝑋𝑖 , there exist 𝑂(22                         ) 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.
3. Discussion and Open Problems
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.


References
 [1] S. E. Schaeffer, Graph clustering, Comput. Sci. Rev. 1 (2007) 27–64. doi:10.1016/j.
     cosrev.2007.05.001.
 [2] A. Ben-Dor, R. Shamir, Z. Yakhini, Clustering gene expression patterns, J. Comput. Biol. 6
     (1999) 281–297. doi:10.1089/106652799318274.
 [3] Z. Wu, R. M. Leahy, An optimal graph theoretic approach to data clustering: Theory and
     its application to image segmentation, IEEE Trans. Pattern Anal. Mach. Intell. 15 (1993)
     1101–1113. doi:10.1109/34.244673.
 [4] N. Bansal, A. Blum, S. Chawla, Correlation clustering, Mach. Learn. 56 (2004) 89–113.
     doi:10.1023/B:MACH.0000033116.57574.95.
 [5] R. Shamir, R. Sharan, D. Tsur, Cluster graph modification problems, Discret. Appl. Math.
     144 (2004) 173–182. doi:10.1016/j.dam.2004.01.007.
 [6] C. Komusiewicz, J. Uhlmann, Cluster editing with locally bounded modifications, Discret.
     Appl. Math. 160 (2012) 2259–2270. doi:10.1016/j.dam.2012.05.019.
 [7] S. Böcker, A golden ratio parameterized algorithm for cluster editing, J. Discrete Algorithms
     16 (2012) 79–89. doi:10.1016/j.jda.2012.04.005.
 [8] J. Chen, J. Meng, A 2k kernel for the cluster editing problem, J. Comput. Syst. Sci. 78 (2012)
     211–220. doi:10.1016/j.jcss.2011.04.001.
 [9] F. V. Fomin, S. Kratsch, M. Pilipczuk, M. Pilipczuk, Y. Villanger, Tight bounds for parame-
     terized complexity of cluster editing with a small number of clusters, J. Comput. Syst. Sci.
     80 (2014) 1430–1447. doi:10.1016/j.jcss.2014.04.015.
[10] B. Balasundaram, F. M. Pajouh, Graph Theoretic Clique Relaxations and Applications,
     Springer New York, 2013, pp. 1559–1598. doi:10.1007/978-1-4419-7997-1\_9.
[11] C. Komusiewicz, Multivariate algorithmics for finding cohesive subnetworks, Algorithms
     9 (2016) 21. doi:10.3390/a9010021.
[12] R. Alba, A graph-theoretic definition of a sociometric clique, Journal of Mathematical
     Sociology 3 (1973) 113–126. doi:10.1080/0022250X.1973.9989826.
[13] B. Balasundaram, S. Butenko, S. Trukhanov, Novel approaches for analyzing biological
     networks, J. Comb. Optim. 10 (2005) 23–39. doi:10.1007/s10878-005-1857-x.
[14] s. Laan, M. Marx, R. Mokken, Close communities in social networks: Boroughs and 2-clubs,
     SSRN Electronic Journal (2015). doi:10.2139/ssrn.2686127.
[15] R. Mokken, Cliques, clubs and clans, Quality & Quantity: International Journal of
     Methodology 13 (1979) 161–173. doi:10.1007/BF00139635.
[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, Efficient 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.

</pre>