---
abstract: 'Finding large “cliquish” subgraphs is a central topic in graph mining and community detection. A popular clique relaxation are 2-clubs: instead of asking for subgraphs of diameter one (these are cliques), one asks for subgraphs of diameter at most two (these are 2-clubs). A drawback of the 2-club model is that it produces star-like hub-and-spoke structures as maximum-cardinality solutions. Hence, we study 2-clubs with the additional constraint to be well-connected. More specifically, we investigate the algorithmic complexity for three variants of well-connected 2-clubs, all established in the literature: robust, hereditary, and “connected” 2-clubs. Finding these more cohesive 2-clubs is NP-hard; nevertheless, we develop an exact combinatorial algorithm, extensively using efficient data reduction rules. Besides several theoretical insights we provide a number of empirical results based on an engineered implementation of our exact algorithm. In particular, the algorithm significantly outperforms existing algorithms on almost all (sparse) real-world graphs we considered.'
author:
- 'Christian Komusiewicz$^{1,}$[^1]'
- André Nichterlein$^2$
- Rolf Niedermeier$^2$
- Marten Picker $^2$
bibliography:
- 'robust-two-club.bib'
date: |
    $^1$ Fachbereich Mathematik und Informatik, Philipps-Universität Marburg, Germany,\
    $^2$ Algorithmics and Computational Complexity, Faculty IV, TU Berlin, Germany,\
    `komusiewicz@informatik.uni-marburg.de {andre.nichterlein,rolf.niedermeier}@tu-berlin.de`
title: 'Exact Algorithms for Finding Well-Connected 2-Clubs in Real-World Graphs: Theory and Experiments[^2]'
---

Introduction {#sec:intro}
============

The $s$-club model, introduced by @mokken, is a well-established mathematical model for community mining in graphs [@For10]. An important special case is the 2-club model. In the corresponding algorithmic problem, the task is to compute a largest 2-club, that is, a maximum-cardinality vertex subset inducing a subgraph of diameter at most two. As a community model, 2-clubs have the drawback that they often form hub-and-spoke structures, that is, they often consist of one vertex that is adjacent to all other vertices of the community plus only few additional edges. Indeed, previous experimental work revealed that most maximum-cardinality 2-clubs in real-world graphs have exactly this hub-and-spoke structure and are thus fairly sparse [@hartung_experiments]. This is essentially the opposite of cliques which provide a subgraph model with maximal (edge) density. In this sense, standard 2-clubs are far away from being cliquish. The drawback of cliques, however, is that they are too demanding with respect to density in order to be meaningful in many applications based on mining cohesive subgraphs [@PYB13; @Kom16]. Hence, we study three 2-club models that exclude the low degree of connectivity that 2-clubs may have while still providing meaningful community abstractions.

#### Three 2-Club Models {#three-2-club-models .unnumbered}

In the classic 2-club model, one relaxes the clique demand by allowing that not all vertices of the community are adjacent but that they may also have distance two or, equivalently, that every vertex pair is either adjacent or has a common neighbor. The problem with this simple relaxation is that there may be only one vertex which is the common neighbor of all nonadjacent vertices. Hence, removing this vertex may destroy connectivity of the 2-club. Next, we describe three “well-connected” variants of 2-clubs that have been proposed in the literature [@PYB13; @VB12]; these three variants will be the central subjects of our studies.

In the first variant of well-connected 2-clubs, one demands that every pair of adjacent vertices has $t-1$ common neighbors and every pair of nonadjacent vertices has $t$ common neighbors.

\[def:robust\] A vertex set $S \subseteq V$ is a *$t$-robust 2-club* in a graph $G=(V,E)$ if any pair of vertices in $S$ is connected in $G[S]$ by $t$ internally vertex-disjoint paths of length at most two.

In the second variant, one demands that the deletion of few vertices does not destroy the 2-club property.

\[def:t-her\] A vertex set $S \subseteq V$ is a *$t$-hereditary 2-club* in a graph $G=(V,E)$ if $G[S\setminus U]$ is a 2-club for all $U\subset S$ where $|U|\le t$.

In the third variant, one only demands that the deletion of few vertices does not destroy connectivity.

\[def:t-conn\] A vertex set $S \subseteq V$ is a *$t$-connected 2-club* in a graph $G=(V,E)$ if it is a 2-club and $G[S]$ is $t$-connected, that is, $|S|>t$ and $G[S\setminus U]$ is connected for all $U\subseteq S$ where $|U|< t$.

Observe the difference of one in the sizes of the sets $U$ in \[def:t-her,def:t-conn\]. Refer to for a comparison of the three variants of well-connected 2-clubs.

\(a) at (0,0); (b) at (0,1); in [1,1,2,2,3,3]{}[ (ai) at ($ (b)!2cm!330-\i*60:(a) $) \[vert\] [i[$u_\x$]{}]{}; ]{} iin [1,3,5]{}[ in [2,4,6]{}[ (ai) – (a); ]{} ]{} = \[color=black,opacity=.15,line cap=round, line join=round, line width=20pt\] (a1.center) – (a6.center) – (a5.center) – (a4.center); (a1.center) – (a2.center) – (a3.center) – (a4.center); (a1.center) – (a4.center);

\(a) at (0,0); (b) at (0,1); in [1,1,2,2,3,3]{}[ (ai) at ($ (b)!2cm!330-\i*60:(a) $) \[vert\] [i[$u_\x$]{}]{}; ]{} iin [1,3,5]{}[ in [2,4,6]{}[ (ai) – (a); ]{} ]{} = \[color=black,opacity=.15,line cap=round, line join=round, line width=20pt\] (a1.center) – (a2.center) – (a3.center); (a1.center) – (a4.center) – (a3.center); (a1.center) – (a6.center) – (a3.center);

Assuming 2-club sizes $|S|\geq t+2$, it is easy to see that a $t$-robust 2-club is a $(t-1)$-hereditary 2-club which again is a $t$-connected 2-club. Clearly, for all three models, fulfilling the connectivity demands for some $t$ implies that they are also fulfilled for all $t'\le t$. Hence, the size of maximum-cardinality 2-clubs is nonincreasing with increasing $t$.

Our three central computational problems, formulated as decision problems (which is more suitable for statements on computational complexity), are defined as follows.

> <span style="font-variant:small-caps;">$t$-Robust / $t$-Hereditary / $t$-Connected 2-Club</span>\
> **Input:** An undirected graph $G = (V,E)$ and nonnegative integers $t$ and $k$.\
> **Question:** Does $G$ contain a $t$-robust / $t$-hereditary / $t$-connected 2-club of size at least $k$?

For brevity, when making general statements holding for all three variants, then we refer to them as $t$-well-connected 2-clubs.

#### Related Work {#sec:related .unnumbered}

Dense subgraph discovery or mining cohesive subgraphs is an active field in graph mining research [@LRJA10; @PYB13; @Kom16]. Algorithms, complexity studies, and experiments for finding $s$-clubs and in particular 2-clubs play a significant role in this context [@BB17; @bourjolly_exact; @BS17; @carvalho; @chang; @GHKR14; @hartung_experiments; @hartung_structural; @MB12; @schaefer2012; @VB12; @YPB17]. @VB12 introduced and motivated the concept of $t$-robustness and performed experiments for $t=2$ and $t=3$, showing that the predicted communities for these settings are much larger than maximum cliques. @PYB13 discussed several further variants of $s$-clubs. For $t$-connected 2-clubs, the special case $t=2$ demands that the $2$-club is biconnected. This case was studied by @YPB17 who presented a branch-and-bound and a branch-and-cut algorithm for the problem of finding biconnected 2-clubs. Moreover, @YPB17 showed that the problem of finding a largest biconnected $2$-club is NP-hard.

Finally, @CA17 studied a variant of $s$-clubs where each vertex is demanded to be part of at least one triangle.

There is a large body of previous work that considers the standard 2-club model. In particular, several algorithmic approaches (heuristics, exact algorithms) have been proposed and examined for the NP-hard computational task [@bourjolly_exact] to find maximum-cardinality 2-clubs [@bourjolly_exact; @bourjolly_heuristics; @BS17; @chang; @hartung_experiments; @MB12; @schaefer2012].

Of particular importance to our work is an exact algorithm for <span style="font-variant:small-caps;">2-Club</span> that uses the following branching: If the graph contains two vertices $u$ and $v$ that have distance at least three, then branch into the two cases to remove $u$ or $v$ from $G$. This algorithm was first proposed by @bourjolly_exact. Later, it was shown that this branching gives a fixed-parameter algorithm for the parameter $|V|-k$ with running time $O(2^{|V|-k}nm)$ [@schaefer2012] and an algorithm with running time $O(\alpha^n)$ where $\alpha<1.62$ is the golden ratio [@chang]. A combination of this branching algorithm with data reduction and pruning rules achieves the so far best performance on random networks and on sparse real-world networks [@hartung_experiments].

#### Our Contributions {#sec:results .unnumbered}

On a conceptual level, we provide an alternative characterization of $t$-hereditary 2-clubs (see \[lem:hereditary-characterization\]). Moreover, we present a “unifying view” on all three considered models based on “compatible vertices” (\[def:compatible\]).

On the level of algorithm theory, to the best of our knowledge we provide the first (formal) NP-hardness proofs for [<span style="font-variant:small-caps;">$t$-Robust $2$-Club</span>]{}and [<span style="font-variant:small-caps;">$t$-Hereditary $2$-Club</span>]{} for all $t\geq 1$. The corresponding reduction also yields an exponential running time lower bound based on the Strong Exponential Time Hypothesis (SETH). Moreover, we generalize the NP-hardness result for [<span style="font-variant:small-caps;">$t$-Connected $2$-Club</span>]{}due to @YPB17 by showing NP-hardness for all $t\geq 1$ even when restricted to split graphs. On the positive side, we generalize the above-mentioned fixed-parameter algorithm for <span style="font-variant:small-caps;">2-Club</span> parameterized by $|V|-k$ [@bourjolly_exact; @chang; @hartung_experiments; @schaefer2012], to obtain a fixed-parameter algorithm for all three problem variants.

On an algorithm engineering and empirical level, under heavy use of efficient and effective data reduction rules and using the above-indicated “unified view” on the three problem variants, we develop an implementation of our fixed-parameter algorithm that outperforms existing implementations on almost all (large and sparse) real-world graphs we experimented with. Only for random graphs we are clearly beaten by previous implementations.

Preliminaries {#sec:prelim}
=============

We only consider simple undirected graphs $G=(V,E)$ where $V$ is the vertex set and $E\subseteq \{\{u,v\}\mid u,v\in V\}$ is the edge set. Throughout this work, we use $n:= |V|$ and $m:= |E|$ to denote the number of vertices and the number of edges in the input graph $G$. A *subgraph* $(V', E')$ of a graph $G = (V, E)$ is a graph with $V' \subseteq V$ and $E' \subseteq E$ such that all edges in $E'$ are between vertices in $V'$, i.e. a graph derived from $G$ by deleting vertices and edges. For a graph $G = (V, E)$ and a subset $S \subseteq V$ of vertices, $G[S]:=(S,\{\{u,v\}\in E\mid u,v\in S\})$ denotes the *subgraph induced by $S$*. For $v \in V$ we set $G-v := G[V\setminus \{v\}]$. For $F \subseteq E$ we set $G-F := (V, E \setminus F)$.

A *path* is a sequence of vertices such that no vertex occurs twice and any two successive vertices in the path are adjacent. The *length of a path* is the number of edges along it. The *distance* $d(u, v)$ between two vertices $u$ and $v$ is the length of a shortest path between these two vertices. If there is a path between two vertices, then these vertices are said to be *connected*, and *disconnected* otherwise. A graph is *connected* if every pair of its vertices is connected. A *connected component* of a graph is a maximal set of vertices which are pairwise connected. Unless stated otherwise, we assume that the input graphs are connected, as otherwise we can process each connected component separately. The *diameter* of a graph is the length of the longest shortest path in the graph, i.e. the maximum distance between any two vertices in the graph. The *open d-neighborhood* $N_{d}(v)$ of a vertex $v$ is the set of all vertices within distance $d$ of $v$ except $v$ itself. The *closed d-neighborhood* $N_{d}[v]$ is defined as $N_{d}[v] := N_{d}(v) \cup \{v\}$. We set $N(v) := N_1(v).$

The *vertex connectivity* of a graph is the minimum number of vertices that has to be removed to disconnect the graph or make it trivial; *edge connectivity* is defined the same way over edges. The *edge density* of a graph is $m / {{n}\choose{2}}$, that is, the fraction of present edges compared to the maximum possible number of edges in a graph of $n$ vertices. In the <span style="font-variant:small-caps;">Clique</span> problem we are given an undirected graph $G = (V,E)$ and an integer $k$, and we ask whether $G$ contains a clique of size $k$, that is, a set $S \subseteq V$ of size $k$ such that every pair of vertices in $S$ is adjacent. Somewhat abusing notation we will use the terms $t$-robust, $t$-hereditary, and $t$-connected 2-club to refer to both the vertex sets and the subgraphs induced by them.

Structural Properties of Well-Connected 2-Clubs {#sec:properties}
===============================================

Before studying the computational complexity of finding $t$-well-connected 2-clubs, we first derive some structural properties of the respective $t$-well-connected 2-club models. We begin with a simple characterization of $t$-hereditary 2-clubs.

\[lem:hereditary-characterization\] A vertex set $S \subseteq V$ is a $t$-hereditary 2-club in a graph $G=(V,E)$ if and only if each nonadjacent pair of vertices of $S$ has at least $t+1$ common neighbors in $G[S]$.

$(\Rightarrow)$ We show the contraposition of this direction. Thus, assume that there are two nonadjacent vertices $u$ and $v$ in $S$ that have at most $t$ common neighbors. Now let $U:=N(u)\cap N(v)$ and observe that $|U|\le t$ by our assumption. The set $S$ is not a 2-club in $G[V\setminus U]$ because $u$ and $v$ are nonadjacent and have no common neighbors. Hence, $S$ is not a $t$-hereditary 2-club.

$(\Leftarrow)$ Assume that every pair of nonadjacent vertices in $S$ has at least $t+1$ common neighbors. Now, let $U\subseteq V$ be any vertex set of size at most $t$. Consider the graph $G[V\setminus U]$. We show that $S$ is a 2-club in $G[V\setminus U]$. Let $u$ and $v$ be two vertices of $S\setminus U$. If $u$ and $v$ are adjacent, then the distance between them is one. Otherwise, the distance between them is two: $u$ and $v$ have at least $t+1$ common neighbors in $G$ and one of them is not contained in $U$.

With this lemma at hand, we can now define the three variants of well-connected 2-clubs based on a predicate over vertex pairs; these definitions are of central importance for specifying our algorithms.

\[def:compatible\] Two vertices $v$ and $w$ in a graph are called *compatible*

-   for $t$-robust 2-clubs if they are adjacent and have at least $t-1$ common neighbors, or if they have at least $t$ common neighbors,

-   for $t$-hereditary 2-clubs if they are adjacent or if they have at least $t+1$ common neighbors,

-   for $t$-connected 2-clubs if they are at distance at most two and are connected by at least $t$ internally vertex-disjoint paths.

Note that if there are two compatible vertices $u$ and $v$, then this does not necessarily mean that in a graph $G$ there is some $t$-well-connected 2-club $S$ containing both $u$ and $v$, see for an example.

in [1,2,3]{}[ (a) at (2\*,0) \[vert\] ; ]{} in [u,v]{}[ (bi) at (2\*i+ 1,1) \[vert\] [$\x$]{}; in [1,2,3]{}[ (a) – (bi); ]{} ]{}

\[def:robust,def:t-conn,def:t-her,def:compatible,lem:hereditary-characterization\] imply the following.

\[obs:comp-is-club\] A graph is a $t$-robust, $t$-hereditary, or $t$-connected 2-club if and only if every pair of vertices in $G$ is compatible.

immediately give the following relation between the three concepts. Observe that there is an offset of 1 in the correspondence between $t$-robust or $t$-connected 2-clubs and $t$-hereditary 2-clubs.

\[obs:model-relations\] A $t$-robust 2-club is a $(t-1)$-hereditary 2-club and a $t$-connected 2-club. A $t$-hereditary 2-club of size at least $t+2$ is a $(t+1)$-connected 2-club.

In \[fig:model-comparison\] in \[sec:intro\], we can already see that a complete bipartite $K_{t,t}$ is a $(t-1)$-hereditary 2-club but not even a $2$-robust 2-club. Moreover, \[fig:t-connected-but-not-2-robust\] depicts a $t$-connected 2-club that is neither a $2$-robust nor a $1$-hereditary 2-club. Thus, \[obs:model-relations\] lists all relations between the three $t$-well-connected 2-club models we study.

\(a) at (0,0); (b) at (0,1); iin [0,...,5]{}[ (ai) at ($ (b)!2cm!-\i*60+180:(a) $) \[draw,thick,inner sep=2pt,minimum size=5pt\] [$V_\nr$]{}; ]{} (c) at (b) \[circle,draw,thick,inner sep=2pt,minimum size=5pt\] [$u$]{}; iin [0,...,5]{}[ ; (ai) – (a); (ai) – (c); ]{}

\(a) at (0,0); (b) at (0,1); in [1,...,]{}[ iin [0,...,5]{}[ (ai) at ($ (b)!2cm!\i*60+\smallDeg*\r*2-\smallDeg-\smallDeg*\maxR:(a) $) \[circle,fill=black,inner sep=0pt,minimum size=5pt\] ; ]{} ]{} (c) at (b) \[circle,draw,thick,inner sep=2pt,minimum size=5pt\] [$u$]{}; iin [0,...,5]{}[ ; in [1,...,]{}[ in [1,...,]{}[ (ai) – (a); (ai) – (c); ]{} ]{} ]{}

In our implementation, we use data reduction rules that remove vertices of low degree. The rationale behind these rules is provided by the following observations.

\[obs:smallDegree\]

1.  Neither a $t$-robust 2-club nor a $t$-connected 2-club can contain a vertex of degree less than $t$.

2.  A $t$-hereditary 2-club $S$ containing a vertex of degree less than $t+1$ is a clique.

First, consider $t$-robust and $t$-connected 2-clubs. Let $S$ be a vertex set containing a vertex $u$ of degree less than $t$. The number of vertex-disjoint paths (of any length) between $u$ and any other vertex in $S$ is less than $t$ since $u$ has less than $t$ neighbors. Hence, $S$ is neither a $t$-robust 2-club nor a $t$-connected 2-club.

We now show the claim for $t$-hereditary 2-clubs. Let $S$ be a $t$-hereditary 2-club containing a vertex $u$ of degree less than $t+1$. It follows from \[def:compatible,obs:comp-is-club\] that $u$ is adjacent to all other vertices in $S$. Hence, $|S| \le t+1$ and all vertices in $S$ have also degree less than $t+1$. It follows from \[def:compatible,obs:comp-is-club\] that $S$ is a clique.

Thus, for $t$-connected and $t$-robust 2-clubs one may remove all vertices of degree less than $t$. Furthermore, to find $t$-hereditary 2-clubs containing vertices of degree less than $t+1$ it is sufficient to solve <span style="font-variant:small-caps;">Clique</span>:

\[cliquesGood\] Every clique is a $t$-hereditary 2-club for all values of $t$.

Clearly, a clique $K$ is a 2-club. Since $K$ does not contain any nonadjacent vertices, \[lem:hereditary-characterization\] implies that $K$ is a $t$-hereditary 2-club.

\[cliquesGood\] implies that the largest $t$-hereditary 2-club is at least as large as a maximum-cardinality clique. In contrast, for every graph there are values of $t$ such that the graph neither contains a $t$-robust 2-club nor a $t$-connected 2-club. For example a clique of $n$ vertices is not $n$-robust and also not $n$-connected. For $t=n-1$, where $n$ is the number of graph vertices, we always obtain the clique model as the following observation implies.

\[smallClubs\] A $t$-hereditary 2-club $S$ with at most $t+2$ vertices is a clique. A $t$-robust/$t$-connected 2-club $S$ with at most $t+1$ vertices is a clique of size $t+1$.

First consider a $t$-hereditary 2-club $S$ with at most $t+2$ vertices. For any pair of vertices of $S$, there are only $t$ further vertices in $S$ which potentially can be common neighbors for both. Therefore, by \[def:compatible\], any two vertices in $S$ can only be compatible if they are adjacent. Thus, $S$ is a clique.

For $t$-robust 2-club and $t$-connected 2-clubs the statement follows from \[obs:smallDegree\] and the fact that the maximum degree in a graph on $t+1$ vertices is at most $t$.

Complexity Classification and Exact Algorithms {#sec:param-comp}
==============================================

In this section, we show that all three $t$-well-connected 2-club detection problems are NP-complete for all fixed $t$. In the case of $t$-robust and $t$-hereditary 2-clubs, we observe that the NP-completeness also holds for graphs that share properties with scale-free networks. The NP-hardness of the problems motivates the development of fixed-parameter algorithms for them. Fixed-parameter algorithms are exact algorithms whose running time is polynomial in the input size but usually exponential in a problem-specific parameter [@Cyg15; @downeyfellows; @Nie06; @FG06]. We will describe such an algorithm for all three problems and show that, in the case of [<span style="font-variant:small-caps;">$t$-Robust $2$-Club</span>]{}and [<span style="font-variant:small-caps;">$t$-Hereditary $2$-Club</span>]{}, it is likely to be optimal with respect to worst-case running time. Subsequently, we will show how to solve all three problems by solving $O(n)$ smaller instances of the problem. This, together with the fixed-parameter algorithm, will serve as the basis for our implementation, providing an exact combinatorial algorithm for finding well-connected 2-clubs.

Hardness Results {#NPhard}
----------------

By a polynomial-time reduction from $2$-<span style="font-variant:small-caps;">Club</span>, we show, for all values of $t$, the NP-hardness of finding $t$-hereditary and $t$-robust 2-clubs.

\[NPc\] [<span style="font-variant:small-caps;">$t$-Robust $2$-Club</span>]{}is NP-complete for every $t\ge 1$. [<span style="font-variant:small-caps;">$t$-Hereditary $2$-Club</span>]{}is NP-complete for every $t\ge 0$.

Containment in NP is obvious. The NP-hardness of <span style="font-variant:small-caps;">$1$-Robust $2$-Club</span> and <span style="font-variant:small-caps;">$0$-Hereditary $2$-Club</span> is already known as these problems are exactly the 2-<span style="font-variant:small-caps;">Club</span> problem [@bourjolly_exact]. The NP-hardness of both problems for the remaining values of $t$ can be shown via simple polynomial-time reductions from the 2-<span style="font-variant:small-caps;">Club</span> problem, which was shown to be NP-complete by @bourjolly_exact.

For any 2-<span style="font-variant:small-caps;">Club</span> instance $(G, k)$ we construct an equivalent [<span style="font-variant:small-caps;">$t$-Hereditary $2$-Club</span>]{} instance $(G', k+t)$, $t > 0$, where $G' = (V', E')$ is obtained from $G$ by adding a set $V^*=\{v^{*}_{1}, \ldots , v^{*}_{t}\}$ of $t$ further vertices and making them adjacent to all vertices of $G$ and to each other. This can obviously be done in polynomial time. It remains to be shown that $G$ has a 2-club of size at least $k$ if and only if $G'$ has a $t$-hereditary 2-club of size at least $k+t$. First, consider a 2-club $S$ in $G$. Then, the set $S \cup V^{*}$ is a $t$-hereditary 2-club in $G'$: Only vertices in $S$ can be pairwise nonadjacent. Moreover, each pair of nonadjacent vertices in $S$ has at least one common neighbor in $S$ and $t$ common neighbors in $V^*$. Thus, by \[def:compatible,obs:comp-is-club\], $S \cup V^{*}$ is a $t$-hereditary 2-club. Conversely, consider a $t$-hereditary 2-club $S'$ of size at least $k+t$ in $G'$. Note that $|V^*| = t$ and thus, by , $S' \setminus V^*$ is a 2-club of size at least $k$ in $G$. For [<span style="font-variant:small-caps;">$t$-Robust $2$-Club</span>]{}, $t > 1$, we adapt the construction by adding to $G$ a set $V^*=\{v^{*}_{1}, \ldots , v^{*}_{t-1}\}$ of $t-1$ further vertices and making them adjacent to all vertices of $V\cup V^*$.

If $G$ has a 2-club $S$ of size at least $k$, then $S\cup V^*$ is a $t$-robust 2-club of size at least $k+{t-1}$ in $G'$: Every pair of vertices from $S$ is connected by at least $t$ internally vertex-disjoint paths of length two in $G'[S\cup V^*]$ since they have $t-1$ such paths via the vertices in $V^*$ and are either adjacent or have a common neighbor in $S$.

Conversely, let $S'$ be a $t$-robust 2-club of size at least $k+t-1$ in $G'$ and let $S:=S'\cap V$. Then, $S$ is a 2-club of size at least $k$ in $G$: Every pair of nonadjacent vertices in $S$ is connected by $t$ vertex-disjoint paths of length two in $G'[S']$. At least one of these paths contains only vertices from $S$ since $|S'\setminus S|\le t-1$. Hence, these nonadjacent vertices have a common neighbor in $S$.

Altogether we have polynomial-time reductions from 2-<span style="font-variant:small-caps;">Club</span> to [<span style="font-variant:small-caps;">$t$-Hereditary $2$-Club</span>]{}for every $t\ge 0$ and from 2-<span style="font-variant:small-caps;">Club</span> to [<span style="font-variant:small-caps;">$t$-Robust $2$-Club</span>]{}for every $t\ge 1$.

The above reduction leaves the graph almost unchanged and thus many NP-hardness results that were obtained for 2-<span style="font-variant:small-caps;">Club</span> transfer almost directly to [<span style="font-variant:small-caps;">$t$-Hereditary $2$-Club</span>]{}and [<span style="font-variant:small-caps;">$t$-Robust $2$-Club</span>]{}. We list here the hardness results for graphs with properties that are typical for certain real-world networks. For instance, the class of split graphs finds applications in social networks in the context of “core-periphery models” [@BE00].

The graph classes mentioned in the subsequent corollary are defined as follows. A graph $G=(V,E)$ is a *split graph* if $V$ can be partitioned into $V_1$ and $V_2$ such that $G[V_1]$ is a clique and $G[V_2]$ is an independent set. A graph has *domination number $1$* if there is a vertex that is adjacent to all other vertices. A graph $G$ has *degeneracy $d$* if every subgraph of $G$ contains a vertex of degree at most $d$.

\[structuralParam\] [<span style="font-variant:small-caps;">$t$-Hereditary $2$-Club</span>]{}and [<span style="font-variant:small-caps;">$t$-Robust $2$-Club</span>]{}are NP-complete for $t \ge 1$ on

1.  graphs with both diameter two and domination number one,\[item:diam\]

2.  connected graphs with average vertex degree at most $\alpha$, for all $\alpha > 2$,\[item:avg-deg\]

3.  graphs with degeneracy $6 + t$, and \[item:degen\]

4.  split graphs. \[item:split-graphs\]

Regarding \[item:diam\], note that the graph $G'$ constructed by the reduction in the proof of \[NPc\] has at least one vertex adjacent to all other vertices and thus diameter two and domination number one. Regarding \[item:avg-deg\], note that the statement is known for $1$-robust 2-clubs, that is, standard 2-clubs [@hartung_structural]. Thus, we discuss subsequently $t$-hereditary 2-clubs for $t\ge 1$ and $t$-robust 2-clubs for $t \ge 2$. We add a long path to the graph obtained by the construction in the proof of \[NPc\] and add an edge from one endpoint of the path to an arbitrary vertex in the original graph. This decreases the average degree to any constant arbitrarily close to 2. No vertex of the path can be contained in any $t$-hereditary ($t\ge 1$) or $t$-robust ($t \ge 2$) 2-club of size at least three. Since we can assume that the solution size $k$ is at least three, we obtain an equivalent instance with the desired average degree. This adjusted reduction shows NP-hardness for any average degree greater than two. Regarding \[item:degen\], note that 2-<span style="font-variant:small-caps;">Club</span> is NP-hard on graphs with degeneracy six [@hartung_structural]. Adding $t$ vertices that are adjacent to all other vertices increases the degeneracy by at most $t$, therefore [<span style="font-variant:small-caps;">$t$-Hereditary $2$-Club</span>]{}and [<span style="font-variant:small-caps;">$t$-Robust $2$-Club</span>]{}are NP-hard on graphs with degeneracy $6 + t$. Regarding \[item:split-graphs\], observe that if the graph $G$ in the 2-<span style="font-variant:small-caps;">Club</span> instance is a split graph, then also the graph $G'$ constructed by the reduction in the proof of \[NPc\] is a split graph. This implies the NP-hardness of [<span style="font-variant:small-caps;">$t$-Hereditary $2$-Club</span>]{}and [<span style="font-variant:small-caps;">$t$-Robust $2$-Club</span>]{}on split graphs since 2-<span style="font-variant:small-caps;">Club</span> remains NP-hard on split graphs [@asahiro].

[<span style="font-variant:small-caps;">$t$-Connected $2$-Club</span>]{}is known to be NP-hard for $t\le 2$ [@BBT05; @YPB17]; for the sake of completeness, we show hardness for all constant $t$. Observe in this context that the reduction in the proof of Theorem \[NPc\] does not work for [<span style="font-variant:small-caps;">$t$-Connected $2$-Club</span>]{}: Adding $t-1$ common neighbors for all vertices of $G$ results in a $t$-connected graph of diameter two.

[<span style="font-variant:small-caps;">$t$-Connected $2$-Club</span>]{}is NP-complete, even on split graphs, for all $t\ge 1$.

Containment in NP is obvious. To show NP-hardness, we use a known reduction from <span style="font-variant:small-caps;">Clique</span> to <span style="font-variant:small-caps;">2-Club</span> [@BBT05]. We assume, however, that in the <span style="font-variant:small-caps;">Clique</span> instance every vertex has at least $t$ neighbors; obviously, <span style="font-variant:small-caps;">Clique</span> remains NP-hard with this restriction. Given such an instance $(G=(V,E),k)$ of <span style="font-variant:small-caps;">Clique</span>, construct an instance $G'=(V',E')$ of [<span style="font-variant:small-caps;">$t$-Connected $2$-Club</span>]{}as follows. The vertex set $V'$ consists of $V$ and one vertex for each edge of $G$. More formally, $V':=V\cup V_E$ where $V_E:=\{v_e\mid e\in E\}$. Now construct the edge set $E'$: First, make $V_E$ a clique. Second, for each $v\in V$ and each edge $e$ that is incident with $v$ in $G$, add an edge between $v$ and $v_e$. The graph $G'$ is a split graph and can obviously be constructed in polynomial time. We conclude the proof by showing that $G$ has a clique of size at least $k$ if and only if $G'$ has a $t$-connected 2-club of size at least $k+|E|$.

Let $S$ be a clique in $G$. Then $S\cup V_E$ is a $t$-connected 2-club of size at least $k+|E|$ in $G'$: $t$-connectivity follows from the fact that, by the assumption on the minimum degree in $G$, each vertex of $S$ has $t$ neighbors in the large clique $V_E$. The 2-club property follows from the fact that each pair of vertices $u, v \in S$ has a common neighbor in $V_E$ since $u$ and $v$ are adjacent in $G$.

Conversely, consider a $t$-connected 2-club $S'$ of size at least $k+|E|$ in $G'$. Consider $S:=S'\cap V$. Clearly, $|S|\ge k$. Moreover, $S$ is a clique in $G$: every pair of vertices $u$ and $v$ in $S$ has a common neighbor in $G'$. This common neighbor represents an edge of $G$ that is incident with $u$ and $v$.

Fixed-Parameter Algorithm with Respect to the Dual Parameter n-k {#dualParam}
----------------------------------------------------------------

We now describe a fixed-parameter algorithm for all three problems which is the basis for our implementation. The general idea—branching on vertices that are incompatible—was introduced by @bourjolly_exact for <span style="font-variant:small-caps;">2-Club</span>. The analysis of the algorithm exploits the parameter $\ell:=n-k$, that is, the number of vertices not contained in a largest $t$-well-connected 2-club.

\[2tC-VD\] For $\ell := n-k$, [<span style="font-variant:small-caps;">$t$-Hereditary $2$-Club</span>]{}and [<span style="font-variant:small-caps;">$t$-Robust $2$-Club</span>]{}can be solved in $O(2^{\ell}\cdot nm)$ time and [<span style="font-variant:small-caps;">$t$-Connected $2$-Club</span>]{}can be solved in $O(2^{\ell}\cdot t^2nm)$ time.

The algorithm is a simple branching algorithm that, as long as two vertices are incompatible, branches into deleting either of them; see for a pseudocode. This procedure leads to a search tree with at most $2^{\ell}$ leaves. To determine in Line 3 whether the current graph already fulfills the desired property, we check whether there are any incompatible vertices in the graph. Thus, the only difference between the three algorithms is the definition of compatibility, that is, in Lines 3 and 5 we need different algorithms to find incompatible vertices.

For [<span style="font-variant:small-caps;">$t$-Robust $2$-Club</span>]{}and for [<span style="font-variant:small-caps;">$t$-Hereditary $2$-Club</span>]{}, we first count for each vertex pair the number of common neighbors. This can be done in $O(nm)$ time by considering for each vertex in $G$ each pair of neighbors. An incompatible pair can now be found in $O(n^2)$ time by considering each vertex pair and applying Definition \[def:compatible\].

For [<span style="font-variant:small-caps;">$t$-Connected $2$-Club</span>]{}, we first determine in $O(nm)$ time whether there is a vertex pair that has distance at least three in $G$. If yes, then the two vertices are nonadjacent. Otherwise, we apply the algorithm of Galil [@Gal80] that determines in $O(t^2nm)$ time whether the graph is $t$-connected or to find a pair of vertices $u$ and $v$ that are in different $t$-connected components if this is not the case.

We next prove that is likely to be asymptotically optimal for [<span style="font-variant:small-caps;">$t$-Robust $2$-Club</span>]{}and [<span style="font-variant:small-caps;">$t$-Hereditary $2$-Club</span>]{}by showing that there can be no algorithm with running time $(2 - \epsilon)^{\ell}\cdot n^{O(1)}$ for any $\epsilon > 0$ for $(2,t)$-<span style="font-variant:small-caps;">Club</span>, unless the so-called Strong Exponential Time Hypothesis (SETH) [@IPZ01] fails.[^3] The SETH postulates that <span style="font-variant:small-caps;">CNF-Sat</span>, the satisfiability problem for boolean formulas in conjunctive normal form, cannot be solved in time $(2 - \epsilon)^{N}\cdot |F|^{O(1)}$ for any $\epsilon > 0$, where $N$ is the number of variables in the given formula $F$ and $|F|$ is the formula size. The proof is based on the reduction described in the proof of and a similar known result for <span style="font-variant:small-caps;">2-Club</span> [@hartung_experiments].

\[2tC-VD-SETH\] If the Strong Exponential Time Hypothesis (SETH) holds, then [<span style="font-variant:small-caps;">$t$-Robust $2$-Club</span>]{}and [<span style="font-variant:small-caps;">$t$-Hereditary $2$-Club</span>]{}do not admit a $(2 - \epsilon)^{\ell}\cdot n^{O(1)}$-time algorithm for any $\epsilon > 0$.

The reduction presented in the proof of \[NPc\] transforms a <span style="font-variant:small-caps;">2-Club</span> instance $(G=(V,E),k)$ into a [<span style="font-variant:small-caps;">$t$-Robust $2$-Club</span>]{}or a [<span style="font-variant:small-caps;">$t$-Hereditary $2$-Club</span>]{}instance $(G'=(V',E'),k')$ where $|V|'=|V|+t-1$ and $k'=k+t-1$ or $|V|'=|V|+t$ and $k'=k+t$. Hence, the dual parameters $\ell=|V|-k$ and $\ell'=|V'|-k'$ are not changed by either reduction. Consequently, any algorithm solving [<span style="font-variant:small-caps;">$t$-Robust $2$-Club</span>]{}or [<span style="font-variant:small-caps;">$t$-Hereditary $2$-Club</span>]{}in $(2 - \epsilon)^{\ell}\cdot n^{O(1)}$ time for some $\epsilon>0$ implies an algorithm solving <span style="font-variant:small-caps;">$2$-Club</span> in this time. This is impossible if the SETH is true [@hartung_experiments].

As a final note, as shown by @chang for <span style="font-variant:small-caps;">2-Club</span>, \[alg:dual-param\] has a worst-case running time of $\alpha^{n} n^{O(1)}$, where $\alpha < 1.62$ is the golden ratio.

\[goldenratio\] [<span style="font-variant:small-caps;">$t$-Robust $2$-Club</span>]{}, [<span style="font-variant:small-caps;">$t$-Hereditary $2$-Club</span>]{}, and [<span style="font-variant:small-caps;">$t$-Connected $2$-Club</span>]{}can be solved in $O(1.62^{n})$ time.

Consider the search tree algorithm of . Whenever we branch over a pair of incompatible vertices $v$ and $w$, we can delete $v$ in one branch and fix $v$ (as contained in the sought solution) in the other branch. The justification for fixing $v$ is that the first branch already explores all possible solutions that do not contain $v$, therefore $v$ can be assumed to be in the solution in the second branch. For any fixed vertex, we delete all vertices that are incompatible with $v$. Thus, in the branch fixing $v$, we can delete $w$ and, possibly, some further vertices. Branching continues until either (a) the graph is $t$-well-connected 2-club or (b) all remaining vertices are fixed. In case (a) we found a solution and in case (b) we fixed two incompatible vertices, leading to a contradiction. Letting $j$ denote the number of nonfixed vertices in $G$, the recursion for the number of leaves in the search tree is $T(j)=T(j-1)+T(j-2)$ and initially $j=n$. This is the recurrence for Fibonacci numbers implying a search tree size of $O(\alpha^n)$ where $\alpha<1.62$.

Turing Kernelization {#maxdegree}
--------------------

In this section, we describe parameterized preprocessing rules for our three $t$-well-connected 2-club detection problems. Herein, the parameter is the maximum degree $\Delta$ of the input graph $G$. The idea of a “Turing kernelization” is to solve the original problem instance by solving polynomially many problem instances whose size is upper-bounded in the parameter value (cf. @Kra14). These problem instances are small if the parameter value is small. In our case, we need to solve $n$ problem instances, each consisting of $O(\Delta^2)$ vertices. An analogous result for 2-club was shown by @schaefer2012.

\[maxdegthm\] [<span style="font-variant:small-caps;">$t$-Robust $2$-Club</span>]{}, [<span style="font-variant:small-caps;">$t$-Hereditary $2$-Club</span>]{}, [<span style="font-variant:small-caps;">$t$-Connected $2$-Club</span>]{}can be solved by solving $O(n)$ instances of [<span style="font-variant:small-caps;">$t$-Robust $2$-Club</span>]{}, [<span style="font-variant:small-caps;">$t$-Hereditary $2$-Club</span>]{}, and [<span style="font-variant:small-caps;">$t$-Connected $2$-Club</span>]{}, respectively, where each instance contains at most $\Delta^{2}$ vertices.

By definition, every 2-club has diameter at most two and is therefore fully contained in the closed 2-neighborhood of each of its vertices in the original input graph. To find the largest $t$-well-connected 2-club in a graph $G$ it is now sufficient to search in each of the $n$ closed 2-neighborhoods of $G$ for a largest such 2-club and take the largest among all of them. In a graph with maximum degree $\Delta\ge 2$ the size of the closed 2-neighborhood of any vertex $v$ is upper-bounded by $\Delta^{2}$ as $v$ can have at most $\Delta$ neighbors which each can have at most $\Delta - 1$ other neighbors besides $v$.

While \[maxdegthm\] is simple to show, it has important practical implications. It allows us to decompose larger (and relatively sparse) graphs into a linear number of smaller graphs where the problem can be solved efficiently. The smaller individual graphs are called *Turing kernels*. This result has been used for 2-<span style="font-variant:small-caps;">Club</span>-implementations [@hartung_experiments] and we use it as well in our implementation as described in . As a corollary, we obtain the following running time bound employing the parameter $\Delta$. To this end, note that one can compute all Turing kernels in $O(n \Delta^2)$ time.

[<span style="font-variant:small-caps;">$t$-Robust $2$-Club</span>]{}, [<span style="font-variant:small-caps;">$t$-Hereditary $2$-Club</span>]{}, and [<span style="font-variant:small-caps;">$t$-Connected $2$-Club</span>]{}can be solved in $O(1.62^{\Delta^2}\cdot n)$ time on graphs with maximum degree $\Delta$.

Implemented Algorithm {#sec:Algorithm}
=====================

In this section we describe our implementation for solving all three extensions of the <span style="font-variant:small-caps;">2-Club</span> model. Recall that we use the term $t$-well-connected 2-clubs to make statements that hold for all three models. The pseudocode given in shows the general setup of the algorithm which includes the Turing kernelization (\[maxdegthm\]) and the search tree (\[2tC-VD\]) combined with data reduction rules inspired by @hartung_experiments.

$\ell \gets 0$; $S \gets \emptyset$ ()[$t = 1$]{}[$\ell \gets \Delta + 1$]{} $\mathcal{T} \gets $ Turing kernels sorted by size in nondecreasing order \[line:turingkernel\] (\[line:Turing-kernel-loop\])[Turing kernel $T \in \mathcal{T}$]{} [ Apply data reduction rules on $T$ ]{}

In addition, our algorithm uses data structures for maintaining compatibility information (see \[def:compatible\]) for all vertices. While the criterion for compatibility depends on the selected model, our algorithm mostly works with the compatibility information. Thus, the major difference between the three models within our algorithm is the test whether two vertices are compatible. For the $t$-robust 2-club and the $t$-hereditary 2-club model, the compatibility of two vertices depends on whether they are adjacent and how many common neighbors they have. It is thus relatively easy to maintain the compatibility information for these two models as deleting a vertex can only affect the compatibilities of its neighbors. For the $t$-connected 2-club model one needs to compute the number of (internally) vertex-disjoint paths to determine whether two vertices at distance at most two are compatible. To this end, we use a standard linear-time reduction to a maximum flow problem with unit capacities. To compute the maximum flow, we use the classic algorithm of Ford and Fulkerson [@FF56].

The Search Tree Method and Turing Kernelization {#sec:search-tree}
-----------------------------------------------

The first step of the algorithm is to utilize Turing kernelization based on our observations from . For each vertex $v$ of the original graph, we construct a Turing kernel consisting of the closed 2-neighborhood $N_{2}[v]$ of that vertex. We then run the search tree method described in on each of the generated Turing kernels. For each Turing kernel we initially mark the vertex $v$ from which we derived the kernel (marking means that we assume that $v$ is part of the $t$-well-connected 2-club). The marking is correct since every vertex is marked exactly once. Additionally, after solving the Turing kernel for $v$ we remove $v$ from the graph and from all subsequent Turing kernels because if $v$ is part of an optimal solution, then we have found this solution in the kernel for $v$. Also, we discard any Turing kernel not larger (in terms of number of vertices) than the current lower bound. The largest $t$-well-connected 2-club of the input graph then is simply the largest among the $t$-well-connected 2-clubs of each individual kernel.

As an initial lower bound, we use maximum degree plus one for $t = 1$ ($t=0$ in the case of $t$-hereditary 2-clubs). For $t \geq 2$, we set the initial lower bound to zero. This is because we know of no lower bounds which are easy to compute and sufficiently strong. Due to the absence of an initial lower bound, we check the individual kernels of the graph in order of nondecreasing size. The idea is to keep for all considered kernels the gap between the current solution size lower bound and the size of the currently considered kernel as small as possible, as this gap constitutes an upper bound on the depth of the search tree for any given kernel. To reduce overhead from re-evaluating the size of each kernel after every vertex deletion, we sort the kernels of the graph once at the beginning of the algorithm by the size of the 2-neighborhood of the respective vertices and stick to this order throughout the run of the algorithm, even though some kernels might become smaller than some of their predecessors due to vertex deletions. In our experiments we observed that this worked quite well in the sense that on instances where the algorithm needs more than a minute, less than 10% of the running time of our algorithm is spent on the branching.

Data Reduction Rules {#sec:reduction-rules}
--------------------

To further improve the search tree method, we exhaustively apply various data reduction rules to shrink the original graph as well as every Turing kernel. The data reduction rules we use are mostly generalizations of known data reduction rules for 2-<span style="font-variant:small-caps;">Club</span> [@hartung_experiments]. They are as follows:

If at any time two vertices are both marked and incompatible, then abort the branch.

Remove all vertices which are incompatible with any marked vertices.

The correctness of these two rules is obvious as a $t$-well-connected 2-club by definition cannot contain incompatible vertices.

Remove vertices of degree less than $t$ (less than $t+1$ for the $t$-hereditary $2$-club model). For $t = 1$ ($t=0$ for the $t$-hereditary $2$-club model) delete all vertices of degree one. If a marked vertex was deleted, then abort the branch.

This data reduction rule is not universally correct, so we need to make two exceptions.

First, deleting degree-one vertices for $t = 1$ ($t=0$ for the $t$-hereditary $2$-club model) is only correct when initializing the algorithm with the closed 1-neighborhood of the maximum degree vertex as initial solution. A 2-club containing a degree-one vertex can only consist of the closed 1-neighborhood of its neighbor. Hence, no solution better than the one obtained from the closed 1-neighborhood of the maximum degree vertex contains degree-one vertices.

Second, \[obs:smallDegree\] shows that for the $t$-hereditary 2-club model, deleting vertices of degree less than $t+1$ is only correct if the solution is not a clique. However, cliques of size at most $t$ are by definition $t$-hereditary 2-clubs. Thus, we first assume that the $t$-hereditary 2-club has size at least $t+1$ which allows us to apply the Low Degree Rule. If we do not find a $t$-hereditary 2-club under this assumption, then we use a standard <span style="font-variant:small-caps;">Clique</span> algorithm to find the largest clique and return it. The running time of the <span style="font-variant:small-caps;">Clique</span> algorithm is, if it is invoked at all, much lower than the running time for finding the $t$-hereditary 2-club of size at least $t+1$. We use the Low Degree Rule extensively on the whole graph as well as on every kernel individually, both initially and whenever the degree of a vertex falls below $t$ due to vertex deletions.

Remove vertices whose number of compatible vertices is lower than the current lower bound. If a marked vertex was deleted, then abort the branch.

The correctness of this data reduction rule follows from the fact that a $t$-well-connected 2-club containing some vertex $v$ can only contain vertices which are compatible with $v$. Thus, if $v$ has less compatibilities than the current lower bound, then no $t$-well-connected 2-club containing $v$ contains more vertices than the current lower bound.

Our next data reduction rule uses the notion of vertex cover. A *vertex cover* in a graph $G = (V,E)$ is a vertex subset $V' \subseteq V$ such that each edge in $E$ is incident with at least one vertex in $V'$.

Let $G = (V, E)$ be the current instance and let $G_{C} = (V, E')$ be the corresponding incompatibility graph, where $\{v, w\} \in E'$ if and only if $v$ and $w$ are incompatible. Compute a lower bound $b$ on the vertex cover size of $G_C$. If $|V|-b$ does not exceed our current lower bound for the solution size, then abort the branch.

The correctness of the Vertex Cover Rule follows from the observation that the size of a minimum vertex cover of $G_{C}$ is a lower bound on the number of vertices in $G$ that still must be deleted in order to obtain a $t$-well-connected 2-club. As a quickly-to-compute lower bound for the vertex cover size we use the size of a maximal matching. The Vertex Cover Rule (VCR) reduces the search space substantially, but it is costly in terms of running time. We therefore use the following observations to cut down the number of necessary applications of the VCR: Whenever we have created no new incompatibilities since the last application of the VCR, the last result of the VCR is still a valid lower bound for the required number of vertex deletions. Thus, we reuse the last lower bound $b$ on the vertex cover when applying the VCR rule. To further decrease the number of VCR applications, we remember the last vertex cover of the incompatibility graph and only count as new those incompatibilities which are not covered by this last vertex cover. If we have created $x$ new conflicts since the last application of the VCR, then a new application of the VCR will report at most $x$ further required deletions over the last result of the VCR. So if the last upper bound minus $x$ is not enough to trigger the VCR, then there is no need to check the VCR again.

If at any time two nonadjacent marked vertices have exactly $x$ common neighbors, then mark all of their neighbors which are not marked yet. Here, $x$ is:

-   $t$ for the $t$-robust 2-club model,

-   $t+1$ for the $t$-hereditary 2-club model, and

-   $1$ for the $t$-connected 2-club model.

The reason for having a much weaker bound for $t$-connected 2-clubs is that the $t$ paths connecting two compatible vertices can have length more than two: For example, consider a cycle $C_5$ on five vertices with exactly two nonadjacent vertices $u$ and $v$ being marked. In the cycle, $u$ and $v$ have exactly one common neighbor. However, the $C_5$ is a $2$-connected $2$-club. The graph shown in \[fig:t-connected-but-not-2-robust\] in \[sec:properties\] “generalizes” the $C_5$ example: The graph is a $t$-connected $2$-club is displayed where vertex pairs (e.g. a marked vertex in the set $V_1$ and a marked vertex in the set $V_4$) have only one common neighbor. Thus, if two nonadjacent marked vertices have at least two common neighbors, then one might still be able to delete one of the two vertices without destroying $t$-connectedness. We exhaustively apply all reduction rules except the Vertex Cover Rule on each constructed Turing kernel. We use the Vertex Cover Rule only during the branching to prune the search tree.

Data Structures {#ssec:data-structures}
---------------

To perform the data reduction rules quickly at all times, the following information about the current Turing kernel is held up-to-date. To this end, recall that the current Turing kernel is a vertex $v \in V$ together with its 2-neighborhood and that the Turing kernels are processed one after the other, see in .

#### Common Neighbor Matrix

A matrix storing for each pair of vertices in the current Turing kernel their number of common neighbors. This data structure is very important for the $t$-hereditary 2-club and $t$-robust 2-club model. However, also in the $t$-connected 2-club model it is useful to check in constant time whether two nonadjacent vertices have a common neighbor, that is, whether they are at distance at most two.

#### Incompatibility Graph

A graph over the same vertex set as in the Turing kernel where two vertices are adjacent if and only if the two vertices are incompatible. Hence, for each edge $\{v, w\}$ in this graph at least one of the two vertices $v$ or $w$ must be deleted in order to obtain a $t$-well-connected 2-club.

#### Compatibility Vector

A vector containing for each vertex $v$ of the current Turing kernel the number of vertices that are compatible with $v$. Among other things this vector allows a fast (linear in the number of vertices of the current Turing kernel) look-up of the vertex that is compatible with the fewest other vertices; this vertex is used as the next branching candidate. When looking for 2-clubs, the entries in the compatibility vector correspond to the size of the 2-neighborhood of the respective vertex.

The initialization of these data structures requires $O(m\Delta + n^{2})$ time for the $t$-hereditary 2-club model and $t$-robust 2-club model, where $n$ is the number of vertices in the kernel, $m$ is the number of edges in the kernel, and $\Delta$ is the maximum vertex degree in the kernel. For the $t$-connected 2-club model we implemented the classical maximum flow algorithm of Ford and Fulkerson [@FF56] to determine whether two vertices are compatible. Thus, for $t$-connected 2-clubs there is an additional $O(tm)$ running time factor giving an overall initialization time of $O(tn^{2}m)$.

We first initialize the common neighbor matrix with zero values and then for each vertex $v$ of the kernel increase the entry of each pair of neighbors of $v$ by one. Afterwards, for the $t$-hereditary 2-club model and the $t$-robust 2-club model, a single pass over the common neighbor matrix suffices to count the number of compatible vertices for each vertex and identifying every initial incompatibility. For the $t$-connected 2-club model, we run the maximum flow algorithm for every pair of vertices that are at distance at most two from each other. The initialization cost can be quite large for dense kernels with many vertices (more than 50% of the overall running time on large social networks), so we apply all data reduction rules we can use without this information first. If after this quick preprocessing the kernel has less vertices than the current lower bound, then we discard the kernel before the initialization of the data structures. To keep the information continuously up-to-date, for every vertex $v$ that is deleted, we do the following.

1.  Decrease the number of compatible vertices of all vertices not compatible with $v$ by one; this can be done in $O(n)$ time, where $n$ is the number of vertices in the current kernel.

2.  Decrease the common neighbor counter for all pairs of neighbors of $v$ by one; this can be done in $O(\deg(v)^{2})$ time, where $\deg(v)$ is the degree of $v$.

3.  Update the incompatibility graph:

    -   For $t$-robust 2-clubs and $t$-hereditary 2-clubs, we can quickly update the incompatibility graph while updating the common neighbor counter (see \[def:compatible\]).

    -   For $t$-connected 2-clubs, we run the maximum flow algorithm between every pair of vertices that were compatible before deleting $v$. If the two vertices have distance more than two, then we set them incompatible without running the maximum flow algorithm.

For $t$-robust 2-clubs and $t$-hereditary 2-clubs, this leads to an $O(n + \deg(v)^{2})$-time overhead for every deletion of a vertex $v$ to keep the information up-to-date. For $t$-connected 2-clubs, the overhead is in the worst case $O(tn^2m)$. Overall, the overhead is quite significant but enables us to perform our data reduction rules quickly and extensively whenever they apply and as soon as they apply.

Integer Linear Programming Formulation for the [<span style="font-variant:small-caps;">$t$-Hereditary $2$-Club</span>]{}Problem {#ssec:ilp}
-------------------------------------------------------------------------------------------------------------------------------

We want to utilize a state-of-the-art ILP solver (Gurobi) as benchmark for our algorithm on instances with $t \geq 2$. To this end, we now describe the ILP formulation for [<span style="font-variant:small-caps;">$t$-Hereditary $2$-Club</span>]{}which we will use in our performance tests in . Given a graph $G = (V,E)$ and an integer $t$, the [<span style="font-variant:small-caps;">$t$-Hereditary $2$-Club</span>]{}problem can be solved with the following ILP:

Introduce a 0/1-variable $x_{v}$ for each vertex $v$ of the graph $G$. Setting $x_{v} = 1$ indicates $v\in S$, where $S$ is the solution set of vertices, that is, a set of vertices constituting a maximum $t$-hereditary $2$-club. The ILP is $$\begin{aligned}
    \text{max } {} & {} \sum_{v \in V} x_v \\
    \text{s.\,t. } {} & {} (t+1) \cdot x_{u} + (t+1) \cdot x_{w} - \smashoperator{\sum_{v\in N(u) \cap N(w)}} x_{v} \leq (t+1) && \forall \{u,w\} \notin E, \\
    & x_v \in \{0,1\} && \forall v \in V.\end{aligned}$$ For each nonadjacent pair of vertices $u$ and $w$ we have a constraint enforcing to either take at most one of the two vertices $u$ and $w$ into the solution or add at least $t+1$ of their common neighbors, too. This formulation generalizes the ILP formulation for the 2-<span style="font-variant:small-caps;">Club</span> problem as first described by @bourjolly_exact and used several times afterwards [@BBT05; @carvalho; @BS17]. Furthermore, we remark that the ILP formulation of @VB12 for finding $t$-robust $2$-clubs is very similar.

Computational Experiments {#sec:experiments}
=========================

In this section, we provide an experimental evaluation of our implementation[^4] (see \[sec:Algorithm\]) on random graphs as well as on real-world graphs from the 10th DIMACS challenge [@Dim12]. Our implementation solves the optimization versions of the problems and finds $t$-well-connected 2-clubs of maximum size. We refer to our implementation in the following as `WCC` (well-connected 2-club). For the special case of solving the basic <span style="font-variant:small-caps;">2-Club</span> problem (see \[ssec:2-club\]), we compare `WCC` against the programs of @hartung_experiments[^5] (referred to as `HKN`) and [^6] (referred to as `CHLS`). Furthermore, in \[ssec:biconnected-club\] we also compare against two programs of @YPB17[^7] (one branch-and-bound algorithm, one ILP) for finding $2$-connected $2$-clubs. In \[ssec:2-t-club\] we analyze the performance of `WCC` for finding $t$-well-connected 2-clubs in social networks for $t \ge 1$. In all our experiments, we set the time limit to one hour. All time measurements include the time to read the input graph.

We ran all our experiments on an Intel(R) Xeon(R) CPU E5-1620 3.60GHz machine with 64GB main memory under the Debian GNU/Linux 7.0 operating system. Our implementation is in Java and runs under the OpenJDK runtime environment in version 1.7.0\_65. The C++ implementation of @YPB17 was compiled with g++ version 5.4.0.

Comparison with other <span style="font-variant:small-caps;">2-Club</span> Algorithms {#ssec:2-club}
-------------------------------------------------------------------------------------

We may use our implementation (`WCC`) in three ways to find 2-clubs: by looking for 1-robust 2-clubs, 0-hereditary 2-clubs, or 1-connected 2-clubs. We report the running times for the setting where we look for $0$-hereditary 2-clubs since this is faster than the other two settings. The setting where we look for $1$-connected 2-clubs is particularly slow since our implementation uses a maximum flow computation to verify that the graph is connected.

#### Random Graphs {#random-graphs .unnumbered}

As in previous experimental evaluations [@hartung_experiments; @chang], we use the random graph generator due to @gendreau where the density of the resulting graphs is controlled by two parameters, $0\le a\le b\le 1$, and the expected density is $(a+b)/2$.

The results on random graphs give a clear picture: As our algorithm is not designed for random graphs but large sparse real-world networks, the implementations of @hartung_experiments (`HKN`) and @chang (`CHLS`) are both significantly faster than ours. However, `WCC` still outperforms our `ILP`. summarizes the results for random graphs with expected density 0.15, which produces the hardest instances as already observed earlier [@bourjolly_exact; @hartung_experiments; @chang].

\[tab:random-2-club-summary\]

     $a$    $b$   $n$                `WCC`    `HKN`             `CHLS`                 `ILP`
  ------ ------ ----- -------------------- -------- ------------------ ---------------------
     0.0    0.3   140                 3.50     1.27               1.00                  3.61
                  150                 5.71     1.71               1.82                  4.48
                  160                 6.84     1.99               2.64                  5.03
    0.05   0.25   140                19.34     6.11               7.37                 38.67
                  150                39.54    11.98              18.00                 63.23
                  160                72.35    18.33              30.54                 95.04
     0.1    0.2   140                70.09    24.34              29.99                246.20
                  150               183.04    59.41              85.94      **605.76 \[2\]**
                  160               557.92   178.16             306.51    **1,115.38 \[9\]**
    0.15   0.15   140               105.68    39.85              48.62                612.50
                  150               322.70   118.77             168.91    **1,508.00 \[8\]**
                  160   **1,132.05 \[1\]**   384.38   **611.65 \[1\]**   **2,594.98 \[46\]**

  :  Results on random graphs of density 0.15. All time measurements are the average over 100 instances with the described parameters. All running times are given in seconds. If a running time is bold, then some of these 100 instances (the number is given in brackets) did not finish within the time limit of one hour and the respective instance is accounted with one hour in the average. Bold values are therefore just lower bounds on the real running times.

The algorithm `HKN` could solve all random instances within the time limit of one hour. Our algorithm `WCC` as well as the algorithm `CHLS` could solve all but one instance within this time limit. Both `WCC` and `CHLS` fail to solve the same instance, which `HKN` could solve in 2,571 seconds. The `ILP`, however, failed on 65 of the overall 1,200 instances.

On average, `WCC` is 3.1 times slower than `HKN` and 2.4 times slower than `CHLS`. If one considers the accumulated running times over all instances, then `WCC` is 3 times slower than `HKN` and 1.9 times slower than `CHLS`. Compared to the `ILP` on instances where it found a solution within the time limit, `WCC` is on average 2.4 times faster and considering the accumulated running times (with unsolved instances counted with one hour), `WCC` is at least 2.7 times faster.

The reason for this relatively weak performance of `WCC` is the extensive usage of data reduction rules. The algorithm tries to apply all data reduction rules, but on random data they seldom apply. To improve the performance on random graphs, improving the efficiency of the data reduction rules as well as investigating heuristic selection strategies concerning when to apply which rule could be a promising approach for improvements.

#### Real-World Graphs {#real-world-graphs .unnumbered}

We considered real-world graphs from the 10th DIMACS challenge [@Dim12]. We ran our algorithm on instances from the categories *Clustering* and *Walshaw’s Graph Partitioning Archive* [@Dim12]; this is a standard benchmark for graph clustering and community detection algorithms also used by @YPB17 to evaluate their implementation for finding biconnected 2-clubs. To test our algorithm on large scale social network graphs we ran it also on graphs from the *co-author and citation* category [@Dim12] and a graph () mined from DBLP[^8] in 2012.

shows our test set of graphs and overviews the results for the real-world graphs.

\[tab:real-world-club-summary\]

Similarly to the experiments on random graphs, `CHLS` was the fastest solver on small instances. This is probably due to the fact that `CHLS` is written in C (`WCC` and `HKN` are written in Java) and it uses an adjacency matrix as graph representation (`WCC` and `HKN` use adjacency lists). Due to the usage of an adjacency matrix to store the graph, `CHLS` could not store and thus not solve any large graph in the *Co-author* category.

`WCC` could solve all but one of the instances of the smaller graphs (less than 50,000 edges) within one second; the exception, namely , needed less than four seconds. On medium-size and large instances, `WCC` clearly outperformed the other algorithms. The only instance that `WCC` could not solve within one hour is the largest graph . A second run without time limit shows a running time of 1.8 hours for this instance; the second-best solver `HKN` needs 8.6 *days*. This good performance is mainly due to the extensive usage of data reduction rules—a feature that slows down our algorithm on random graphs.

Comparison with other <span style="font-variant:small-caps;">$2$-Connected 2-Club</span> Algorithms {#ssec:biconnected-club}
---------------------------------------------------------------------------------------------------

We considered the same real-world instances as in \[ssec:2-club\] to compare against the two implementations of @YPB17. Their first implementation, which we refer to as `BB`, is a combinatorial branch-and-bound algorithm with some lower bound heuristics. Their second implementation, which we refer to as `BC`, is a branch-and-cut algorithm that is based on an ILP formulation. The results of the three algorithms are shown in \[tab:biconnected\].

\[tab:biconnected\]

`WCC` solved 21 out of the 26 instances within the time limit of one hour and all but one of the smaller graphs with less than 50,000 edges within less than one minute. Only one instance, namely , could not be solved within one hour. Moreover, `WCC` solved two larger graphs with more than 800,000 edges within less than 10 minutes. As already discussed in , `WCC` is not as efficient for the $t$-connected 2-club model as for the other two models. In fact, a closer inspection of our implementation on the graph showed that more than 95% of the running time went into the maximum flow-based connectivity check. Herein, the reduction to the maximum flow instance, without the computation of the maximum flow itself, took more than half of the time. Although this reduction can be performed in linear time, it is applied very often after branching or after applying the data reduction rules.

`BB` solved 11 and `BC` solved 13 out of the 26 instances. Both of these solvers were faster on the smallest instances and on a few medium size instances. In fact, the smaller graph that `WCC` could not solve is solved by `BC` in around eight minutes. However, `WCC` solved three smaller graphs (, , ) with less than 10,000 edges in less than a second each and both `BB` and `BC` could not solve them in less than half an hour. Neither `BB` nor `BC` could solve any of the larger graphs with more than 800,000 edges. In fact, the ILP-based solver `BC` did not even finish writing all constraints within one hour for these large graphs.

Summarizing, `WCC` solved substantially more instances than `BB` and `BC`. Again, the good performance is mainly due to the extensive usage of data reduction rules. Furthermore, as one can see in the results for , if the data reductions are not effective enough, then `WCC` needs much more time to solve the instance.

We did not perform tests on random graphs since we expect that the outcome is similar as in \[ssec:2-club\]: `WCC` will be outperformed by `BB` and `BC`.

Evaluation for $t \ge 1$ {#ssec:2-t-club}
------------------------

Finally, we performed experiments for computing $t$-well-connected 2-clubs with $t \ge 1$. For these experiments, we compare the running times of `WCC` and `ILP`. Moreover, we compare our three well-connected 2-club models with each other. Herein, we compare $t$-robust 2-clubs and $t$-connected 2-clubs with $(t-1)$-hereditary 2-clubs. The reason is that the base case—2-clubs—is reached for different $t$-values: A 2-club is a $1$-robust 2-club, a $1$-connected 2-club, and a $0$-hereditary 2-club. Furthermore, one can see many similar solutions when comparing $t$-robust 2-clubs against $(t-1)$-hereditary 2-clubs. We ran our implementation with values for $t$ being 1, 2, 3, 4, 5, 7, 9, 10, 15, 20, 50, 100, and 1,000. The performance of our implementation varies for different values of $t$ but there seems to be no clear correlation between $t$ and the performance.

In our tests `WCC` clearly outperformed `ILP`. Furthermore, `ILP` could solve only small real-world graphs. Due to this one-sided result, we only discuss the results of `WCC`. We refer to for a complete list of the experiments on real-world graphs (including `ILP`). Comparing `WCC` on the three models, unsurprisingly, the results for $(t-1)$-hereditary 2-clubs and $t$-robust 2-clubs are very similar (see \[fig:time-diff-models\]).

table \[y=timeHereditary, x=t,col sep = semicolon\][compare-models.csv]{}; table \[y=timeRobust, x=t,col sep = semicolon\][compare-models.csv]{}; table \[y=timeConnected, x=t,col sep = semicolon\][compare-models.csv]{};

table \[y=timeHereditary, x=t,col sep = semicolon\][compare-models.csv]{}; table \[y=timeRobust, x=t,col sep = semicolon\][compare-models.csv]{}; table \[y=timeConnected, x=t,col sep = semicolon\][compare-models.csv]{};

table \[y=timeHereditary, x=t,col sep = semicolon\][compare-models.csv]{}; table \[y=timeRobust, x=t,col sep = semicolon\][compare-models.csv]{}; table \[y=timeConnected, x=t,col sep = semicolon\][compare-models.csv]{};

table \[y=timeHereditary, x=t,col sep = semicolon\][compare-models.csv]{}; table \[y=timeRobust, x=t,col sep = semicolon\][compare-models.csv]{}; table \[y=timeConnected, x=t,col sep = semicolon\][compare-models.csv]{};

In both variants, `WCC` solved the same 329 of the overall 338 instances within one hour. On average, the $t$-robust 2-club could be computed 5% faster. Probably, this is due to the fact that for computing $(t-1)$-hereditary 2-clubs we run a clique-algorithm if the $(t-1)$-hereditary 2-club has size at most $t$ (see \[smallClubs\]). Only in 20 of the 175 instances that contain a $t$-robust 2-club the maximum $(t-1)$-hereditary 2-club is larger than the maximum $t$-robust 2-club (see also \[fig:size-diff-models\]).

table \[y=sizeHereditary, x=t,col sep = semicolon\][compare-models.csv]{}; table \[y=sizeRobust, x=t,col sep = semicolon\][compare-models.csv]{}; table \[y=sizeConnected, x=t,col sep = semicolon\][compare-models.csv]{};

table \[y=sizeHereditary, x=t,col sep = semicolon\][compare-models.csv]{}; table \[y=sizeRobust, x=t,col sep = semicolon\][compare-models.csv]{}; table \[y=sizeConnected, x=t,col sep = semicolon\][compare-models.csv]{};

table \[y=sizeHereditary, x=t,col sep = semicolon\][compare-models.csv]{}; table \[y=sizeRobust, x=t,col sep = semicolon\][compare-models.csv]{}; table \[y=sizeConnected, x=t,col sep = semicolon\][compare-models.csv]{};

table \[y=sizeHereditary, x=t,col sep = semicolon\][compare-models.csv]{}; table \[y=sizeRobust, x=t,col sep = semicolon\][compare-models.csv]{}; table \[y=sizeConnected, x=t,col sep = semicolon\][compare-models.csv]{};

The largest relative difference in sizes (in cases where a $t$-robust 2-club exists) was observed in the graph where the largest $4$-robust 2-club has size six and the largest $3$-hereditary 2-club has size nine.

For , , , and , `WCC` finds the largest $(t-1)$-hereditary 2-club and the largest $t$-robust 2-club relatively quickly (always within three minutes). This is not the case for the two largest graphs and . While could be solved within one hour for all values of $t$ except 1 and 3, could not be solved for $t$ ranging from 2 to 10. However, experiments without time limit and with further statistics collected during all stages of the implementation solved all instances within two hours. Since computing and outputting these additional data affected the running time quite a lot, we did not include the measured running times in the appendix.

`WCC` found the largest $t$-connected 2-club on many instances (290 of the 338 instances were solved). While only one of the smaller graphs () caused trouble for `WCC`, `WCC` struggled on large graphs with more than 800,000 edges; only 39 of the 78 instances corresponding to these large graphs could be solved within the time limit of one hour. On the instances `WCC` could deal with it needed much more time than for finding the largest $t$-robust or $(t-1)$-hereditary 2-club (see also \[fig:time-diff-models\]). A good example here is the graph where finding the largest $9$-connected 2-club was more than 100 times slower than finding the largest $8$-hereditary 2-club.

#### Detailed Running Time Analysis for $(t-1)$-Hereditary and $t$-Robust 2-Club Model {#detailed-running-time-analysis-for-t-1-hereditary-and-t-robust-2-club-model .unnumbered}

A closer inspection of the graph shows that, for all $t > 1$, our implementation spent around 75% of the time for constructing the Turing kernels and initializing the data structures (common neighbor matrix, incompatibility graph, and compatibility vector; see \[sec:Algorithm\]). The rest of the time is spent mostly on applying the data reduction rules; for each value of $t$, less than 30 seconds were spent on the actual branching. For $t=1$, the maximum degree of 3,299 gives a lower bound of 3,300 for the solution, which in this case is the solution size. Thus, all but six Turing kernels can be dismissed due to too small size before initializing the data structures (see discussion in \[ssec:data-structures\]). This explains why the implementation was that much faster for $t=1$.

The graph is quite different. This can be seen for example in the solution size: For increasing $t$ the size of the solution decreases only slightly (see \[fig:size-diff-models\] bottom-right plot); this is in stark contrast to the graph. Furthermore, for $t=1$ on the graph, there were 3,175 Turing kernels that were all larger than the lower bound. The average number of vertices in these Turing kernels was 1,389; the maximum was 2,022, the minimum 1,189. Recall that our data structures involve square matrices (the common neighbor matrix) whose number of rows and columns is equal to the number of vertices in the respective Turing kernel. This explains why the initialization of these data structures was the bottleneck in our implementation.

Overall Conclusions from Experiments
------------------------------------

We demonstrated the effectiveness of our general search-tree approach to find $t$-well-connected 2-clubs in large sparse real-world networks. In particular, to the best of our knowledge, we provide the first results for large sparse social networks with more than a million edges. The key ingredients for our implementation are the extensive usage of Turing kernels and data reduction rules. For finding $t$-connected 2-clubs there is room for improving our implementation. To this end, the most obvious approach is to look for an efficient data structure that can quickly delete vertices and answer connectivity queries. Finding good lower bounds is another approach to speed up our implementation as we only use a lower bound for the base case of finding 2-clubs.

Our experiments also indicated that the common ILP formulations are not able to cope with the large graphs we consider. The reason is simply that creating all constraints is too time consuming.[^9] Combining Turing-kernelization and data reduction rules with ILPs using row generation and other sophisticated tricks might lead to a competitive program.

Outlook {#sec:outlook}
=======

We studied three established models for cohesive subgraphs, namely $t$-robust, $t$-hereditary, and $t$-connected 2-clubs. These are considered to overcome the typical hub-and-spoke structure in the solutions of classical 2-<span style="font-variant:small-caps;">Club</span> problem. We presented theoretical findings for these models which provided the basis for our implementation of an exact algorithm for the problems. Our experiments demonstrate the efficiency of the presented algorithm on large sparse real-world graphs.

We conclude with some challenges for future research:

-   Our algorithmic result with respect to maximum degree (see ) does not fully explain the success of our implementation on our data set as the parameter value is too large (see \[tab:graphs\]). Moreover, we have NP-hardness even if the smaller parameters average degree and degeneracy are constant (see ). Thus, finding the “right” structure that explains the practically observed performance also in theory remains a task for future research.

-   It is open to study the polynomial-time approximability of the different $t$-well connected 2-club variants. Notably, <span style="font-variant:small-caps;">2-Club</span> has a factor-$O(n^{1/2})$ approximation algorithm and is NP-hard to approximate within a factor of $O(n^{1/2-\varepsilon})$ [@asahiro].

-   An extension of the algorithmic approach to 3-clubs and beyond is another challenge. @AC14 presented an ILP formulation for $t$-robust $3$-clubs and @VB12 presented an ILP formulation for a relaxation of $t$-robust $s$-clubs with $s>2$. Solving the relaxed problems turned out to be computationally very hard; we are not aware of experimental evaluations of the exact formulation for $t$-robust $3$-clubs.

-   @VPBP14 studied a variation of $t$-robust 2-clubs (called $\gamma$-relative-robust 2-clubs) where essentially the constant $t$ is replaced by a function in the size of the club. Our algorithms do not work for this variant since we always assume that at most one of two incompatible vertices (see \[def:compatible\] in \[sec:properties\]) can be in a $t$-well-connected 2-club. This assumption does not hold for $\gamma$-relative-robust 2-clubs. Extending our work to this model remains a task for future work.

-   The combination of efficient data reduction rules with mathematical programming techniques may lead to further accelerations in finding $t$-well-connected 2-clubs.

#### Acknowledgment {#acknowledgment .unnumbered}

We are grateful to four anonymous reviewers of *EJOR* for their careful and constructive feedback. We thank Oleksandra Yezerska, Foad Mahdavi Pajouh and Sergiy Butenko [@YPB17] for providing us with their source code of their programs.

Full Experimental Results for $t \ge 1$ {#sec:appendix}
=======================================

[^1]: CK was partially supported by the DFG, project MAGZ (KO 3669/4-1).

[^2]: Parts of this work are based on the last author’s master thesis [@Pic15]. Work started when all authors were with TU Berlin.

[^3]: The SETH is a well-accepted hypothesis in computational complexity theory and is used in several other lower-bound results [@LMS11].

[^4]: Available from <http://fpt.akt.tu-berlin.de/software/well-connected-2-club/wc2club.jar>.

[^5]: Available from <http://fpt.akt.tu-berlin.de/two_club/>.

[^6]: Available from <https://sites.google.com/site/kdynamicneighborhoodproject/>.

[^7]: @YPB17 sent us the code of their two programs.

[^8]: <http://dblp.uni-trier.de/faq/Am+I+allowed+to+crawl+the+dblp+website.html>

[^9]: To the best of our knowledge, ILP formulations for <span style="font-variant:small-caps;">2-Club</span> and its variants have at least $n^2-m$ constraints [@BS17; @YPB17; @VB12]. Even for the smallest graph from the *co-author and citation* category [@Dim12], this amounts to more than $5.2 \cdot 10^{10}$ constraints which, on the hardware we used, could not be generated within one hour.
