11institutetext: Fachbereich Mathematik und Informatik, Philipps-Universität
Marburg,
Marburg, Germany
11email<EMAIL_ADDRESS>
# The Parameterized Complexity of $s$-Club with Triangle and Seed Constraints

Jaroslav Garvardt  Christian Komusiewicz  0000-0003-0829-7032 Frank Sommer
Supported by the Deutsche Forschungsgemeinschaft (DFG), project EAGR (KO
3669/6-1). 0000-0003-4034-525X

###### Abstract

The s-Club problem asks, for a given undirected graph $G$, whether $G$
contains a vertex set $S$ of size at least $k$ such that $G[S]$, the subgraph
of $G$ induced by $S$, has diameter at most $s$. We consider variants of
$s$-Club where one additionally demands that each vertex of $G[S]$ is
contained in at least $\ell$ triangles in $G[S]$, that $G[S]$ contains a
spanning subgraph $G^{\prime}$ such that each edge of $E(G^{\prime})$ is
contained in at least $\ell$ triangles in $G^{\prime}$, or that $S$ contains a
given set $W$ of seed vertices. We show that in general these variants are
W[1]-hard when parameterized by the solution size $k$, making them
significantly harder than the unconstrained $s$-Club problem. On the positive
side, we obtain some FPT algorithms for the case when $\ell=1$ and for the
case when $G[W]$, the graph induced by the set of seed vertices, is a clique.

##  1 Introduction

Finding cohesive subgroups in social or biological networks is a fundamental
task in network analysis. A classic formulation of cohesiveness is based on
the observation that cohesive groups have small diameter. This observation led
to the $s$-club model originally proposed by Mokken [15]. An _$s$ -club_ in a
graph $G=(V,E)$ is a set of vertices $S$ such that $G[S]$, the subgraph of $G$
induced by $S$, has diameter at most $s$. The 1-clubs are thus precisely the
cliques and the larger the value of $s$, the more the clique-defining
constraint of having diameter one is relaxed. In the $s$-Club problem we aim
to decide whether $G$ contains an $s$-club of size at least $k$.

A big drawback of $s$-clubs is that the largest $s$-clubs are often not very
cohesive with respect to other cohesiveness measures such as density or
minimum degree. This behavior is particularly pronounced for $s=2$: the
largest $2$-club in a graph is often the vertex $v$ of maximum degree together
with its neighbors [10]. To avoid these so-called hub-and-spoke structures, it
has been proposed to augment the $s$-club definition with additional
constraints [5, 14, 16, 18].

One of these augmented models, proposed by Carvalho and Almeide [5], asks that
every vertex is part of a triangle [5]. This property was later generalized to
the _vertex- $\ell$-triangle_ property, which asks that every vertex of $S$ is
in at least $\ell$ triangles in $G[S]$ [1].

Vertex Triangle $s$-Club

Input: |  An undirected graph $G$ = $(V,E)$, and two integers $k,\ell\geq 1$.
---|---
Question: |  Does $G$ contain an $s$-club $S$ of size at least $k$ that fulfills the vertex-$\ell$-triangle property?

The vertex-$\ell$-triangle constraint entails some desirable properties for
cohesive subgraphs. For example, in a vertex-$\ell$-triangle $s$-club, the
minimum degree is larger than $\sqrt{2\ell}$. However, some undesirable
behavior of hub-and-spoke structures remains. For example, the graph
consisting of two cliques of size $d+1$ that are connected via one edge is a
vertex-$\binom{d}{2}$-triangle 3-club but it can be made disconnected via one
edge deletion. Thus, vertex-$\ell$-triangle $s$-clubs are not robust with
respect to edge deletions.

To overcome this problem, we introduce a new model where we put triangle
constraints on the edges of the $s$-club instead of the vertices. More
precisely, we say that a vertex set $S$ of a graph $G$ fulfills the _edge-
$\ell$-triangle_ property if $G[S]$ contains a spanning subgraph
$G^{\prime}\coloneqq(S,E^{\prime})$ such that every edge in $E(G^{\prime})$ is
in at least $\ell$ triangles in $G^{\prime}$ and the diameter of $G^{\prime}$
is at most $s$. Next, we introduce the related problem.

Edge Triangle $s$-Club

Input: |  An undirected graph $G=(V,E)$, and two integers $k,\ell\geq 1$.
---|---
Question: |  Does $G$ contain a vertex set $S$ of size at least $k$ that fulfills the edge-$\ell$-triangle property?

Note that in this definition, the triangle and diameter constraints are
imposed on a spanning subgraph of $G[S]$. In contrast, for Vertex Triangle
$s$-Club, they are imposed directly on $G[S]$. The reason for this distinction
is that we would like to have properties that are closed under edge
insertions. Properties which are closed under edge insertions are also well-
motivated from an application point of view since adding a new connection
within a group should not destroy this group. If we would impose the triangle
constraint on the induced subgraph $G[S]$ instead, then an
edge-$\ell$-triangle $s$-club $S$ would not be robust to edge additions. For
example, consider a graph $G$ consisting of clique $C$ to which two vertices
$u$ and $v$ are attached in such a way that both $u$ and $v$ have exactly $2$
neighbors in $C$ which are distinct. The $V(G)$ is an edge-$1$-triangle
$3$-club, but other adding the edge $uv$, the edge $uv$ is contained in no
triangle and thus any edge-$1$-triangle $3$-club cannot contain both $u$ and
$v$.

Observe that every set that fulfills the edge-$\ell$-triangle property also
fulfills the vertex-$\ell$-triangle property. Also note that the converse is
not true: A vertex-$\ell$-triangle $s$-club is not necessarily also an
edge-$\ell$-triangle $s$-club. For this, consider the above mentioned graph
consisting of two cliques of size $d+1$ that are connected via one edge Then,
this graph is an vertex-$\binom{d}{2}$-triangle-$3$-club. But after deleting
$e$ the graph is disconnected. Moreover, each vertex $v\in S$ has at least
$\ell+1$ neighbors in $S$: Consider an arbitrary edge $uv$. Since $uv$ is in
at least $\ell$ triangles $\\{u,v,w_{1}\\},\ldots,\\{u,v,w_{\ell}\\}$ we thus
conclude that $u$ and $v$ have degree at least $\ell$. We can show an even
stronger statement: an edge-$\ell$-triangle $s$-club $S$ is robust against up
to $\ell$ edge deletions, as desired.

###### Proposition 1

Let $G=(V,E)$ be a graph and let $S$ be an edge-$\ell$-triangle $s$-club in
$G$. More precisely, let $G^{\prime}$ be a spanning subgraph of $G[S]$ such
that every edge in $E(G^{\prime})$ is in at least $\ell$ triangles in
$G^{\prime}$ and the diameter of $G^{\prime}$ is at most $s$. If $\ell$ edges
are removed from $G^{\prime}$, then $S$ is still an $(s+\ell)$-club and a
$(2s)$-club.

###### Proof

We show that if $\ell$ edges are removed from $G^{\prime}$, the diameter of
the resulting graph $\widetilde{G}$ increases by at most $\ell$. Let
$P=(v_{1},\ldots,v_{s+1})$ be a path of length $s$ in $G^{\prime}$. Since
$G^{\prime}$ is an edge-$\ell$-triangle $s$-club, every edge $v_{i}v_{i+1}$ of
$P$ is part of at least $\ell$ triangles in $G^{\prime}$. Thus, for two
vertices $v_{i}$ and $v_{i+1}$ in $P$ there is a path of length at most two
from $v_{i}$ to $v_{i+1}$ in $G^{\prime}$, either directly through the edge
$v_{i}v_{i+1}$ or via a vertex $u$ that forms one of the $\ell$ triangles with
$v_{i}$ and $v_{i+1}$ in $G^{\prime}$. Thus,
$\operatorname{dist}(v_{i},v_{i+1})$ increases by at most $1$ after one edge
deletion and only if $v_{i}v_{i+1}$ is removed. Since at most $\ell$ of the
edges in $P$ are removed, we have
$\operatorname{dist}(v_{1},v_{s+1})\leq\operatorname{dist}(v_{1},v_{2})+\ldots+\operatorname{dist}(v_{s},v_{s+1})\leq
s+\ell$ in $\widetilde{G}$. By the same arguments, we also have
$\operatorname{dist}(v_{1},v_{s+1})\leq 2s$.

Thus, after deleting $\ell$ edges in $G^{\prime}$, $S$ is an $(s+\ell)$-club
and a $(2s)$-club. ∎

The following further variant of $s$-Club is also practically motivated but
not necessarily by concerns about the robustness of the $s$-club. Here the
difference to the standard problem is simply that we are given a set of seed
vertices $W$ and aim to find a large $s$-club that contains all seed vertices.

Seeded $s$-Club

Input: |  An undirected graph $G$ = $(V,E)$, a subset $W\subseteq V$, and an integer $k\geq 1$.
---|---
Question: |  Does $G$ contain an $s$-club $S$ of size at least $k$ such that $W\subseteq S$?

This variant has applications in community detection, where we are often
interested in finding communities containing some set of fixed vertices [12,
19].

In this work, we study the parameterized complexity of the three above-
mentioned problems with respect to the standard parameter solution size $k$.
Our goal is to determine whether FPT results for $s$-Club [6, 17] transfer to
these practically motivated problem variants.

#### Known Results.

The $s$-Club problem is NP-hard for all $s\geq 1$ [4], even when the input
graph has diameter $s+1$ [2]. For $s=1$, $s$-Club is equivalent to Clique and
thus W[1]-hard with respect to $k$. In contrast, for every $s>1$, $s$-Club is
fixed-parameter tractable (FPT) with respect to the solution size $k$ [6, 17].
This fixed-parameter tractability can be shown via a Turing kernel with
$\mathcal{O}(k^{2})$ vertices for even $s$ and $\mathcal{O}(k^{3})$ vertices
for odd $s$ [17, 6]. The complexity of $s$-Club has been also studied with
respect to different classes of input graphs [9] and with respect to
structural parameters such as degeneracy of the input graph [11]. The $s$-Club
problem can be solved efficiently in practice, in particular for $s=2$ [4, 6,
10]. In particular, the $2$-Club problem has efficient branch-and-bound
algorithms [6, 10] which can compute the optimal solutions on very large
sparse graphs.

Vertex Triangle $s$-Club is NP-hard for all $s\geq 1$ and for all $\ell\geq 1$
[5, 1]. We are not aware of any algorithmic studies of Edge Triangle $s$-Club
or Seeded $s$-Club. NP-hardness of Edge Triangle $s$-Club for $\ell=1$ can be
shown via the reduction for Vertex Triangle $s$-Club for $\ell=1$ [1]. Also,
the NP-hardness of Seeded $s$-Club for $W\neq\emptyset$ follows directly from
the fact that an algorithm for the case where $|W|=1$ can be used as a black
box to solve $s$-Club. Further robust models of $s$-clubs, which are not
considered in this work, include $t$-hereditary $s$-clubs [16], $t$-robust
$s$-clubs [18], and $t$-connected $s$-clubs [20, 14]. For an overview on
clique relaxation models and complexity issues for the corresponding subgraph
problems we refer to the relevant surveys [13, 16].

#### Our Results.

An overview of our results is given in Table 1. For Vertex Triangle $s$-Club
and Edge Triangle $s$-Club, we provide a complexity dichotomy for all
interesting combinations of $s$ and $\ell$, that is, for all $s\geq 2$ and
$\ell\geq 1$, into cases that are FPT or W[1]-hard with respect to $k$,
respectively. Our W[1]-hardness reduction for Edge Triangle $s$-Club for
$\ell\geq 2$ also shows the NP-hardness of this case. The FPT-algorithms are
obtained via adaptions of the Turing kernelization for $s$-Club.
Interestingly, Vertex Triangle $s$-Club with $\ell=1$ is FPT only for larger
$s$, whereas Edge Triangle $s$-Club with $\ell=1$ is FPT for all $s$. In our
opinion, this means that the edge-$\ell$-triangle property is preferable not
only from a modelling standpoint but also from an algorithmic standpoint as it
allows to employ Turing kernelization as a part of the solving procedure, at
least for $\ell=1$. It is easy to see that standard problem kernels of
polynomial size are unlikely to exist for Vertex Triangle $s$-Club and Edge
Triangle $s$-Club: $s$-clubs are necessarily connected and thus taking the
disjoint union of graphs gives a trivial or-composition and, therefore, a
polynomial problem kernel implies coNP $\subseteq$ NP/poly [3].

All of our hardness results for Vertex Triangle $s$-Club and Edge Triangle
$s$-Club are shown by a reduction from Clique which is W[1]-hard with respect
to $k$ [7, 8]. The idea is to replace each vertex of the Clique instance by a
vertex gadget. These gadgets are constructed in such a way that if one of
these vertices is part of a vertex/edge-$\ell$-triangle $2$-club $S$, then the
entire vertex gadget is part of $S$. We can then use the distance constraint
to make sure that full vertex gadgets are chosen only if the corresponding
vertices are adjacent. While this idea is very natural, using the triangle
constraint without creating many vertices that are too close to each other
turned out to be technically challenging.

For Seeded $s$-Club, we provide a kernel with respect to $k$ for clique seeds
$W$ and W[1]-hardness with respect to $k$ for some other cases. For $s=2$, our
results provide a dichotomy into FPT and W[1]-hardness with respect to $k$ in
terms of the structure of the seed.

Table 1: Overview of our results of the parameterized complexity of the three problems with respect to the parameter solution size $k$. |  Vertex Triangle $s$-Club |  Edge Triangle $s$-Club |  Seeded $s$-Club
---|---|---|---
FPT |  $\ell=1$ and $s\geq 4$ |  $\ell=1$ for each $s$ |  $W$ is a clique
W[1]-h |  $\ell=1$ and $s\leq 3$ |  $\ell\geq 2$ for each $s$ |  $s=2$ and $G[W]$ contains at least two non-adjacent vertices
|  $\ell\geq 2$ for each $s$ |  |  $s\geq 3$ and $G[W]$ contains atleast $2$ connected components

The W[1]-hardness of Seeded $s$-Club is provided by two reductions from
Clique. One reduction is for the case $s=2$ and any seed that contains at
least two non-adjacent vertices $u$ and $z$. The other reduction is for the
case $s\geq 3$ and any seed that contains at least two connected components
$U$ and $Z$. In both cases we add two copies $X_{1}$ and $X_{2}$ of the graph
of the Clique instance to the new instance of Seeded $s$-Club such that each
vertex of $X_{1}$ has distance at most $s$ to $u$ or $U$ if its copy in
$X_{2}$ is also part of the solution. We show a similar property for $X_{2}$
and $z$ or $Z$. This ensures that if $p_{1}\in X_{1}$ is in the solution if
and only if $p_{2}\in X_{2}$ is in the solution. Furthermore, the reductions
have the property that vertex $p_{1}$ in $X_{1}$ has distance at most $s$ to
vertex $q_{2}$ in $X_{2}$ if and only if $pq$ is an edge of the Clique
instance. This feature will then ensure that the same clique has to be chosen
from both copies.

Our W[1]-hardness results, in particular those for Seeded $s$-Club, show that
the FPT results for $s$-Club are quite brittle since the standard argument
that we may assume $k\geq\Delta$ fails and that adding even simple further
constraints makes finding small-diameter subgraphs much harder.

#### Preliminaries.

For integers $p,q$, we denote $[p,q]\coloneqq\\{p,p+1,\ldots,q\\}$ and
$[q]\coloneqq[1,q]$. For a graph $G$, we let $V(G)$ denote its vertex set and
$E(G)$ its edge set. We let $n$ and $m$ denote the order of $G$ and the number
of edges in $G$, respectively. A _path of length $p$_ is a sequence of
pairwise distinct vertices $v_{1},\ldots,v_{p+1}$ such that $v_{i}v_{i+1}\in
E(G)$ for each $i\in[p]$. The _distance_ $\operatorname{dist}_{G}(u,v)$ is the
length of a shortest path between vertices $u$ and $v$. Furthermore, we define
$\operatorname{dist}_{G}(u,W)\coloneqq\min_{w\in W}\operatorname{dist}(u,w)$.
We denote by $\operatorname{diam}_{G}(G)\coloneqq\max_{u,v\in
V(G)}\operatorname{dist}_{G}(u,v)$ the _diameter_ of $G$. Let $S\subseteq
V(G)$ be a vertex set. We denote by $N_{i}(S)\coloneqq\\{u\in
V\mid\operatorname{dist}(u,S)=i\\}$ the _open $i$-neighborhood_ of $S$ and by
$N_{i}[S]\coloneqq\bigcup_{j\leq i}N_{i}(S)\cup S$ the _closed
$i$-neighborhood_ of $S$. For a vertex $v\in V(G)$, we write
$N_{i}(v)\coloneqq N_{i}(\\{v\\})$ and $N_{i}[v]\coloneqq N_{i}[\\{v\\}]$. A
graph $G^{\prime}\coloneqq(V^{\prime},E^{\prime})$ with $V^{\prime}\subseteq
V$, and $E^{\prime}\subseteq E(G[V^{\prime}])$ is a _subgraph_ of $G$. By
$G[S]\coloneqq(S,\\{uv\in E(G)\mid u,v\in S\\})$ we denote the _subgraph
induced by_ $S$. Furthermore, by $G-S\coloneqq G[V\setminus S]$ we denote the
induced subgraph obtained after the deletion of the vertices in $S$. A vertex
set such that each pair of vertices is adjacent is called a _clique_ and a
clique consisting of three vertices is a triangle.

For the definitions of parameterized complexity theory, we refer to the
standard monographs [7, 8]. All of our hardness results are shown by a
reduction from Clique.

Clique

Input: |  An undirected graph $G=(V,E)$ and an integer $k$.
---|---
Question: |  Does $G$ contain a clique of size at least $k$?

Clique is W[1]-hard with respect to $k$ [7, 8].

##  2 Vertex Triangle $s$-Club

In this section, we settle the parameterized complexity of Vertex Triangle
$s$-Club with respect to the solution size $k$. First, we show that this
problem is fixed-parameter tractable when $\ell=1$ and $s\geq 4$. Afterwards,
we show W[1]-hardness for all remaining cases, that is, for $\ell\geq 2$ and
$s\geq 2$, and also for $\ell=1$ and $s\in\\{2,3\\}$.

###  2.1 FPT-Algorithms

The overall idea is based on the idea of the Turing kernel for $2$-Club, that
is, bounding the size of $N_{s}[v]$ for each vertex $v\in V(G)$. The first
step is to remove all vertices which are not in a triangle.

###### Reduction Rule 2.1

Let $(G,k)$ be an instance of Vertex Triangle $s$-Club. Delete all vertices
from $G$ which are not part of any triangle.

Clearly, Reduction Rule 2.1 is correct and can be exhaustively applied in
polynomial time. The application of Reduction Rule 2.1 has the following
effect: if some vertex $v$ is close to many vertices, then $(G,k)$ is a
trivial yes-instance.

###### Lemma 1

Let $(G,k)$ be an instance of Vertex Triangle $s$-Club with $\ell=1$ and
$s\geq 4$ to which Reduction Rule 2.1 is applied. Then, $(G,k)$ is a yes-
instance if $|N_{\lfloor s/2\rfloor-1}[v]|\geq k$ for some vertex $v\in V(G)$.

###### Proof

Let $v\in V(G)$ be a vertex such that $|N_{\lfloor s/2\rfloor-1}[v]|\geq k$.
We construct a vertex-$1$-triangle $s$-club $T$ of size at least $|N_{\lfloor
s/2\rfloor-1}[v]|\geq k$. Initially, we set $T\coloneqq N_{\lfloor
s/2\rfloor-1}[v]$. Now, for each vertex $w\in N_{\lfloor s/2\rfloor-1}(v)$ we
do the following: Since Reduction Rule 2.1 is applied, we conclude that there
exist two vertices $x$ and $y$ such that $G[\\{w,x,y\\}]$ is a triangle. We
add $x$ and $y$ to the set $T$. We call the set of vertices added in this step
the _$T$ -expansion_.

Next, we show that $T$ is indeed a vertex-$1$-triangle $s$-club for $s\geq 4$.
Observe that each vertex in $T$ is either in $N_{\lfloor s/2\rfloor-1}[v]$ or
a neighbor of a vertex in $N_{\lfloor s/2\rfloor-1}(v)$. Hence, each vertex in
$T$ has distance at most $\lfloor s/2\rfloor$ to vertex $v$. Thus, $T$ is an
$s$-club. It remains to show that each vertex of $T$ is in a triangle. Observe
that for each vertex $w\in N_{\lfloor s/2\rfloor-2}[v]$ we have $N(w)\subseteq
N_{\lfloor s/2\rfloor-1}[v]$. Recall that since Reduction Rule 2.1 is applied,
each vertex in $G$ is contained in a triangle. Thus, each vertex of
$N_{\lfloor s/2\rfloor-2}[v]$ is contained in a triangle in $T$. Furthermore,
all vertices in $N_{\lfloor s/2\rfloor-1}(v)\cup(T\setminus N_{\lfloor
s/2\rfloor-1}[v])$ are in a triangle because of the $T$-expansion. Since
$|T|\geq|N_{\lfloor s/2\rfloor-1}[v]|\geq k$, the statement follows.∎

Next, we show that Lemma 1 implies the existence of a Turing kernel for $s\geq
4$. We do this by showing that $N_{s}[v]$ is bounded for every vertex in the
graph. This in turn implies that the problem is fixed-parameter tractable. It
is sufficient to bound the size of $N_{s}[v]$ for each $v\in V(G)$ since we
then can query the oracle for an $s$-club of size $k$.

###### Theorem 2.2

Vertex Triangle $s$-Club for $\ell=1$ admits a $k^{4}$-vertex Turing kernel if
$s=4$ or $s=7$, a $k^{5}$-vertex Turing kernel if $s=5$, and a $k^{3}$-vertex
Turing kernel if $s=6$ or $s\geq 8$.

###### Proof

First, we apply Reduction Rule 2.1. Because of Lemma 1 we conclude that
$(G,k)$ is a trivial yes-instance if $|N_{\lfloor s/2\rfloor-1}[v]|\geq k$ for
any vertex $v\in V(G)$. Thus, in the following we can assume that $|N_{\lfloor
s/2\rfloor-1}[v]|<k$ for each vertex $v\in V(G)$. We use this fact to bound
the size of $N_{s}[v]$ in non-trivial instances.

In this case we have $\lfloor s/2\rfloor-1=1$. Hence, for each $s\geq 4$ from
$|N_{\lfloor s/2\rfloor-1}[v]|<k$ we obtain that the size of the neighborhood
of each vertex is bounded. Thus, we obtain a $k^{4}$-vertex Turing kernel for
$s=4$ and a $k^{5}$-vertex Turing kernel for $s=5$. Furthermore, if $s=7$ we
have $\lfloor s/2\rfloor-1=2$. Thus, we obtain a $k^{4}$-vertex Turing kernel
for $s=7$ since $N_{7}[v]\subseteq N_{8}[v]=N_{2}[N_{2}[N_{2}[N_{2}[v]]]]$.

If $s=6$ or $s\geq 8$, then $\lfloor s/2\rfloor-1\geq\lceil s/3\rceil$.
Observe that $N_{s}[v]$ is contained in $N_{\lceil s/3\rceil}[N_{\lceil
s/3\rceil}[N_{\lceil s/3\rceil}[v]]]$. Thus, we obtain a $k^{3}$-vertex Turing
kernel for $s=6$ or $s\geq 8$.∎

Note that $s\geq 4$ is necessary to ensure $\lfloor s/2\rfloor-1\geq 1$. In
our arguments to obtain a Turing kernel $\ell=1$ is necessary for the
following reason: if $\ell\geq 2$, then the remaining vertices of the other
triangles of a vertex in the $T$-expansion may be contained in $N_{\lfloor
s/2\rfloor+1}$ and, thus, adding them will not necessarily give an $s$-club.
Also note that using $N_{t}[v]$ for some $t<\lfloor s/2\rfloor-1$ does not
help: The remaining vertices of the other triangles of a vertex in the
$T$-expansion may be contained in in $N_{t+1}$. But now, another $T$-expansion
for the vertices in $N_{t+1}$ is necessary. This may lead to a cascade of
$T$-expansions where eventually, we add vertices with distance at least $s+1$
to $v$. Thus, the constructed set is no $s$-club anymore.

###  2.2 Parameterized Hardness

In the following, we prove W[1]-hardness for Vertex Triangle $s$-Club
parameterized by the solution size $k$ for all cases not covered by Theorem
2.2, that is, $\ell\geq 2$ and $s\geq 2$, and also for $\ell=1$ and
$s\in\\{2,3\\}$.

###### Theorem 2.3

Vertex Triangle $s$-Club is W[1]-hard for parameter $k$ if $\ell\geq 2$, and
if $\ell=1$ and $s\in\\{2,3\\}$.

For some combinations of $s$ and $\ell$ we provide hardness for restricted
input graphs. More precisely, we prove that Vertex Triangle $s$-Club is
W[1]-hard even if each vertex $v\in V(G)$ is contained in _exactly_ $\ell$
triangles in the input graph. In other words, the hardness does not depend on
the fact that we could choose different triangles. We provide this hardness
for the case $s\geq 3$ and arbitrary $\ell$ and also for $s=2$ when
$\ell=\binom{c-1}{2}$ for some integer $c$.

We prove the theorem by considering four subcases. The proofs for the four
cases all use a reduction from the W[1]-hard Clique problem. In these
constructions, each vertex $v$ of the Clique instance is replaced by a vertex
gadget $T^{v}$ such that every vertex-$\ell$-triangle $s$-club $S$ either
contains $T^{v}$ completely or contains no vertex of $T^{v}$. This property is
obtained since each vertex in $T^{v}$ will be in exactly $\ell$ triangles and
each of these triangles is within $T^{v}$. The idea is that if $uv\notin E(G)$
then there exists a vertex $x\in T^{u}$ and a vertex $y\in T^{v}$ such that
$\operatorname{dist}(x,y)\geq s+1$.

#### Vertex Triangle $2$-Club.

First, we handle the case $s=2$.

###### Construction 2.4

Let $(G,k)$ be an instance of Clique and let $c$ be the smallest number such
that $\binom{c-1}{2}\geq\ell$. We construct an instance $(G^{\prime},c(k+1))$
of Vertex Triangle $2$-Club as follows.

  * •

For each vertex $v\in V(G)$, we add a clique
$T^{v}\coloneqq\\{x_{1}^{v},\ldots,x_{c}^{v}\\}$ of size $c$ to $G^{\prime}$.

  * •

For each edge $vw\in E(G)$, we connect the cliques $T^{v}$ and $T^{w}$ by
adding the edge $x^{v}_{2i-1}x^{w}_{2i}$ and $x^{w}_{2i-1}x^{v}_{2i}$ to
$G^{\prime}$ for each $i\in[\lfloor c/2\rfloor]$.

  * •

Furthermore, we add a clique $Y\coloneqq\\{y_{1},\ldots,y_{c}\\}$ of size $c$
to $G^{\prime}$.

  * •

We also add, for each $i\in[c]$ and each $v\in V(G)$, the edge
$x^{v}_{i}y_{i}$ to $G^{\prime}$.

Note that the clique size $c$ ensures that each vertex $x\in V(G^{\prime})$ is
contained in at least $\binom{c-1}{2}\geq\ell$ triangles in $G^{\prime}$.
Furthermore, note that the clique $Y$ is only necessary when $c$ is odd to
ensure that the vertices $x^{v}_{c}$ and $x^{w}_{c}$ have a common neighbor.
We add the clique $Y$ in both cases to unify the construction and the
correctness proof. Next, we show that for each vertex gadget $T^{v}$ the
intersection with each vertex-$\ell$-triangle $2$-club is either empty or
$T^{v}$.

###### Lemma 2

Let $S$ be a vertex-$\ell$-triangle $2$-club in $G^{\prime}$. Then,

  * a)

$S\cap T^{v}\neq\emptyset\Leftrightarrow T^{v}\subseteq S$, and

  * b)

$S^{\prime}\coloneqq S\cup Y$ is also a vertex-$\ell$-triangle $2$-club in
$G^{\prime}$.

###### Proof

First, we show statement $a)$. Assume that for a vertex $z\in T^{v}$ for some
$v\in V(G)$ we have $z\in S$ for some vertex-$\ell$-triangle $2$-club $S$.
Note that $T^{v}$ contains all vertices which form a triangle with vertex $z$.
Since $c$ is minimal such that $\binom{c-1}{2}\geq\ell$ and since $T^{v}$ is a
clique, we conclude that $T^{v}\subseteq S$ to fulfill the property that
vertex $z$ is contained in at least $\ell$ triangles in $G[S]$. Thus,
$T^{v}\subseteq S$.

Second, we show statement $b)$. Since each vertex $y\in Y$ forms only
triangles with vertices in $Y$ and $Y$ has size $\binom{c-1}{2}$, we conclude
that $Y\subseteq S^{*}\Leftrightarrow S^{*}\cap Y\neq\emptyset$ for each
vertex-$\ell$-triangle $2$-club $S^{*}$. In the following, let $S$ be a
vertex-$\ell$-triangle $2$-club such that $Y\cap S=\emptyset$. From statement
$a)$ we conclude that $S\coloneqq\bigcup_{v\in P}T^{v}$ for some set
$P\subseteq V(G)$. Next, we show that $S^{\prime}\coloneqq S\cup Y$ is also a
vertex-$\ell$-triangle $2$-club. Since each vertex is contained in a clique of
size $c$ in $S$, it is in sufficiently many triangles. Thus, it remains to
prove that $S^{\prime}$ is a $2$-club. Hence, consider some vertex $x^{v}_{i}$
and some vertex $y_{j}$ for some $i,j\in[c]$ and $v\in P$. Then, $y_{i}$ is a
common neighbor of $x^{v}_{i}$ and $y_{j}$. Hence, $S^{\prime}$ is a
vertex-$\ell$-triangle $2$-club and thus $b)$ holds.∎

Now, we prove the correctness of Construction 2.4.

###### Lemma 3

For each $\ell\in\mathds{N}$, the Vertex Triangle $2$-Club problem
parameterized by $k$ is W[1]-hard.

###### Proof

We prove that $G$ contains a clique of size $k$ if and only if $G^{\prime}$
contains a vertex-$\ell$-triangle $2$-club of size at least $c(k+1)$.

Let $C$ be a clique of size at least $k$ in $G$. We argue that $S\coloneqq
Y\cup\bigcup_{v\in C}T^{v}$ is a vertex-$\ell$-triangle $2$-club of size
$c(k+1)$ in $G^{\prime}$. Note that for each vertex $v\in T^{v}$ we have
$|T^{v}|=c$. Since $T^{v}$ is a clique, we conclude that each vertex in
$T^{v}$ is contained in exactly $\binom{c-1}{2}\geq\ell$ triangles. The same
is true for each vertex in $Y$. Hence, each vertex in $S$ is contained in at
least $\ell$ triangles. Thus, it remains to show that $S$ is a $2$-club.
Consider the vertices $x^{v}_{i}$ and $x^{w}_{j}$ for $v,w\in C$, $i\in[c-1]$,
and $j\in[c]$. If $i$ is odd, then $x^{w}_{i+1}\in N(x^{v}_{i})\cap
N(x^{w}_{j})$. Otherwise, if $i$ is even, $x^{w}_{i-1}\in N(x^{v}_{i})\cap
N(x^{w}_{j})$. In both cases, we obtain
$\operatorname{dist}(x^{v}_{i},x^{w}_{j})\leq 2$. Next, consider two vertices
$x^{v}_{c}$ and $x^{w}_{c}$ in $S$. Observe that $y_{c}\in N(x^{v}_{c})\cap
N(x^{w}_{c})$. Since $Y$ is a clique, it remains to consider vertices
$x^{v}_{i}$ and $y_{j}$ in $S$ for $i\in[c]$ and $j\in[c]$. Observe that
$x^{v}_{j}\in N(y_{j})\cap N[x^{v}_{i}]$. Thus, $G^{\prime}$ contains a
vertex-$\ell$-triangle $2$-club of size at least $c(k+1)$.

Conversely, suppose that $G^{\prime}$ contains a vertex-$\ell$-triangle
$2$-club $S$ of size at least $c(k+1)$. By Lemma 2, we can assume that
$Y\subseteq S$ and for each vertex gadget $T^{v}\in G^{\prime}$ we either have
$T^{v}\subseteq S$ or $T^{v}\cap S=\emptyset$. Hence, $S$ contains at least
$k$ cliques of the form $T^{v}$. Assume towards a contradiction that $S$
contains two cliques $T^{v}$ and $T^{w}$ such that $vw\notin E(G)$ and
consider the two vertices $x^{v}_{1}\in T^{v}$ and $x^{w}_{2}\in T^{w}$. Note
that these vertices always exist since $c\geq 3$. Observe that
$N[x^{v}_{1}]=T^{v}\cup\\{x^{u}_{2}\mid uv\in E(G)\\}\cup\\{y_{1}\\}$ and
$N[x^{w}_{2}]=T^{w}\cup\\{x^{u}_{1}\mid uw\in E(G)\\}\cup\\{y_{2}\\}$. Thus,
$\operatorname{dist}(x^{v}_{1},x^{w}_{2})\geq 3$, a contradiction. Hence, for
each two distinct vertex gadgets $T^{v}$ and $T^{w}$ that are contained in
$S$, we observe that $vw\in E(G)$. Consequently, the set $\\{v\mid
T^{v}\subseteq S\\}$ is a clique of size at least $k$ in $G$.∎

If $\ell=\binom{c-1}{2}$ for some integer $c$, then Lemma 3 also holds for the
restriction that each vertex is contained in exactly $\ell$ triangles in the
input graph $G^{\prime}$.

#### Vertex Triangle $s$-Club for $s=3$ and for $\ell\geq 2$ and $s\geq 4$.

Now, we provide hardness for the remaining cases. We consider three subcases.
Case $1$ deals with odd $s$. Case $2$ covers the case that $s$ is even and
$\ell\geq 3$. Case $3$ deals with the case that $s$ is even and $\ell=2$. All
three cases use the same vertex gadget. Only the edges between these gadgets,
called _connector edges_ , differ. The idea is to construct the vertex gadgets
$T^{v}$ in such a way that there are pairs of vertices in $T^{v}$ of distance
$2s^{*}$ which is almost $s$. Thus, in a vertex-$\ell$-triangle $s$-club, the
distance between two different vertex gadgets must be small. The first part of
the following construction describes the vertex gadget which is used in all
three cases. For an illustration of this construction see Fig. 1.

$a)$$q^{v}_{2}$$p^{v}_{2}$$x^{v}_{s^{*},2}=x^{v}_{3,2}$$x^{v}_{3,1}$$y^{v}_{2,1}$$x^{v}_{2,1}$$x^{v}_{2,2}$$y^{v}_{1,2}$$x^{v}_{1,2}$$x^{v}_{1,1}$$q^{v}_{1}$$p^{v}_{1}$$p^{w}_{2}$$q^{w}_{2}$$x^{w}_{3,1}$$x^{w}_{s^{*},2}=x^{w}_{3,2}$$z^{w}_{s^{*}-1,1}=z^{w}_{2,1}$$x^{w}_{2,2}$$x^{w}_{2,1}$$z^{w}_{1,2}$$x^{w}_{1,1}$$x^{w}_{1,2}$$p^{w}_{1}$$q^{w}_{1}$$b)$$q^{v}_{3}$$p^{v}_{3}$$x^{v}_{s^{*},1}=x^{v}_{2,1}$$x^{v}_{s^{*},3}=x^{v}_{2,3}$$y^{v}_{s^{*}-1,1}=y^{v}_{1,1}$$z^{v}_{s^{*}-1,3}=z^{v}_{1,3}$$x^{v}_{1,3}$$x^{v}_{1,1}$$q^{v}_{1}$$p^{v}_{1}$$q^{v}_{2}$$p^{v}_{2}$
Figure 1: $a)$ The vertex gadgets $T^{v}$ and $T^{w}$ for $s\in\\{7,8\\}$ and
$\ell=2$. The blue lines are only added if $s$ is odd and the red lines are
only added if $s$ is even. $b)$ The vertex gadget $T^{v}$ for $s\in\\{5,6\\}$
and $\ell=3$.

###### Construction 2.5

We set $s^{*}\coloneqq\lfloor(s-1)/2\rfloor$. Let $(G,k)$ be an instance of
Clique. We construct an equivalent instance $(G^{\prime},3\ell ks^{*})$ of
Vertex Triangle $s$-Club. Recall that $\ell\geq 1$ and $s=3$, or $\ell\geq 2$
and $s\geq 4$. For each vertex $v\in V(G)$ we construct a vertex gadget
$T^{v}$. This vertex gadget is used for each reduction of the three cases.

  * •

We add the vertices $p^{v}_{i}$, and $q^{v}_{i}$, and an edge
$p^{v}_{i}q^{v}_{i}$ for each $i\in[\ell]$ to $G^{\prime}$.

  * •

We add a vertex $x^{v}_{j,i}$ for each $i\in[\ell]$ and each $j\in[s^{*}]$ to
$G^{\prime}$.

  * •

We add an edge $y^{v}_{t,i}z^{v}_{t,i}$ for each $i\in[\ell]$ and each
$t\in[s^{*}-1]$ to $G^{\prime}$. Note that these vertices only exist, if
$s\geq 5$.

The vertices $x^{v}_{j,i}$, $y^{v}_{t,i}$, and $z^{v}_{t,i}$ are referred to
as the _cascading vertices_. They are used to ensure that all vertices in
$T^{v}$ are in exactly $\ell$ triangles and that there are vertex pairs of
distance $2s^{*}$ within $T^{v}$. Note that since $s\geq 3$ we create at least
$\ell$ many $x$-vertices. We connect these vertices as follows:

  * •

We add the edges $p^{v}_{i}x^{v}_{1,j}$ and $q^{v}_{i}x^{v}_{1,j}$ for each
$i\in[\ell-1]$ and each $j\in[\ell]$ to $G^{\prime}$.

  * •

We add the edges $p^{v}_{\ell}x^{v}_{s^{*},j}$ and
$q^{v}_{\ell}x^{v}_{s^{*},j}$ for each $j\in[\ell]$ to $G^{\prime}$.

  * •

We add the edges $y^{v}_{t,i}x^{v}_{t,i}$ and $z^{v}_{t,i}x^{v}_{t,i}$ for
each $i\in[\ell]$, and each $t\in[s^{*}-1]$ to $G^{\prime}$.

  * •

We add the edges $y^{v}_{t,i}x^{v}_{t+1,j}$ and $z^{v}_{t,i}x^{v}_{t+1,j}$ for
each $i\in[\ell]$, each $j\in[\ell]\setminus\\{i\\}$, and each $t\in[s^{*}-1]$
to $G^{\prime}$.

Note that if $s=3$ or $s=4$, the graph $G^{\prime}$ is a non-induced biclique
where one partite set consists of the vertices $\\{x^{v}_{1,j}\mid
j\in[\ell]\\}$ and the other partite set consists of the vertices
$\\{\\{p^{v}_{i},q^{v}_{i}\\}\mid i\in[\ell]\\}$. Furthermore, the additional
edges are $p^{v}_{i}q^{v}_{i}$ for each $i\in[\ell]$. Also, observe that each
vertex gadget $T^{v}$ consists of exactly $3\ell s^{*}$ vertices.

From now on, the construction for the three cases differs. We now connect
these vertex gadgets by introducing the _connector edges_ : For each edge
$vw\in E(G)$ we add edges between the vertex gadgets $T^{v}$ and $T^{w}$ of
the corresponding vertices. We distinguish the three cases.

  1. Case I:

$s$ is odd. We add the edges $p^{v}_{i}q^{w}_{i}$ and $q^{v}_{i}p^{w}_{i}$ to
$G^{\prime}$ for each $i\in[\ell]$ to $G^{\prime}$.

  2. Case II:

$s$ is even and $\ell\geq 3$. We add the edges $p^{v}_{1}q^{w}_{1}$,
$q^{v}_{1}p^{w}_{1}$, $p^{v}_{\ell}q^{w}_{\ell}$, and
$q^{v}_{\ell}p^{w}_{\ell}$ to $G^{\prime}$.

  3. Case III:

$s$ is even and $\ell=2$. We add the edges $p^{v}_{1}x^{w}_{s^{*},1}$, and
$p^{w}_{1}x^{v}_{s^{*},1}$ to $G^{\prime}$.

We make the following observation about the connector edges between different
vertex gadgets: If $s$ is odd (Case I), or if $s$ is even and $\ell\geq 3$
(Case II), we have $N(p^{v}_{i})\setminus T^{v}\subseteq\\{q^{w}_{i}\mid vw\in
E(G)\\}$ and also $N(q^{v}_{i})\setminus T^{v}\subseteq\\{p^{w}_{i}\mid vw\in
E(G)\\}$ for each $v\in V(G)$ and each $i\in[\ell]$. Otherwise, if $s$ is even
and $\ell=2$ (Case III), observe that we have $N(p^{v}_{1})\setminus
T^{v}=\\{x^{w}_{s*,1}\mid vw\in E(G)\\}$ and also $N(x^{v}_{s^{*},1})\setminus
T^{v}=\\{p^{w}_{1}\mid vw\in E(G)\\}$ for each $v\in V(G)$. Since only the
connector edges have endpoints in different vertex gadgets, we thus observe
the following.

###### Observation 2.6

All $3$ endpoints of each triangle in $G^{\prime}$ are contained in exactly
one vertex gadget.

Next, we show that each vertex in a vertex gadget $T^{v}$ is contained in
exactly $\ell$ triangles. Together with Observation 2.6 this implies that each
vertex in $G^{\prime}$ is contained in exactly $\ell$ triangles.

###### Lemma 4

Let $T^{v}$ be a vertex gadget. Each vertex in $T^{v}$ is contained in exactly
$\ell$ triangles.

###### Proof

We make a case distinction, that is, for each vertex $a\in T^{v}$ we present
exactly $\ell$ triangles containing vertex $a$. We distinguish the different
vertices of a vertex gadget.

Case 1: Consider vertex $p^{v}_{d}$ for some $d\in[\ell-1]$. Because of
Observation 2.6 we only have to consider the neighbors of $p^{v}_{d}$ in
$T^{v}$. By construction we have $N(p^{v}_{d})\cap
T^{v}=\\{q^{v}_{d}\\}\cup\\{x^{v}_{1,j}\mid j\in[\ell]\\}$. Observe that the
only edges within $N(p^{v}_{d})\cap T^{v}$ are the edges
$q^{v}_{d}x^{v}_{1,j}$ for each $j\in[\ell]$. Thus, $p^{v}_{d}$ is contained
in the $\ell$ triangles $\\{\\{p^{v}_{d},q^{v}_{d},x^{v}_{1,i}\\}\mid
i\in[\ell]\\}$. By similar arguments the same is true for vertex $q^{v}_{d}$.

Case 2: Consider vertex $p^{v}_{\ell}$. By construction we have
$N(p^{v}_{\ell})=\\{q^{v}_{\ell}\\}\cup\\{x^{v}_{s^{*},i}\mid
i\in[\ell]\\}\cup\\{q^{w}_{d}\mid vw\in E(G)\\}$ if $s$ is odd or $s$ is even
and $\ell\geq 3$. If $s$ is even and $\ell=2$ we have
$N(p^{v}_{\ell})=\\{q^{v}_{\ell}\\}\cup\\{x^{v}_{s^{*},i}\mid i\in[\ell]\\}$.
Observe that the only edges within $N(p^{v}_{\ell})$ are the edges
$q^{v}_{\ell}x^{v}_{s^{*},i}$ for each $i\in[\ell]$. Thus, $p^{v}_{\ell}$ is
contained in the $\ell$ triangles
$\\{\\{p^{v}_{\ell},q^{v}_{\ell},x^{v}_{s^{*},i}\\}\mid i\in[\ell]\\}$. By
similar arguments the same is true for vertex $q^{v}_{\ell}$.

Case 3: Now, consider vertices $x^{v}_{1,i}$ and $x^{v}_{s^{*},i}$ for some
$i\in[\ell]$. Here we have to distinguish if $s\in\\{3,4\\}$ or $s\geq 5$
since $y^{v}_{t,i}$ exists only in the second case.

First, consider the case $s=3$ or $s=4$. Note that we now have
$x^{v}_{1,i}=x^{v}_{s^{*},i}$. By construction we have
$N(x^{v}_{1,i})=\\{p^{v}_{j}\mid j\in[\ell]\\}\cup\\{q^{v}_{j}\mid
j\in[\ell]\\}$. Note that the only edges within $N(x^{v}_{1,i})$ have the form
$p^{v}_{j}q^{v}_{j}$ for each $j\in[\ell]$. Thus, $x^{v}_{1,i}$ is contained
in the $\ell$ triangles $\\{\\{x^{v}_{1,i},p^{v}_{j},q^{v}_{j}\\}\mid
j\in[\ell]\\}$.

Second, consider the case $s\geq 5$. First, we investigate vertex
$x^{v}_{1,i}$. By construction we have $N(x^{v}_{1,i})=\\{p^{v}_{j}\mid
j\in[\ell-1]\\}\cup\\{q^{v}_{j}\mid
j\in[\ell-1]\\}\cup\\{y^{v}_{1,i},z^{v}_{1,i}\\}$. The only edges within
$N(x^{v}_{1,i})$ are the edge $p^{v}_{j}q^{v}_{j}$ for each $j\in[\ell-1]$ and
the edge $y^{v}_{1,i}z^{v}_{1,i}$. Thus, $x^{v}_{1,i}$ is contained in the
$\ell-1$ triangles $\\{\\{x^{v}_{1,i},p^{v}_{j},q^{v}_{j}\\}\mid
j\in[\ell-1]\\}$, and in the triangle
$\\{x^{v}_{1,i},y^{v}_{1,i},z^{v}_{1,i}\\}$.

Now, consider vertex $x^{v}_{s^{*},i}$. Because of Observation 2.6 we only
have to consider the neighbors of $x^{v}_{s^{*},i}$ in $T^{v}$. By
construction we observe that $N(x^{v}_{s^{*},i})\cap
T^{v}\subseteq\\{p^{v}_{\ell},q^{v}_{\ell}\\}\cup\\{y^{v}_{s^{*}-1,j},z^{v}_{s^{*}-1,j}\mid
j\in[\ell]\setminus\\{i\\}\\}$. Note that the only edges within
$N(x^{v}_{s^{*},i})$ are the edge $p^{v}_{\ell}q^{v}_{\ell}$ and the edge
$y^{v}_{s^{*}-1,j}z^{v}_{s^{*}-1,j}$ for each $j\in[\ell]\setminus\\{i\\}$.
Thus, $x^{v}_{s^{*},i}$ is contained in the triangle
$\\{x^{v}_{s^{*},i},p^{v}_{\ell},q^{v}_{\ell}\\}$ and in the $\ell-1$
triangles $\\{\\{x^{v}_{s^{*},i},y^{v}_{s^{*}-1,j},z^{v}_{s^{*}-1,j}\\}\mid
j\in[\ell]\setminus\\{i\\}\\}$.

Case 4: Consider vertex $x^{v}_{r,i}$ for some $i\in[\ell]$ and some
$r\in[2,s^{*}-1]$. Recall that these vertices only exist if $s\geq 7$. By
construction
$N(x^{v}_{r,i})=\\{y^{v}_{r,i},z^{v}_{r,i}\\}\cup\\{y^{v}_{r-1,j},z^{v}_{r-1,j}\mid
j\in[\ell]-1\\}$. The only edges within $N(x^{v}_{r,i})$ have the form
$y^{v}_{r,i}z^{v}_{r,i}$ and $y^{v}_{r-1,j}z^{v}_{r-1,j}$ for each
$j\in[\ell]\setminus\\{i\\}$. Thus, $x^{v}_{r,i}$ is contained in the triangle
$\\{x^{v}_{r,i},y^{v}_{r,i},z^{v}_{r,i}\\}$ and in the $\ell-1$ triangles
$\\{\\{x^{v}_{r,i},y^{v}_{r-1,j},z^{v}_{r-1,j}\\}\mid
j\in[\ell]\setminus\\{i\\}\\}$.

Case 5: Finally, consider vertex $y^{v}_{t,i}$ for some $i\in[\ell]$ and some
$t\in[s^{*}-1]$. Recall that these vertices only exist if $s\geq 5$. By
construction we have
$N(y^{v}_{t,i})=\\{x^{v}_{t,i},z^{v}_{t,i}\\}\cup\\{x^{v}_{t+1,j}\mid
j\in[\ell]\setminus\\{i\\}\\}$. The only edges within $N(y^{v}_{t,i})$ is the
edge $x^{v}_{t,i}z^{v}_{t,i}$ and the edge $x^{v}_{t+1,j}z^{v}_{t,i}$ for each
$j\in[\ell]\setminus\\{i\\}$. Thus, $y^{v}_{t,i}$ is contained in the triangle
$\\{y^{v}_{t,i},z^{v}_{t,i},x^{v}_{t,i}\\}$ and in the $\ell-1$ triangles
$\\{\\{y^{v}_{t,i},z^{v}_{t,i},x^{v}_{t+1,j}\\}\mid
j\in[\ell]\setminus\\{i\\}\\}$. By similar arguments the same holds for vertex
$z^{v}_{t,i}$.

Thus, each vertex in $T^{v}$ is contained in exactly $\ell$ triangles.∎

From Lemma 4 and Observation 2.6, we conclude the following.

###### Observation 2.7

Let $S$ be a vertex-$\ell$-triangle $s$-club for $s=3$ and $\ell\geq 1$ and or
for for $s\geq 4$ and $\ell\geq 2$ in $G^{\prime}$. Then, $S\cap
T^{v}\neq\emptyset\Leftrightarrow T^{v}\subseteq S$.

Now, we prove the correctness of Construction 2.5.

###### Lemma 5

For each $s=3$ and $\ell\geq 1$, and also for each $s\geq 4$ and $\ell\geq 2$
the Vertex Triangle $s$-Club problem parameterized by $k$ is W[1]-hard, even
if each vertex in the input graph is contained in exactly $\ell$ triangles.

###### Proof

We show that $G$ contains a clique of size at least $k$ if and only if
$G^{\prime}$ contains a vertex-$\ell$-triangle $s$-club of size at least
$3\ell ks^{*}$.

Let $K$ be a clique of size at least $k$ in $G$. We argue that
$S\coloneqq\bigcup_{v\in K}T^{v}$ is a vertex-$\ell$-triangle $s$-club of size
at least $3\ell ks^{*}$ in $G^{\prime}$. The size bound follows from the fact
that each $T^{v}$ consists of exactly $3\ell s^{*}$ vertices. Furthermore, by
Lemma 4 each vertex in $T^{v}$ for some $v\in V(G)$ is contained in exactly
$\ell$ triangles in $G^{\prime}[T^{v}]$. Hence, it remains to show that $S$ is
an $s$-club.

To do so, we first prove the following two claims. To formulate the claims, we
need some further notation. We define
$T^{v}_{0}\coloneqq\\{p^{v}_{1},\ldots,p^{v}_{\ell-1}\\}\cup\\{q^{v}_{1},\ldots,q^{v}_{\ell-1}\\}$
and $T^{v}_{\ell}\coloneqq\\{p^{v}_{\ell},q^{v}_{\ell}\\}$. Recall that if
$\ell=1$, then $T^{v}_{0}=\emptyset$. Otherwise, both sets are nonempty. This
claim

###### Claim 1

For $\ell\geq 2$, we have
$\operatorname{dist}_{G^{\prime}}(u,a)+\operatorname{dist}_{G^{\prime}}(u,b)=2s^{*}$
for each vertex $a\in T^{v}_{0}$, each vertex $b\in T^{v}_{\ell}$, and for
each vertex $u\in T^{v}\setminus(T^{v}_{0}\cup T^{v}_{\ell})$.

Proof.  By $X^{v}_{1}\coloneqq\\{x^{v}_{1,j}\mid j\in[\ell]\\}$ we denote the
neighbors of $T^{v}_{0}$. We define the sets $X^{v}_{2},\ldots,X^{v}_{s^{*}}$
and $Y^{v}_{1},Z^{v}_{1},\ldots,Y^{v}_{s^{*}-1},Z^{v}_{s^{*}-1}$ analogue. We
first make some observations about the neighborhoods of these vertex sets
which then allows us to obtain upper and lower bounds on these paths.

  * •

$T^{v}_{0}\cup\\{y^{v}_{1,i},z^{v}_{1,i}\\}\subseteq N(x^{v}_{1,i})$ for each
$i\in[\ell]$. Hence $N(X^{v}_{1})=T^{v}_{0}\cup Y^{v}_{1}\cup Z^{v}_{1}$.

  * •

$T^{v}_{\ell}\cup\\{y^{v}_{s^{*}-1,j},z^{v}_{s^{*}-1,j}\\}\subseteq
N(x^{v}_{s^{*},i})$ for each $i\in[\ell]$ and each
$j\in[\ell]\setminus\\{i\\}$. Hence, $N(X^{v}_{s^{*}})=T^{v}_{\ell}\cup
Y^{v}_{s^{*}-1}\cup Z^{v}_{s^{*}-1}$.

  * •

$\\{y^{v}_{t,i},y^{v}_{t-1,j},z^{v}_{t,i},z^{v}_{t-1,j}\\}\subseteq
N(x^{v}_{t,i})$ for each $t\in[2,s^{*}-1]$, each $i\in[\ell]$ and each
$j\in[\ell]\setminus\\{i\\}$. Hence, $N(X^{v}_{t})=Y^{v}_{t}\cup Z^{v}_{t}\cup
Y^{v}_{t-1}\cup Z^{v}_{t-1}$ for $t\in[2,s^{*}-1]$.

  * •

$x^{v}_{t,i},x^{v}_{t+1,j},z^{v}_{t,i}\in N(y^{v}_{t,i})$ and also
$x^{v}_{t,i},x^{v}_{t+1,j},y^{v}_{t,i}\in N(z^{v}_{t,i})$ for each
$t\in[s^{*}-1]$, each $i\in[\ell]$ and each $j\in[\ell]\setminus\\{i\\}$.
Hence, $N(Y^{v}_{t})=X^{v}_{t}\cup Z^{v}_{t}\cup Y^{v}_{t-1}$ and
$N(Z^{v}_{t})=X^{v}_{t}\cup Y^{v}_{t}\cup Y^{v}_{t-1}$ for each
$t\in[s^{*}-1]$.

From the above and a vertex $u\in X^{v}_{z}$ we obtain a path to $a$ of length
$2z-1$ by using subsequent vertices from $Y_{z-1},X_{z-1},\ldots,Y_{1},X_{1}$.
A similar observation can be made for a path from $u$ to $b$. The cases $u\in
Y_{z}\cup Z_{z}$ is treated similar. This implies that
$\operatorname{dist}_{G^{\prime}}(u,a)+\operatorname{dist}_{G^{\prime}}(u,b)\leq
2s^{*}$ for each vertex $a\in T^{v}_{0}$, each vertex $b\in T^{v}_{\ell}$, and
for each vertex $u\in T^{v}\setminus(T^{v}_{0}\cup T^{v}_{\ell})$.
Furthermore, note that in each two steps on any path we can increase/decrease
the first sub-index by one. Hence
$\operatorname{dist}_{G^{\prime}}(u,a)+\operatorname{dist}_{G^{\prime}}(u,b)\geq
2s^{*}$. Thus,
$\operatorname{dist}_{G^{\prime}}(u,a)+\operatorname{dist}_{G^{\prime}}(u,b)=2s^{*}$.
$\blacksquare$

Now, we use Claim 1 to show that $T^{v}$ is a $(2s^{*})$-club.

###### Claim 2

If $s$ is odd, then $T^{v}$ is an $(s-1)$-club and if $s$ is even, then
$T^{v}$ is an $(s-2)$-club for each vertex $v\in V(G)$.

Proof.  Recall that for $s\in\\{3,4\\}$ the gadget $T^{v}$ is a non-induced
biclique. Hence, the statement is true in this case. In the following, we
assume that $s\geq 5$. Note that this implies that $\ell\geq 2$. We only
consider the case that $s$ is odd. The case that $s$ is even follows
analogously.

Consider a pair of vertices $u,\widetilde{u}$ of $T^{v}\setminus(T^{v}_{0}\cup
T^{v}_{\ell})$. To bound the distance of $u$ and $\widetilde{u}$, we consider
one path via a vertex in $T^{v}_{0}$ and one via a vertex in $T^{v}_{\ell}$.
We have
$\operatorname{dist}_{G^{\prime}}(u,\widetilde{u})\leq\min(\operatorname{dist}_{G^{\prime}}(u,a)+\operatorname{dist}_{G^{\prime}}(a,\widetilde{u}),\operatorname{dist}_{G^{\prime}}(u,b)+\operatorname{dist}_{G^{\prime}}(b,\widetilde{u}))$
for each vertex $a\in T^{v}_{0}$, and each vertex $b\in T^{v}_{\ell}$. From
Claim 1 we know that
$\operatorname{dist}_{G^{\prime}}(u,a)+\operatorname{dist}_{G^{\prime}}(u,b)=2s^{*}$
and that
$\operatorname{dist}_{G^{\prime}}(\widetilde{u},a)+\operatorname{dist}_{G^{\prime}}(\widetilde{u},b)=2s^{*}$.
Hence, $\operatorname{dist}_{G^{\prime}}(u,\widetilde{u})\leq 2s^{*}\leq s-1$.
Thus, $T^{v}$ is indeed an $(s-1)$-club. $\blacksquare$

Now, we show that for two vertices $v$ and $w$ in $K$, a vertex $u\in T^{v}$,
and a vertex $\widetilde{u}\in T^{w}$ we have
$\operatorname{dist}_{G^{\prime}}(u,\widetilde{u})\leq s$. We consider the
three cases:

Case I: $s$ is odd. Observe that since $vw\in E(G)$, each vertex
$u\in(T^{v}_{0}\cup T^{v}_{\ell})$ has one neighbor in $T^{w}$. Since $T^{w}$
is an $(s-1)$-club by Claim 2, we obtain that for each vertex
$\widetilde{u}\in T^{w}$ we have
$\operatorname{dist}_{G^{\prime}}(u,\widetilde{u})\leq s$ if $u\in
T^{v}_{0}\cup T^{v}_{\ell}$. Hence, it remains to consider the case that $u\in
T^{v}\setminus(T^{v}_{0}\cup T^{v}_{\ell})$ and that $\widetilde{u}\in
T^{w}\setminus(T^{w}_{0}\cup T^{w}_{\ell})$. For this, let
$u^{v}_{1}\coloneqq\operatorname{dist}_{G^{\prime}}(u,p^{v}_{1}),\widetilde{u}^{w}_{1}\coloneqq\operatorname{dist}_{G^{\prime}}(q^{w}_{1},\widetilde{u}),u^{v}_{\ell}\coloneqq\operatorname{dist}_{G^{\prime}}(u,p^{v}_{\ell})$,
and
$\widetilde{u}^{w}_{\ell}\coloneqq\operatorname{dist}_{G^{\prime}}(q^{w}_{\ell},\widetilde{u})$.
Note that

$\displaystyle\operatorname{dist}_{G^{\prime}}(u,\widetilde{u})$
$\displaystyle\leq\min(u^{v}_{1}+1+\widetilde{u}^{w}_{1},u^{v}_{\ell}+1+\widetilde{u}^{w}_{\ell})$
$\displaystyle=1+\min(u^{v}_{1}+\widetilde{u}^{w}_{1},u^{v}_{\ell}+\widetilde{u}^{w}_{\ell}).$

In this inequality, the ’$+1$’ is the result of the fact that we have to use
an edge to get from gadget $T^{v}$ to gadget $T^{w}$. By Claim 1 we know that
$u^{v}_{1}+u^{v}_{\ell}=2s^{*}$ and that
$\widetilde{u}^{w}_{1}+\widetilde{u}^{w}_{\ell}=2s^{*}$. Since $s$ is odd, we
obtain that $\operatorname{dist}_{G^{\prime}}(u,\widetilde{u})\leq
1+2s^{*}=s$. Thus, $S$ is a vertex-$\ell$-triangle $s$-club of size $3\ell
ks^{*}$.

Case II: $s$ is even and $\ell\geq 3$. For each vertex pair $u\in
T^{v}\setminus T^{v}_{0}$ and $\widetilde{u}\in T^{w}\setminus T^{w}_{0}$ the
proof of $\operatorname{dist}_{G^{\prime}}(u,\widetilde{u})\leq s$ is
analogous to the proof in Case $1$ handling odd values of $s$. Hence, it
remains to show that each vertex $u\in T^{v}_{0}$ has distance at most $s$ to
each vertex $\widetilde{u}\in T^{w}$. Observe that
$\operatorname{dist}_{G^{\prime}}(u,p^{v}_{1})\leq 2$ since
$T^{v}_{0}\subseteq N(x^{v}_{1,1})$ and $x_{1,1}^{*}$ is a neighbor of
$p^{v}_{1}$. Thus, $\operatorname{dist}_{G^{\prime}}(u,q^{w}_{1})=3$ since
$vw\in E(G)$. Furthermore, for each vertex $\widetilde{u}\in T^{w}\setminus
T^{w}_{\ell}$ we have
$\operatorname{dist}_{G^{\prime}}(\widetilde{u},q^{w}_{1})\leq s-3$ by the
proof of Claim 2. Hence, $\operatorname{dist}(u,\widetilde{u})\leq s$. Thus,
it remains to consider the case that $u\in T^{v}_{0}$ and that
$\widetilde{u}\in T^{w}_{\ell}=\\{p^{w}_{\ell},q^{w}_{\ell}\\}$. Since $vw\in
E(G)$ we conclude that $\widetilde{u}$ has a neighbor in $T^{v}$. Since
$T^{v}$ is an $(s-2)$-club by Claim 2 we conclude that
$\operatorname{dist}_{G^{\prime}}(u,\widetilde{u})=s-1$. Hence, $S$ is a
vertex-$\ell$-triangle $s$-club of size $3\ell ks^{*}$.

Case III: $s$ is even and $\ell=2$. Let $x^{w}\coloneqq x_{s^{*},1}^{w}$ and
$x^{v}\coloneqq x_{s^{*},1}^{v}$. Furthermore, let
$u^{v}_{1}\coloneqq\operatorname{dist}_{G^{\prime}}(u,p^{v}_{1}),\widetilde{u}^{w}_{x}\coloneqq\operatorname{dist}_{G^{\prime}}(x^{w},\widetilde{u}),u^{v}_{x}\coloneqq\operatorname{dist}_{G^{\prime}}(u,x^{v})$,
and
$\widetilde{u}^{w}_{1}\coloneqq\operatorname{dist}_{G^{\prime}}(p^{w}_{1},\widetilde{u})$.
We have

$\displaystyle\operatorname{dist}_{G^{\prime}}(u,\widetilde{u})$
$\displaystyle\leq\min(u^{v}_{1}+1+\widetilde{u}^{w}_{x},u^{v}_{x}+1+\widetilde{u}^{w}_{1})$
$\displaystyle=1+\min(u^{v}_{1}+\widetilde{u}^{w}_{x},u^{v}_{x}+\widetilde{u}^{w}_{1}).$

Again, the ’$+1$’ is the result that we have to use an edge to go from $T^{v}$
to gadget $T^{w}$. Consider the following claim.

###### Claim 3

For each vertex $u\in T^{v}$ we have $u^{v}_{1}+u^{v}_{x}\leq s-1$.

Claim 3 directly implies that

$\min(u^{v}_{1}+\widetilde{u}^{w}_{x},u^{v}_{x}+\widetilde{u}^{w}_{1})\leq
s-1$

and thus $\operatorname{dist}_{G^{\prime}}(u,\widetilde{u})\leq s$. This in
turn implies that $S$ is a vertex-$\ell$-triangle $s$-club of size $3\ell
ks^{*}$. Thus, it remains to prove Claim 3.

Proof.  Since $T^{v}$ is an $(s-2)$-club by Claim 2, we conclude that each
vertex $u\in(N[p^{v}_{1}]\cup N[x^{v}_{s^{*},1}])\cap T^{v}$ has distance at
most $s$ to each vertex in $T^{v}$. Hence, it remains to show that each vertex
$u\in T^{v}\setminus(N[p^{v}_{1}]\cup N[x^{v}_{s^{*},1}]))$ has distance at
most $s$ to each vertex $u^{\prime}\in T^{v}$. If $s=4$, then
$T^{v}\subseteq(N[p^{v}_{1}]\cup N[x^{v}_{s^{*},1}])$ and hence the claim is
proven. Hence, in the following, we consider the case $s\geq 6$.

Next, we consider the case that $u\in T^{v}_{0}$. Since $T^{v}_{0}\subseteq
N(x^{v}_{1,1})$ we conclude that $u^{v}_{1}\leq 2$. By the proof of Claim 2 we
conclude that $u^{v}_{x}=s-3$. Hence, Claim 3 is true in this case.

For all remaining cases, it is sufficient to prove the claim for each vertex
$u\in T^{v}\setminus(T^{v}_{0}\cup T^{v}_{\ell})$. First, we consider the case
that $u\coloneqq x^{v}_{t,i}$ for some $t\in[s^{*}]$ and some $i\in[\ell]$.
Then we have $\operatorname{dist}_{G^{\prime}}(x^{v}_{t,i},p^{v}_{1})=2t-1$
and $\operatorname{dist}_{G^{\prime}}(x^{v}_{t,i},x^{v}_{s^{*},1})\leq
2(s^{*}-t)+2$ and hence
$\operatorname{dist}_{G^{\prime}}(x^{v}_{t,i},p^{v}_{1})+\operatorname{dist}_{G^{\prime}}(x^{v}_{t,i},x^{v}_{s^{*},1})\leq
2t-1+s^{*}-2t+2=s^{*}+1\leq s-1$.

Second, we consider the case that $u\coloneqq y^{v}_{t,i}$ for some
$t\in[s^{*}-1]$ and some $i\in[\ell]$. Then we have
$\operatorname{dist}_{G^{\prime}}(y^{v}_{t,i},p^{v}_{1})=2t$ and
$\operatorname{dist}_{G^{\prime}}(y^{v}_{t,i},x^{v}_{s^{*},1})\leq
2(s^{*}-t)+1$ and hence we obtain that
$\operatorname{dist}_{G^{\prime}}(y^{v}_{t,i},p^{v}_{1})+\operatorname{dist}_{G^{\prime}}(y^{v}_{t,i},x^{v}_{s^{*},1})\leq
2t+s^{*}-2t+1=s^{*}+1\leq s-1$. The case that $u\coloneqq z^{v}_{t,i}$ follows
by the same argumentation. $\blacksquare$

Conversely, suppose that $G^{\prime}$ contains a vertex-$\ell$-triangle
$s$-club of size at least $3\ell ks^{*}$. Because of Observation 2.7 for each
vertex-gadget $T^{v}$ we either have $T^{v}\subseteq S$ or $T^{v}\cap
S=\emptyset$. Hence, $S$ contains at least $k$ vertex gadgets. We assume
towards a contradiction that $S$ contains two vertex gadgets $T^{v}$ and
$T^{w}$ such that $vw\notin E(G)$. In each case, we will determine a vertex
$u_{v}\in T^{v}$ and a vertex $u_{w}\in T^{w}$ such that
$\operatorname{dist}_{G^{\prime}}(u_{v},u_{w})\geq s+1$. This contradiction to
the $s$-club property allows us to conclude that the set $\\{v\mid
T^{v}\subseteq S\\}$ is a clique of size at least $k$ in $G$.

Case I: $s$ is odd. We define vertex $u_{v}$ as follows. The vertex $u_{w}$ is
defined analogously. Recall that in this case we have $s^{*}=(s-1)/2$.

  * •

If $s\equiv 3\mod 4$, we set $u_{v}\coloneqq x^{v}_{(s+1)/4,1}$.

  * •

Otherwise, if $s\equiv 1\mod 4$, we set $u_{v}\coloneqq y^{v}_{(s-1)/4,1}$.

Observe that for each vertex $u\in T^{v}_{0}\cup T^{v}_{\ell}$ we have
$\operatorname{dist}_{G^{\prime}}(u_{v},u)=(s-1)/2$. Furthermore, recall that
the vertices in $T^{v}_{0}\cup T^{v}_{\ell}$ are the only vertices in $T^{v}$
with neighbors in other vertex gadgets.

Similarly, for each vertex $u^{\prime}\in T^{w}_{0}\cup T^{w}_{\ell}$ we have
$\operatorname{dist}_{G^{\prime}}(u_{w},u^{\prime})=(s-1)/2$. But since
$vw\notin E(G)$ there are no edges between $T^{v}$ and $T^{w}$, we obtain for
each choice of $u$ and $u^{\prime}$ that
$\operatorname{dist}_{G^{\prime}}(u_{v},u_{w})\geq\operatorname{dist}_{G^{\prime}}(u_{v},u)+2+\operatorname{dist}_{G^{\prime}}(u^{\prime},u_{w})=(s-1)/2+2+(s-1)/2=s+1$,
a contradiction.

Case II: $s$ is even and $\ell\geq 3$. We set $u_{v}\coloneqq p^{v}_{2}$ and
$u_{w}\coloneqq x^{w}_{s^{*},1}$. Note that $u_{v}\in T^{v}_{0}$ since
$\ell\geq 3$. By the construction we obtain that for each vertex
$u_{0}\in\\{p^{v}_{1},q^{v}_{1}\\}$ we have
$\operatorname{dist}_{G^{\prime}}(u_{v},u_{0})=2$ since $T^{v}_{0}\subseteq
N(x^{v}_{1,1})$. Furthermore, for each vertex
$u_{\ell}\in\\{p^{v}_{\ell},q^{v}_{\ell}\\}$ we have
$\operatorname{dist}_{G^{\prime}}(u_{v},u_{\ell})=s-2$. Next, observe that for
each vertex $u^{\prime}_{0}\in\\{p^{w}_{1},q^{w}_{1}\\}$ we have
$\operatorname{dist}_{G^{\prime}}(u_{w},u^{\prime}_{0})=s-3$ and for each
vertex $u^{\prime}_{\ell}\in\\{p^{w}_{\ell},q^{w}_{\ell}\\}$ we have
$\operatorname{dist}(u_{w},u^{\prime}_{\ell})=1$.

Since $vw\notin E(G)$, there are no edges between the gadgets $T^{v}$ and
$T^{w}$. Hence,
$\operatorname{dist}(u_{v},u_{w})\geq\min(\operatorname{dist}(u_{v},u_{0})+2+\operatorname{dist}_{G^{\prime}}(u^{\prime}_{0},u_{w}),\operatorname{dist}_{G^{\prime}}(u_{v},u_{\ell})+2+\operatorname{dist}_{G^{\prime}}(u^{\prime}_{\ell},u_{w}))$
for each vertex $u_{0}\in\\{p^{v}_{1},q^{v}_{1}\\}$, each
$u^{\prime}_{0}\in\\{p^{w}_{1},q^{w}_{1}\\}$, each $u_{\ell}\in T^{v}_{\ell}$,
and each $u^{\prime}_{\ell}\in T^{w}_{\ell}$. By the above argumentation we
obtain
$\operatorname{dist}_{G^{\prime}}(u_{v},u_{w})\geq\min(2+2+s-3,s-2+2+1)=s+1$,
a contradiction.

Case III: $s$ is even and $\ell=2$. We define the vertices $u_{v}$ and $u_{w}$
as follows:

  * •

If $s=4$, we set $u_{v}\coloneqq x^{v}_{1,2}$ and $u_{w}\coloneqq p^{w}_{2}$.

  * •

If $s\equiv 0\mod 4$ and $s\geq 8$, we set $u_{v}\coloneqq x^{v}_{s/4,1}$ and
$u_{w}\coloneqq y^{w}_{s/4,1}$.

  * •

If $s\equiv 2\mod 8$, we set $u_{v}\coloneqq y^{v}_{(s-2)/4,2}$ and
$u_{w}\coloneqq x^{w}_{(s+2)/4,1}$.

  * •

If $s\equiv 6\mod 8$, we set $u_{v}\coloneqq y^{v}_{(s-2)/4,1}$ and
$u_{w}\coloneqq x^{w}_{(s+2)/4,2}$.

From the definition of these vertices we obtain that
$\operatorname{dist}_{G^{\prime}}(u_{v},p^{v}_{1})=s/2-1$,
$\operatorname{dist}_{G^{\prime}}(u_{v},x^{v}_{s^{*},1})=s/2$,
$\operatorname{dist}_{G^{\prime}}(u_{w},p^{w}_{1})=s/2$, and that
$\operatorname{dist}_{G^{\prime}}(u_{w},x^{w}_{s^{*},1})=s/2-1$. Recall that
the vertices $p^{u}_{1}$ and $x^{u}_{s^{*},1}$ are the only vertices in
$T^{u}$ which have neighbors outside $T^{u}$ for each $u\in V(G)$.
Furthermore, observe that all neighbors of $p^{u}_{1}$ which are not contained
in $T^{u}$ are the vertices $x^{b}_{s^{*},1}$ where $ub\in E(G)$. Similar, all
neighbors of $x^{u}_{s^{*},1}$ which are not in $T^{u}$ are of the form
$p^{b}_{1}$ where $ub\in E*G)$. We conclude that
$\operatorname{dist}_{G^{\prime}}(u_{v},u_{w})\geq\operatorname{dist}(u_{v},p^{v}_{1})+3+\operatorname{dist}(x^{w}_{s^{*},1},u_{w})$
Here, the ’$+3$’ results from the fact that at least $3$ edges to switch the
vertex gadgets have to be used: one is not sufficient since $uw\notin E(G)$
and also two are not sufficient since in two steps one can only reach a vertex
$p^{c}_{1}$ for $c\in V(G)$ from $p^{v}_{1}$ but no vertex $x^{d}_{s^{*},1}$
for $d\in V(G)$. Hence, $\operatorname{dist}_{G^{\prime}}(u_{v},u_{w})\geq
s/2-1+3+s/2-1=s+1$, a contradiction.∎

##  3 Edge Triangle $s$-Club

In this section we settle the parameterized complexity of Edge Triangle
$s$-Club with respect to the solution size $k$. Recall that a vertex set $S$
is an edge-$\ell$-triangle $s$-club if $G[S]$ contains a spanning subgraph
$G^{\prime}=(S,E^{\prime})$ such that each edge in $E(G^{\prime})$ is
contained in at least $\ell$ triangles within $G^{\prime}$ and the diameter of
$G^{\prime}$ is at most $s$. First, we show that Edge Triangle $s$-Club is FPT
with respect to $k$ when $\ell=1$ irrespective of the value of $s$ by
providing a Turing kernel. To show this, it is sufficient to delete edges
which are not part of a triangle. Afterwards, we prove W[1]-hardness of Edge
Triangle $s$-Club with respect to $k$ for all fixed $\ell\geq 2$.

###  3.1 Edge Triangle $s$-Club with $\ell=1$

Now, we prove that Edge Triangle $s$-Club for $\ell=1$ admits a Turing kernel
with respect to $k$ implying that the problem is FPT. To obtain the kernel we
need the following reduction rule which removes edges which are in no
triangle.

###### Reduction Rule 3.1

Let $(G,k)$ be an instance of Edge Triangle $s$-Club. Delete all edges from
$G$ which are not part of any triangle.

It is clear that Reduction Rule 3.1 is correct and can be applied in
polynomial time. The idea that after Reduction Rule 3.1 is applied, we can
bound the size of the neighborhood of each vertex. Next, we prove that after
the application of Reduction Rule 3.1 each edge with both endpoints in the
closed neighborhood of a vertex in contained in a triangle.

###### Lemma 6

Let $(G,k)$ be an instance of Edge Triangle $s$-Club with $\ell=1$ to which
Reduction Rule 3.1 is applied. For each vertex $v\in V(G)$ each edge in
$G[N[v]]$ is contained in at least one triangle in $G[N[v]]$.

###### Proof

First, we consider edges of the form $uv$ where $u$ is a neighbor of $v$.
Since Reduction Rule 3.1 is applied, there exists another vertex $w\in V(G)$
such that $G[\\{u,v,w\\}]$ is a triangle. Observe that $w\in N(v)$.

Second, each edge $uw$ with $u,w\in N(v)$ is in a triangle with vertex $v$.∎

Next, we show that any instance such that sufficiently many vertices are close
to some vertex $v$ is a yes-instance.

###### Lemma 7

Let $(G,k)$ be an instance of Edge Triangle $s$-Club with $\ell=1$ to which
Reduction Rule 3.1 is applied. Then, $(G,k)$ is a yes-instance if $|N_{\lfloor
s/2\rfloor}[v]|\geq k$ for some vertex $v\in V(G)$.

###### Proof

By Lemma 6 each edge in $N_{\lfloor s/2\rfloor}[v]$ is contained in at least
one triangle since $N_{\lfloor s/2\rfloor}[v]=\bigcup_{w\in N_{\lfloor
s/2\rfloor-1}[v]}N[w]$. Furthermore, each vertex in $N_{\lfloor
s/2\rfloor}[v]$ has distance at most $\lfloor s/2\rfloor$ to vertex $v$.
Hence, $N_{\lfloor s/2\rfloor}[v]$ is an $s$-club and by definition
$|N_{\lfloor s/2\rfloor}[v]|\geq k$.∎

Lemma 7 implies a Turing kernel for $k$ which implies that the problem is
fixed-parameter tractable.

###### Theorem 3.2

Edge Triangle $s$-Club for $\ell=1$ admits a $k^{2}$-vertex Turing kernel if
$s$ is even and a $k^{3}$-vertex Turing kernel if $s$ is odd and $s\geq 3$.

###### Proof

First, we apply Reduction Rule 3.1 exhaustively. Because of Lemma 7 we
conclude that $(G,k)$ is a trivial yes-instance, if $|N_{\lfloor
s/2\rfloor}[v]|\geq k$ for some $v\in V(G)$. Hence, in the following we can
assume that $k>|N_{\lfloor s/2\rfloor}[v]|$ for each vertex $v\in V(G)$.

First, we consider the case that $s$ is even. Then $\lfloor s/2\rfloor=s/2$
and we obtain that $N_{s}[v]\subseteq N_{s/2}[N_{s/2}[v]]$ for each $v\in
V(G)$. Thus, $|N_{s}[v]|\leq k^{2}$.

Second, we consider the case that $s$ is odd. Observe that we have
$N_{s}[v]\subseteq N_{\lfloor s/2\rfloor}[N_{\lfloor s/2\rfloor}[N_{\lfloor
s/2\rfloor}[v]]]$ for each $v\in V(G)$. Thus, $|N_{s}[v]|\leq k^{3}$.∎

###  3.2 Edge Triangle $s$-Club for $\ell\geq 2$

Now we show W[1]-hardness for the remaining cases.

###### Theorem 3.3

Edge Triangle $s$-Club is W[1]-hard for parameter $k$ if $\ell\geq 2$.

Next, we describe the construction of the reduction to prove Theorem 3.3. We
reduce from Clique. The idea is to construct one vertex gadget for each vertex
of the Clique instance and to add edges between two different vertex gadgets
if and only of the two corresponding vertices are adjacent in such a way that
all these edges are in exactly $\ell$ triangles. For an illustration of this
construction see Fig. 2.

###### Construction 3.4

Let $(G,k)$ be an instance of Clique with $k\geq 3$. We construct an
equivalent instance $(G^{\prime},k^{\prime})$ of Edge-Triangle $s$-Club for
some fixed $\ell\geq 2$ as follows. Let $\ell^{*}\coloneqq\lceil\ell/2\rceil$
and let $x\coloneqq 6\cdot\ell^{*}(s-1)+\lfloor\ell/2\rfloor$. For each vertex
$v\in V(G)$, we construct the following vertex gadget $T^{v}$. For better
readability, all sub-indices of the vertices in $T^{v}$ are considered modulo
$x$. Our construction distinguishes even and odd values of $\ell$. First, we
describe the part of the construction which both cases have in common.

  1. 1.

We add vertex sets $A_{v}\coloneqq\\{a^{v}_{i}\mid i\in[0,x]\\}$ and
$B_{v}\coloneqq\\{b^{v}_{i}\mid i\in[0,x]\\}$ to $G^{\prime}$.

  2. 2.

We add the edges $a^{v}_{i}a^{v}_{i+j}$, and $b^{v}_{i}b^{v}_{i+j}$ for each
$i\in[0,x]$ and each $j\in[-3\ell^{*},3\ell^{*}]\setminus\\{0\\}$ to
$G^{\prime}$.

  3. 3.

We add the edge $a^{v}_{i}b^{v}_{i+j}$ for each $i\in[0,x]$ and each
$j\in[-3\ell^{*},3\ell^{*}]$ to $G^{\prime}$.

In other words, an edge $a^{v}_{i}b^{v}_{j}$ is added if the indices differ by
at most $3\ell^{*}$. For even $\ell$, this completes the construction of
$T^{v}$. For odd $\ell$, we extend $T^{v}$ as follows:

  1. 0-1.

We add the vertex set $C_{v}\coloneqq\\{c^{v}_{i}\mid i\in[0,x]\text{ and
}i\equiv 0\mod\ell^{*}\\}$ to $G^{\prime}$. Note that $C_{v}$ consists of
exactly $6s-5$ vertices.

  2. 0-2.

We add the edges $c^{v}_{i}a^{v}_{i+j}$ and $c^{v}_{i}b^{v}_{i+j}$ for each
$i\in[0,x]$ such that $i\equiv 0\mod\ell^{*}$ and each
$j\in[-3\ell^{*},3\ell^{*}]$ to $G^{\prime}$.

  3. 0-3.

Also, we add the edge $c^{v}_{i}c^{v}_{i+j}$ to $G^{\prime}$ for each
$i\in[0,x]$ such that $i\equiv 0\mod\ell^{*}$ and each
$j\in[-3\ell^{*},3\ell^{*}]\setminus\\{0\\}$ to $G^{\prime}$ if the
corresponding vertex $c^{v}_{i+j}$ exists.

In other words, an edge between $c^{v}_{i}$ and $a^{v}_{j}$, $b^{v}_{j}$, or
$c^{v}_{j}$ is added if the indices differ by at most $3\ell^{*}$. Now, for
each edge $uv\in E(G)$, we add the following to $G^{\prime}$:

  1. 0-4.

We add the edges $a^{v}_{i}b^{u}_{i+j}$ and $a^{u}_{i}b^{v}_{i+j}$ for each
$i\in[0,x]$ and $j\in[0,\lfloor\ell/2\rfloor]$.

  2. 0-5.

If $\ell$ is odd, we also add the edges $c^{v}_{i}b^{u}_{i+j}$ and
$c^{u}_{i}b^{v}_{i+j}$ for each $i\in[0,x]$ such that $i\equiv 0\mod\ell^{*}$
and each $j\in[0,\lfloor\ell/2\rfloor]$ to $G^{\prime}$.

Observe that each vertex $b^{u}_{i+j}$ is adjacent to _exactly_ one vertex in
$C_{v}$.

In other words, an edge between $a^{v}_{i}$ or $c^{v}_{i}$ and $b^{v}_{j}$ is
added if $j$ exceeds $i$ by at most $\lfloor\ell/2\rfloor$. Finally, if $\ell$
is even, we set $k^{\prime}\coloneqq 2(x+1)k=(\ell(6s-5)+2)\cdot k$, and if
$\ell$ is odd, we set $k^{\prime}\coloneqq(2(x+1)+6s-5)k=(\ell+2)(6s-5)\cdot
k$.

$a^{v}_{0}$$a^{v}_{1}$$a^{v}_{2}$$a^{v}_{3}$$a^{v}_{4}$$a^{v}_{5}$$a^{v}_{6}$$a^{v}_{7}$$a^{v}_{8}$$a^{v}_{9}$$a^{v}_{10}$$a^{v}_{11}$$a^{v}_{12}$$a^{v}_{13}$$A_{v}$$B_{w}$$A_{w}$$b^{u}_{0}$$b^{u}_{1}$$b^{u}_{2}$$b^{u}_{3}$$b^{u}_{4}$$b^{u}_{5}$$b^{u}_{6}$$b^{u}_{7}$$b^{u}_{8}$$b^{u}_{9}$$b^{u}_{10}$$b^{u}_{11}$$b^{u}_{12}$$b^{u}_{13}$$B_{u}$
Figure 2: Construction for Theorem 3.3 when $s=3$ and $\ell=2$ and $G$ is a
$P_{3}$ on $\\{u,v,w\\}$ with $uv\notin E(G)$. Only the gadgets
$A_{v},B_{w},A_{w}$, and $B_{u}$ are shown. For simplicity, no edges within
$A_{v}$, $B_{w}$, $A_{w}$, and $B_{u}$ are drawn and edges between $B_{w}$ and
$A_{w}$ are only drawn if one endpoint is $a^{w}_{3}$, $a^{w}_{4}$,
$a^{w}_{9}$, or $a^{w}_{10}$.
Blue encircled vertices are neighbors of $a^{v}_{0}$, red encircled vertices
have distance $2$ to $a^{v}_{0}$, and black encircled vertices have distance
$3$ to $a^{v}_{0}$. Thus, $a^{v}_{0}$ and $b^{u}_{7}=b^{u}_{0+1+3\cdot 1\cdot
2}=b^{u}_{0+\lfloor\ell/2\rfloor+3\ell^{*}(s-1)}$ have distance at least $4$.

Construction 3.4 has two key mechanisms: First, if $uv\notin E(G)$ then for
each vertex $a\in A_{v}$ there is at least one vertex $b\in B_{u}$ such that
$\operatorname{dist}(a,b)>s$. Second, each edge with one endpoint in $A_{v}$
and one endpoint in $B_{u}$ is contained in _exactly_ $\ell$ triangles.
Furthermore, if $\ell$ is odd, then this also holds for each edge with one
endpoint in $C_{v}$ and one in $B_{u}$. Consider an edge-$\ell$-triangle
$s$-club $S$ and let $\widetilde{G}=(S,\widetilde{E})$ be a spanning subgraph
of $G[S]$ with the maximal number of edges, such that each edge of
$\widetilde{E}$ is contained in at least $\ell$ triangles in $\widetilde{G}$
and the diameter of $\widetilde{G}$ is $s$. As we will show, the two mechanics
ensure that an edge with one endpoint in $A_{v}$ (or $C_{v}$) and the other
endpoint in $B_{u}$ is contained in $\widetilde{E}$ if and only if $S$
contains all vertices of $A_{v}$ (and $C_{v}$) and $B_{u}$. We call this the
_enforcement property_. Next, we formalize this property. To this end, we
introduce the following notation. By $E_{uv}$ we denote the set of all edges
with one endpoint in $A_{v}$ (or $C_{v}$ if $\ell$ is odd) and the other
endpoint in $B_{u}$.

###### Lemma 8

Let $S$ be an edge-$\ell$-triangle $s$-club $G^{\prime}$ constructed in
Construction 3.4. More precisely, let $\widetilde{G}=(S,\widetilde{E})$ be a
maximal subgraph of $G[S]$ such that each edge in $E(\widetilde{G})$ is
contained in at least $\ell$ triangles within $\widetilde{G}$ and the diameter
of $\widetilde{G}$ is at most $s$. Let $e\in E_{uv}$. Then $e\in
E(\widetilde{G})$ if and only if $A_{v},B_{u}\subseteq S$ (and $C_{v}\subseteq
S$, if $\ell$ is odd).

###### Proof

Before we show the two implications, we prove the following cascading property
of edge-$\ell$-triangle $s$-clubs which contain at least one edge of $E_{uv}$.

###### Claim 4

If $a^{v}_{i}b^{u}_{j}\in E(\widetilde{G})$ or $c^{v}_{i}b^{u}_{j}\in
E(\widetilde{G})$, then,$E_{uv}\subseteq E(\widetilde{G})$.

Proof.  First, we consider even values of $\ell$. Note that
$\ell^{*}=\lfloor\ell/2\rfloor=\ell/2=\lceil\ell/2\rceil$. By construction we
have

$N[a^{v}_{i}]=\\{a^{v}_{i+i^{\prime}},b^{v}_{i+i^{\prime}}\mid
i^{\prime}\in[-3\ell/2,3\ell/2]\\}\cup\\{b^{w}_{i+i^{\prime}}\mid
i^{\prime}\in[0,\ell/2]\text{ and }vw\in E(G)\\},$

and similar

$N[b^{u}_{j}]=\\{a^{u}_{j+i^{\prime}},b^{u}_{j+i^{\prime}}\mid
i^{\prime}\in[-3\ell/2,3\ell/2]\\}\cup\\{a^{w}_{j-i^{\prime}}\mid
i^{\prime}\in[0,\ell/2]\text{ and }uw\in E(G)\\}.$

Since $a^{v}_{i}b^{u}_{j}\in E(G^{\prime})$ we obtain by Part 0-4. of
Construction 3.4 that $j=i+z$ for some $z\in[0,\ell/2]$. Let
$y\coloneqq\ell/2-z$ and observe that $N(a^{v}_{i})\cap
N(b^{u}_{j})=\\{a^{v}_{i+i^{\prime}}\mid
i^{\prime}\in[-y,z]\setminus\\{0\\}\\}\cup\\{b^{u}_{j+i^{\prime}}\mid
i^{\prime}\in[-z,y]\setminus{\\{0\\}}\\}$. Thus, the edge $a^{v}_{i}b^{u}_{j}$
is contained in exactly $\ell$ triangles whose vertex sets are all contained
in $G^{\prime}[A_{v}\cup B_{u}]$. Since $a^{v}_{i}b^{u}_{j}\in
E(\widetilde{G})$, we thus conclude that all vertices and edges which form
these $\ell$ triangles are contained in $\widetilde{G}$. In particular, we
obtain that $a^{v}_{i+1}b^{u}_{j+1}\in E(\widetilde{G})$ and thus also that
$a^{v}_{i+1},b^{u}_{j+1}\in V(\widetilde{G})$. Now, since
$a^{v}_{i+1}b^{u}_{j+1}\in E(\widetilde{G})$ we can repeat the above
argumentation for the edge $a^{v}_{i+1}b^{u}_{j+1}$ and inductively for the
edge $a^{v}_{i+q}b^{v}_{i+q}$ for all $q\in[x]$. We then have verified that
$A_{v}\cup B_{u}\subseteq V(\widetilde{G})$ and that each edge in $E_{uv}$ is
contained in $E(\widetilde{G})$. Recall that $A_{v}$ and $B_{u}$ have size
$x+1$.

Second, we consider odd values of $\ell$, that is $\ell=2t+1$ for some integer
$t$. Note that $\lfloor\ell/2\rfloor=t$ and that
$\ell^{*}=\lceil\ell/2\rceil=t+1$. Furthermore, observe that vertex
$b^{u}_{j}$ has exactly one neighbor $c^{v}_{j+i^{\prime}}$ in $C_{v}$ for
some $i^{\prime}\in[0,t]$ such that $j+i^{\prime}\mod(t+1)=0$.

Hence, by construction we have

  * •

$N[a^{v}_{i}]=N[c^{v}_{i}]=\\{a^{v}_{i+i^{\prime}},b^{v}_{i+i^{\prime}}\mid
i^{\prime}\in[-3(t+1),3(t+1)]\\}\cup\\{c^{v}_{i+i^{\prime}}\mid
i^{\prime}\in[-3(t+1),3(t+1)]\text{ and
}(i+i^{\prime})\mod(t+1)=0\\}\cup\\{b^{w}_{i+i^{\prime}}\mid
i^{\prime}\in[0,t]\text{ and }vw\in E(G)\\}$,

  * •

$N[b^{u}_{j}]=\\{a^{u}_{j+i^{\prime}},b^{u}_{j+i^{\prime}}\mid
i^{\prime}\in[-3(t+1),3(t+1)]\\}\cup\\{c^{u}_{j+i^{\prime}}\mid
i^{\prime}\in[-3(t+1),3(t+1)]\text{ and
}(j+i^{\prime})\mod(t+1)=0\\}\cup\\{a^{w}_{j-i^{\prime}}\mid
i^{\prime}\in[0,t]\text{ and }uw\in E(G)\\}\cup\\{c^{w}_{j-i^{\prime}}\mid
i^{\prime}\in[0,t]\text{ and }(j-i^{\prime})\mod(t+1)=0\text{ and }uw\in
E(G)\\}$, and

Since $a^{v}_{i}b^{u}_{j}\in E(G^{\prime})$ we obtain by Part 0-4. of
Construction 3.4 that $j=i+z$ for some $z\in[0,t]$. Now, let $y\coloneqq t-z$
and let $c^{v}_{i^{\prime}}$ be the unique neighbor of $b^{u}_{j}$ in $C_{v}$.
We conclude that $N(a^{v}_{i})\cap N(b^{u}_{j})=\\{a^{v}_{i+j^{\prime}}\mid
j^{\prime}\in[-y,z]\setminus\\{0\\}\\}\cup\\{b^{u}_{j+j^{\prime}}\mid
j^{\prime}\in[-z,y]\setminus{0}\\}\cup\\{c^{v}_{i^{\prime}}\\}$.

Hence, both vertices have exactly $t+t+1=\ell$ common neighbors and thus
$N(a^{v}_{i})\cap N(b^{u}_{j})\subseteq S$. By similar arguments a similar
statement can be shown for the edge $c^{v}_{i}b^{u}_{j}$. Thus, the edges
$a^{v}_{i}b^{u}_{j}$ and $c^{v}_{i}b^{u}_{j}$ are contained in exactly $\ell$
triangles whose vertex sets are contained in $G[A_{v}\cup C_{v}\cup B_{u}]$.

Since $a^{v}_{i}b^{u}_{j}\in E(\widetilde{G})$ we thus conclude that all
vertices and edges which form these $\ell$ triangles are contained in
$\widetilde{G}$. In particular, we obtain that $a^{v}_{i+1}b^{u}_{j+1}\in
E(\widetilde{G})$ and also that $a^{v}_{i+1},b^{u}_{j+1}\in V(\widetilde{G})$.
Now, since $a^{v}_{i+1}b^{u}_{j+1}\in E(\widetilde{G})$ we can repeat the
above argumentation for the edge $a^{v}_{i+1}b^{u}_{j+1}$ and inductively for
the edge $a^{v}_{i+q}b^{v}_{i+q}$ for all $q\in[x]$. We then have verified
that $A_{v}\cup B_{u}\cup C_{v}\subseteq V(\widetilde{G})$ and that each edge
in $E_{uv}$ is contained in $E(\widetilde{G})$. $\blacksquare$

Now, we are ready to prove the two implications. The implication that if $e\in
E(\widetilde{G})$ then $A_{v},B_{u}\subseteq S$ (and $C_{v}\subseteq S$, if
$\ell$ is odd) directly follows from Claim 4. It remains to show the other
implication. From Claim 4 we conclude that either $E_{uv}\subseteq
E(\widetilde{G})$ or $E_{uv}\cap E(\widetilde{G})=\emptyset$. If
$E_{uv}\subseteq E(\widetilde{G})$, then we are done, so assume towards a
contradiction that $E_{uv}\cap E(\widetilde{G})=\emptyset$. Recall that
$A_{v}\cup B_{u}\subseteq S$ (and also $C_{v}\subseteq S$ is $\ell$ is odd).
Furthermore, recall that $\widetilde{G}$ is maximal, that is, there exists no
spanning subgraph of $G[S]$ which has more edges than $\widetilde{G}$. Hence,
adding all edges in $E_{uv}$ to $\widetilde{G}$ is still an
edge-$\ell$-triangle $s$-club, a contradiction to the maximality of
$\widetilde{G}$.∎

Now, we prove the correctness of the reduction for Theorem 3.3.

######  Proof (of Theorem 3.3)

We show that $G$ contains a clique of size at least $k$ if and only if
$G^{\prime}$ contains an edge-$\ell$-triangle $s$-club of size at least
$k^{\prime}$.

Let $K$ be a clique of size $k$ in $G$. Recall that $T^{v}$ is the gadget of
vertex $v\in V(G)$. We verify that $S\coloneqq\\{u\in V(T^{v})\mid v\in K\\}$
is an edge-$\ell$-triangle $s$-club of size at least $k^{\prime}$. More
precisely, we show that $\widetilde{G}\coloneqq G[S]$ fulfills all properties
of being an edge-$\ell$-triangle $s$-club. Since $|T^{v}|=2\ell^{*}(6s-5)+2$
if $\ell$ is even and $|T^{v}|=(2\ell^{*}+1)(6s-5)$ if $\ell$ is odd for each
$v\in K$ and since $|K|\geq k$, we have $|S|=|V(\widetilde{G})|\geq
k^{\prime}$. It remains to show that $\widetilde{G}$ is an
edge-$\ell$-triangle $s$-club.

Next, we show that $\widetilde{G}$ is an $s$-club.

First, we show that $T^{v}$ is an $s$-club. Therefore, consider the vertex
pair $\\{a^{v}_{i},a^{v}_{j}\\}$ for some $v\in K$. Observe that
$P\coloneqq(a^{v}_{i},a^{v}_{i+1},\ldots,a^{v}_{i+p})$ for $i+p=j$ is a path
of length $p$ from $a^{v}_{i}$ to $a^{v}_{j}$ and that
$Q\coloneqq(a^{v}_{i},a^{v}_{i-1},\ldots,a^{v}_{i-q})$ for $i-q=j$ is a path
of length $q$ from $a^{v}_{i}$ to $a^{v}_{j}$. Clearly, $p+q=x+1$. Hence,
$\min(p,q)\leq(x+1)/2\leq 3\ell^{*}(s-1)+\lfloor\ell/2\rfloor$. Without loss
of generality, assume that the minimum is achieved by path $P$ and assume that
$p=\alpha\cdot(3\ell^{*})+\beta$ for some $\alpha\in[s-1]$ and some
$\beta<3\ell^{*}$. Recall that by Part 2 of Construction 3.4,
$a^{v}_{i^{\prime}}a^{v}_{j^{\prime}}\in E(G^{\prime})$ if and only if
$j^{\prime}=i^{\prime}+z$ for some
$z\in[-3\ell^{*},3\ell^{*}]\setminus\\{0\\}$. Hence,

$(a^{v}_{i},a^{v}_{i+1\cdot(3\ell^{*})},\ldots,a^{v}_{i+\alpha\cdot(3\ell^{*})},a^{v}_{i+\alpha\cdot(3\ell^{*})+\beta})$

is a path of length at most $(s-1)+1=s$ from $a^{v}_{i}$ to $a^{v}_{j}$.

These arguments also apply symmetrically to the vertex pairs
$\\{b^{v}_{i},b^{v}_{j}\\}$ and $\\{a^{v}_{i},b^{v}_{j}\\}$ for each $v\in K$.
Furthermore, if $\ell$ is odd, observe that the above argumentation can also
be used to show that the vertex pairs $\\{c^{v}_{i},a^{v}_{j}\\}$,
$\\{c^{v}_{i},b^{v}_{j}\\}$, and $\\{c^{v}_{i},c^{v}_{j}\\}$ have distance at
most $s$ to each other.

Second, we show that $a^{v}_{i}$ has distance at most $s$ to $b^{u}_{j}$. Note
that by Part 0-4. of Construction 3.4, $a^{v}_{i}$ has neighbors
$b^{u}_{i},\ldots,b^{u}_{i+\lfloor\ell/2\rfloor}$ since $uv\in E(G)$. In the
following, we assume that $j\neq i+z$ for all $z\in[0,\lfloor\ell/2\rfloor]$.
Consider the paths
$P\coloneqq(a^{v}_{i},b^{u}_{i+\lfloor\ell/2\rfloor},b^{u}_{i+\lfloor\ell/2\rfloor+1},\ldots,,b^{u}_{i+\lfloor\ell/2\rfloor+p})$
for $i+\lfloor\ell/2\rfloor+p=j$ of length $p+1$ and
$Q\coloneqq(a^{v}_{i},b^{u}_{i},b^{u}_{i-1},\ldots,b^{u}_{i-q})$ for $i-q=j$
of length $q+1$. Observe that $(p+1)+(q+1)=(x+3)-\lfloor\ell/2\rfloor$. Thus,
$p+q=(x+1)-\lfloor\ell/2\rfloor=6\ell^{*}(s-1)+1$. Since $p$ and $q$ are
integers we have $\min(p,q)\leq((x+1)-\lfloor\ell/2\rfloor)/2=3\ell^{*}(s-1)$.

Without loss of generality assume that the minimum is achieved by path $P$ and
assume that $p=\alpha\cdot(3\ell^{*})+\beta$ for some $\alpha\in[s-2]$ and
some $\beta\leq 3\ell^{*}$. Recall that by Part 2 of Construction 3.4, we have
$b^{u}_{i^{\prime}}b^{u}_{j^{\prime}}\in E(G^{\prime})$ if and only if
$j^{\prime}=i^{\prime}+z$ for some
$z\in[-3\ell^{*},3\ell^{*}]\setminus\\{0\\}$. Now, observe that

$(a^{v}_{i},b^{u}_{i+\lfloor\ell/2\rfloor},b^{u}_{i+\lfloor\ell/2\rfloor+1\cdot(3\ell^{*})},\ldots,b^{u}_{i+\lfloor\ell/2\rfloor+\alpha\cdot(3\ell^{*})},b^{u}_{i+\lfloor\ell/2\rfloor+\alpha\cdot(3\ell^{*})+\beta})$

is a path of length at most $1+(s-2)+1=s$ from $a^{v}_{i}$ to $b^{u}_{j}$.

Furthermore, if $\ell$ is odd, observe that the above argumentation can also
be used to show that the vertex pairs $\\{c^{v}_{i},b^{u}_{j}\\}$ have
distance at most $s$ to each other by replacing $a^{v}_{i}$ with $c^{v}_{i}$
in the paths $P$ and $Q$.

The fact that vertices $a^{v}_{i}$ and $a^{u}_{j}$, and $b^{v}_{i}$ and
$b^{u}_{j}$, respectively, have distance at most $s$ to each other can be
proven similar as we showed that $a^{v}_{i}$ and $b^{u}_{j}$ have distance at
most $s$ by observing that $a^{v}_{i}$ has distance $2$ to each vertex
$a^{u}_{i+z}$ with $z\in[-3\ell^{*},\lfloor\ell/2\rfloor+3\ell^{*}]$ since
$a^{v}_{i}$ has neighbors $b^{u}_{i},\ldots,b^{u}_{i+\lfloor\ell/2\rfloor}$
and since by Part 2 of Construction 3.4, we have
$b^{u}_{i^{\prime}}a^{u}_{j^{\prime}}\in E(G^{\prime})$ if and only if
$j^{\prime}=i^{\prime}+z^{\prime}$ for some
$z^{\prime}\in[-3\ell^{*},3\ell^{*}]$.

Furthermore, if $\ell$ is odd, observe that the above argumentation can also
be used to show that the vertex pairs $\\{c^{v}_{i},a^{u}_{j}\\}$ and
$\\{c^{v}_{i},c^{u}_{j}\\}$ have distance at most $s$ to each other by
replacing $a^{v}_{i}$ with $c^{v}_{i}$ and replacing $a^{u}_{j}$ with
$c^{u}_{j}$, respectively, in the paths $P$ and $Q$.

Hence, $\widetilde{G}$ is indeed an $s$-club.

Next, we show that each edge in $E(\widetilde{G})$ is contained in at least
$\ell$ triangles which are contained in $\widetilde{G}$.

Consider the edge $a^{v}_{i}a^{v}_{i+j}$ for some
$j\in[-3\ell^{*},3\ell^{*}]$. Without loss of generality, assume that $j>0$.
By Part 2 Construction 3.4, both vertices are adjacent to each vertex
$a^{v}_{i+i^{\prime}}$ with $i^{\prime}\in[3\ell^{*}]\setminus\\{j\\}$. Hence,
both vertices are in at least $3\ell^{*}-1\geq\ell$ triangles.

Furthermore, the statement can be shown analogously for the edges
$b^{v}_{i}b^{v}_{i+j}$ (and $c^{v}_{i}c^{v}_{i+j}$ if $\ell$ is odd) for some
$j\in[-3\ell^{*},3\ell^{*}]$.

Also, the statement can be shown analogously for the edge
$a^{v}_{i}b^{v}_{i+j}$ for some $j\in[-3\ell^{*},3\ell^{*}]$. If $j\geq 0$,
then $a^{v}_{i+z}$ for each $z\in[3\ell^{*}]$ is a common neighbor of both
vertices and thus the edge $a^{v}_{i}b^{v}_{i+j}$ is contained in at least
$\ell$ triangles. The case $j<0$ can be shown analogously.

For odd $\ell$, the statement can be shown analogously for the edges
$a^{v}_{i}c^{v}_{i+j}$, $b^{v}_{i}c^{v}_{i+j}$, and $c^{v}_{i}c^{v}_{i+j}$ for
some $j\in[-3\ell^{*},3\ell^{*}]$.

The fact that the edges $a^{v}_{i}b^{u}_{i+j}$ and $c^{v}_{i}b^{u}_{i+j}$ are
contained in exactly $\ell$ triangles follows from the proof of Lemma 8.

We conclude that each edge in $E(\widetilde{G})$ is contained in at least
$\ell$ triangles in $\widetilde{G}$. Thus, $S$ is indeed an
edge-$\ell$-triangle $s$-club of size $k^{\prime}$.

Conversely, let $S$ be an edge-$\ell$-triangle $s$-club of size at least
$k^{\prime}$ in $G^{\prime}$. More precisely, let $\widetilde{G}$ be a maximal
spanning subgraph of $G[S]$ which has diameter at most $s$ and such that each
edge in $E(\widetilde{G})$ is contained in at least $\ell$ triangles is
$\widetilde{G}$. We show that $G$ contains a clique of size at least $k$.

First, we show that for each vertex $x\in A_{v}\cup B_{v}\cup C_{v}$ there
exists a vertex $y\in A_{u}\cup B_{u}\cup C_{u}$ such that
$\operatorname{dist}(x,y)\geq s+1$ if $uv\notin E(G)$. For this, recall that
by construction each two vertices with sub-indices $i^{\prime}$ and
$j^{\prime}$ are not adjacent if their difference (modulo $x$) is larger than
$3\ell^{*}$.

###### Claim 5

In $G^{\prime}$ we have $\operatorname{dist}(x_{i},y_{j})\geq s+1$ for each
$i\in[0,x]$, $j\coloneqq i+\lfloor\ell/2\rfloor+3\ell^{*}(s-1)$,
$x_{i}\in\\{a^{v}_{i},b^{v}_{i},c^{v}_{i}\\}$, and
$y_{j}\in\\{a^{u}_{j},b^{u}_{j},c^{u}_{j}\\}$ if $uv\notin E(G)$.

Proof.  There are two possible paths from $x_{i}$ to
$y_{i+\lfloor\ell/2\rfloor+3\ell^{*}(s-1)}$ with respect to the indices.
First, there is a subsequence of the indices which is increasing
($i,i+1,\ldots,i+\lfloor\ell/2\rfloor+3\ell^{*}(s-1)$). This path has length
$\lfloor\ell/2\rfloor+3\ell^{*}(s-1)$. Second, there is a subsequence of the
indices which is decreasing ($i,i-1,\ldots,i-i^{\prime}$, where
$-i^{\prime}=i+\lfloor\ell/2\rfloor+3\ell^{*}(s-1)$). This path has length
$3\ell^{*}(s-1)+1$.

Hence, each path from $x_{i}$ to $y_{i+\lfloor\ell/2\rfloor+3\ell^{*}(s-1)}$
has to overcome at least $3\ell^{*}(s-1)+1$ indices. Observe that whenever an
edge between $A_{p}$ (or $C_{p}$) and $B_{q}$ for $p,q\in V(G)$ with $pq\in
E(G)$ is traversed, by construction the index can increase/decrease by at most
$\lfloor\ell/2\rfloor$. Now, we use the fact that $uv\notin E(G)$: There are
no edges between the vertex gadgets $T^{v}$ and $T^{u}$. Thus, at least two
times such a traversal of at most $\lfloor\ell/2\rfloor$ indices has to be
done. Hence, the index $i$ can increase or decrease by at most
$2\cdot\lfloor\ell/2\rfloor+3\ell^{*}(s-2)<3\ell^{*}(s-1)+1$ if at least $2$
edge traversals between different vertex gadgets are necessary. Thus, both
vertices have distance at least $s+1$. $\blacksquare$

The following statement directly follows from Claim 5 and Lemma 8.

###### Claim 6

If $A_{v}\subseteq S$ (or $C_{v}\subseteq S$ if $\ell$ is odd) and
$B_{u}\subseteq S$ then $uv\in E(G)$.

We now use Claims 5 and 6 to show that $G$ contains a clique of size at least
$k$. We distinguish the cases whether $S$ contains only parts of one of the
gadgets $A_{v}$, $B_{v}$, or $C_{v}$ or whether $S$ contains all vertices of
the gadgets $A_{v}$ (or $B_{v}$, or $C_{v}$) completely.

First, assume that for some vertex $v\in V(G)$ we have $A_{v}\cap
S\neq\emptyset$ and $A_{v}\not\subseteq S$. In the following, we show that $S$
only contains vertices of gadget $T^{v}$ and from gadgets $T^{u}$ such that
$uv\in E(G)$. Since $A_{v}\not\subseteq S$, we conclude that in
$\widetilde{G}$ we have $N_{\widetilde{G}}(A_{v}\cap S)\subseteq(B_{v}\cup
C_{v})$: Otherwise, vertex $a_{v}$ has a neighbor $b_{u}\in B_{u}$ and by
Lemma 8 we would obtain $A_{v}\subseteq S$, a contradiction to the assumption
$A_{v}\not\subseteq S$. If $B_{v}\not\subseteq S$, then by Lemma 8 no vertex
in $B_{v}$ can have a neighbor $a^{w}_{i}$ or $c^{w}_{i}$ for some $w\neq v$.
Hence, $S\cap T^{v}$ would be a connected component of size at most $3(x+1)$,
a contradiction to the size of $S$ since $k\geq 3$. Thus, we may assume that
$B_{v}\subseteq S$. Observe that if $a^{w}_{i}\in S$ or $c^{w}_{i}\in S$ for
some $w\in V(G)$ such that $vw\in E(\widetilde{G})$, that is, also $vw\in
E(G^{\prime})$, then we have $A_{w}\subseteq S$ and $C_{w}\subseteq S$ by
Lemma 8 since each vertex $a^{w}_{i}$ and $c^{w}_{i}$ has a neighbor in
$B_{v}$. Let $W\coloneqq\\{w_{1},\ldots,w_{t}\\}$ denote the set of vertices
$w_{j}$ such that $vw_{j}\in E(G)$ and $A_{w_{j}},C_{w_{j}}\subseteq S$. If
$w_{x}w_{y}\notin E(G)$ for some $x,y\in[t]$ with $x\neq y$, then
$a^{w_{x}}_{0}$ and $a^{w_{y}}_{\lfloor\ell/2\rfloor+3\ell^{*}(s-1)}$ have
distance at least $s+1$ by Claim 5. Thus $w_{x}w_{y}\in E(G)$ for each
$x,y\in[t]$ with $x\neq y$.

Assume towards a contradiction that $a^{p}_{i}\in S$ or $c^{p}_{i}\in S$ for
some $p\in V(G)\setminus w$ with $p\neq v$. Note that $pv\notin E(G)$ since
otherwise $p\in W$ by the definition of $W$. Observe that since
$B_{v}\subseteq S$ we also have
$b^{v}_{i+\lfloor\ell/2\rfloor+3\ell^{*}(s-1)}\in S$. But since $pv\notin
E(G)$ we obtain from Claim 5 that
$\operatorname{dist}(z_{i},b^{v}_{i+\lfloor\ell/2\rfloor+3\ell^{*}(s-1)})\geq
s+1$ for $z_{i}=a_{i}$ or $z_{i}=c_{i}$, a contradiction. We conclude that $S$
does not contain any vertex $a^{p}_{i}$ or $c^{p}_{i}$ with $p\neq v$ or
$p\neq w_{j}$ for $j\in[t]$.

Next, assume towards a contradiction that $b^{p}_{i}\in S$ for some $p\in
V(G)$ with $p\neq v$ and $p\notin W$. If $pv\notin E(G)$, then $b^{p}_{i}$ and
$b^{v}_{i+\lfloor\ell/2\rfloor+3\ell^{*}(s-1)}$ have distance at least $s+1$
again by Claim 5. Thus, we can assume that $pv\in E(G)$. Recall that
$b^{v}_{i+\lfloor\ell/2\rfloor+3\ell^{*}(s-1)}\in S$. As defined by Claim 5,
each shortest path from $b^{p}_{i}$ to
$b^{v}_{i+\lfloor\ell/2\rfloor+3\ell^{*}(s-1)}$ can swap at most once between
different vertex gadgets. In this case, there is exactly one swap from $T^{p}$
to $T^{v}$. From the above we know that $(A_{p}\cup C_{p})\cap S=\emptyset$.
Thus, each shortest path from $b^{p}_{i}$ to
$b^{v}_{i+\lfloor\ell/2\rfloor+3\ell^{*}(s-1)}$ uses at least one vertex in
$A_{v}\cup C_{v}$. Since at least one edge with endpoint $A_{v}\cup C_{v}$ is
contained in $S$, we conclude from Lemma 8 that $A_{v}\cup C_{v}\subseteq S$,
a contradiction to the assumption $A_{v}\not\subseteq S$.

Hence, there is no vertex $p\neq v$ and $p\notin W$ such that $T^{p}\cap
S\neq\emptyset$. In other words, $S$ contains only vertices from the gadget
$T^{v}$ and from gadgets $T^{u}$ with $vu\in E(G)$. Thus, $S\subseteq
T^{v}\cup\bigcup_{j=1}^{t}T^{w_{j}}$. By definition of $k^{\prime}$, we have
$t\geq k-1$ and we conclude that $G$ contains a clique of size at least $k$.
The case that we have $B_{v}\cap S\neq\emptyset$ and $B_{v}\not\subseteq S$ or
$C_{v}\cap S\neq\emptyset$ and $C_{v}\not\subseteq S$ for some vertex $v\in
V(G)$ can be handled similarly.

Second, consider the case that for each set $A_{v}$ with $A_{v}\cap
S\neq\emptyset$ we have $A_{v}\subseteq S$, that for each set $B_{v}$ with
$B_{v}\cap S\neq\emptyset$ we have $B_{v}\subseteq S$ , and that for each set
$C_{v}$ with $C_{v}\cap S\neq\emptyset$ we have $C_{v}\subseteq S$. Let
$W_{A}\coloneqq\\{w_{A}^{j}\mid A_{w_{j}}\subseteq S\\}$,
$W_{B}\coloneqq\\{w_{B}^{j}\mid B_{w_{j}}\subseteq S\\}$ ,and
$W_{C}\coloneqq\\{w_{C}^{j}\mid C_{w_{j}}\subseteq S\\}$. If $W_{A}=\emptyset$
or $W_{B}=\emptyset$ or $W_{C}=\emptyset$then each connected component in
$G^{\prime}[S]$ has size at most $2(x+1)<k^{\prime}$. Thus, we may assume that
$W_{A}\neq\emptyset$, $W_{B}\neq\emptyset$ ,and $W_{C}\neq\emptyset$. By Claim
6, we have $w^{i}_{A}w^{j}_{B}\in E(G)$ for each $w^{i}_{A}\in W_{A}$ and
$w^{j}_{B}\in W_{B}$ and also $w^{i}_{C}w^{j}_{B}\in E(G)$ for each
$w^{i}_{C}\in W_{C}$ and $w^{j}_{B}\in W_{B}$. Furthermore, by Claim 5, we
have $w^{j}_{B}w^{j^{\prime}}_{B}\in E(G)$ for
$w^{j}_{B},w^{j^{\prime}}_{B}\in W_{B}$, $w^{i}_{A}w^{i^{\prime}}_{A}\in E(G)$
for $w^{i}_{A},w^{i^{\prime}}_{A}\in W_{A}$, $w^{i}_{C}w^{i^{\prime}}_{C}\in
E(G)$ for $w^{i}_{C},w^{i^{\prime}}_{C}\in W_{C}$, and also ,
$w^{i}_{A}w^{i^{\prime}}_{C}\in E(G)$ for $w^{i}_{A}\in W_{A}$ and
$w^{i^{\prime}}_{C}\in W_{C}$. Hence, we obtain that
$\min(|W_{A}|,|W_{B}|,|W_{C}|)\geq k$ and thus $G$ contains a clique of size
$k$. ∎

##  4 Seeded $s$-Club

In this section we study the parameterized complexity of Seeded $s$-Club with
respect to the standard parameter solution size $k$. Recall that is this
problem we aim to find an $s$-club containing a given seed of vertices. Here,
we assume that $|W|<k$ since otherwise the problem can be solved in polynomial
time.

###  4.1 Tractable Cases

For clique seeds, we provide the following kernel. Note that here we present a
kernel and not only a Turing kernel.

###### Theorem 4.1

Seeded $s$-Club admits a kernel with $\mathcal{O}(k^{2|W|+1})$ vertices if $W$
is a clique.

Note that this kernel has polynomial size if $W$ has constant size. In the
following, assume that $G[W]$ is a clique. To prove the kernel, we first
remove all vertices with distance at least $s+1$ to any vertex in $W$. Second,
we show that if the remaining graph, that is, $N_{s}[W]$, is sufficiently
large, then $(G,W,k)$ is a trivial yes-instance.

###### Reduction Rule 4.2

Let $(G,W,k)$ be an instance of Seeded $s$-Club. If $G$ contains a vertex $u$
such that $\operatorname{dist}(u,w)\geq s+1$ for some $w\in W$, then remove
$u$.

Clearly, Reduction Rule 4.2 is correct and can be applied in polynomial time.
Next, we show that if the remaining graph is sufficiently large then $(G,W,k)$
is a yes-instance of Seeded $s$-Club.

###### Lemma 9

An instance $(G,W,k)$ of Seeded $s$-Club with $|N_{s-1}[W]|\geq k^{2}$ is a
yes-instance.

To prove Lemma 9 for $s\geq 3$ we need the following technical lemmas.

###### Lemma 10

An instance $(G,W,k)$ of Seeded $s$-Club with $s\geq 3$ is a yes-instance if
$|N_{\lfloor(s+1)/2\rfloor-1}[W]|\geq k$.

###### Proof

By definition $W\subseteq N_{\lfloor(s+1)/2\rfloor-1}[W]$ and
$|N_{\lfloor(s+1)/2\rfloor-1}[W]|\geq k$. Thus, it remains to show that
$N_{\lfloor(s+1)/2\rfloor-1}[W]$ is an $s$-club. Therefore, consider a pair of
vertices $u,v\in N_{\lfloor(s+1)/2\rfloor-1}[W]$. Observe that by definition
$\operatorname{dist}(u,W)\leq\lfloor(s+1)/2\rfloor-1$ and
$\operatorname{dist}(v,W)\leq\lfloor(s+1)/2\rfloor-1$. Since $W$ is a clique,
we have
$\operatorname{dist}(u,v)\leq(\lfloor(s+1)/2\rfloor-1)+1+(\lfloor(s+1)/2\rfloor-1)\leq
s$. Hence, the lemma follows.∎

Note that the assumption $s\geq 3$ in Lemma 10 is necessary to guarantee that
$\lfloor(s+1)/2\rfloor-1\geq 1$. Next, we show that if a vertex in
$N_{\lfloor(s+1)/2\rfloor-1}(W)$ has many vertices close to it, then $(G,W,k)$
is a yes-instance.

###### Lemma 11

An instance $(G,W,k)$ of Seeded $s$-Club in which $s\geq 3$ and $|N_{\lfloor
s/2\rfloor}(v)|\geq k$ for some vertex $v\in N_{\lfloor(s+1)/2\rfloor-1}(W)$
is a yes-instance.

###### Proof

Let $v$ be a vertex as specified in the lemma. By definition of $v$, there
exists a path $P\coloneqq(q_{0},q_{1},\ldots,q_{\lfloor(s+1)/2\rfloor-1})$ of
length $\lfloor(s+1)/2\rfloor-1$ in $G$ such that
$q_{\lfloor(s+1)/2\rfloor-1}=v$, $w_{0}\in W$, and $q_{i}\in N_{i}(q_{0})$. We
show that $S\coloneqq N_{\lfloor s/2\rfloor}(v)\cup W\cup P$ is an $s$-club of
size $k$ containing $W$. Clearly, $W\subseteq S$ and $|S|\geq k$. Thus, it
remains to show that $S$ is an $s$-club.

Consider a vertex $w\in W$. Vertex $w$ has distance at most $i+1$ to vertex
$w_{i}$. In particular, $\operatorname{dist}(w,v)\leq\lfloor(s+1)/2\rfloor$.
Since each vertex $u\in N_{\lfloor s/2\rfloor}[v]$ has distance at most
$\lfloor s/2\rfloor$ to $v$ we obtain that
$\operatorname{dist}(w,u)\leq\lfloor(s+1)/2\rfloor+\lfloor s/2\rfloor=s$. By
similar arguments we can also show that vertex $w_{i}$ for
$i\in[\lfloor(s+1)/2\rfloor-1]$ has distance at most $s$ to each vertex in
$S$.

Finally, consider two vertices $x,y\in N_{\lfloor s/2\rfloor}[v]$. Note that
$\operatorname{dist}(x,v)\leq\lfloor s/2\rfloor$ and also
$\operatorname{dist}(y,v)\leq\lfloor s/2\rfloor$ and thus
$\operatorname{dist}(x,y)\leq s$.

Thus, $S$ is indeed an $s$-club.∎

With those two lemmas we are now able to prove Lemma 9.

######  Proof (Proof of Lemma 9)

First, we consider the case $s=2$. It is sufficient to show that $(G,W,k)$ is
a yes-instance if $|N[w]|\geq k$ for some $w\in W$ since $|W|\leq k$ and since
$N[W]\geq k^{2}$ by our assumption. Since all vertices in $N(w)$ have the
common neighbor $w$, we conclude that $N[w]$ is a $2$-club. Also, since $W$ is
a clique, we have $W\subseteq N[w]$. The size bound of $N_{s-1}[W]$ follows
from $|N[w]|\geq k$. Thus, $(G,W,k)$ is a yes-instance.

Second, we consider the case $s\geq 3$. Observe that

$N_{s-1}[W]=N_{\lfloor(s+1)/2\rfloor-1}[W]\cup\bigcup_{v\in
N_{\lfloor(s+1)/2\rfloor-1}[W]}N_{\lfloor s/2\rfloor}[v].$

By Lemma 10, $(G,W,k)$ is a yes-instance if
$|N_{\lfloor(s+1)/2\rfloor-1}[W]|\geq k$ and, by Lemma 11, $(G,W,k)$ is a yes-
instance if $|N_{\lfloor s/2\rfloor}(v)|\geq k$ for some $v\in
N_{\lfloor(s+1)/2\rfloor-1}(W)$. Thus, by the above equality we conclude that
$(G,W,k)$ is a yes-instance.∎

Finally, we bound the size of $N_{s}(W)$. There we assume that
$|N_{s-1}[W]|<k^{2}$ by Lemma 9 and that Reduction Rule 4.2 is applied.

###### Lemma 12

An instance $(G,W,k)$ of Seeded $s$-Club with $|N_{s}(W)|\geq k^{2|W|+1}$
which is reduced with respect to Reduction Rule 4.2 is a yes-instance.

###### Proof

Since Reduction Rule 4.2 has been applied exhaustively, each vertex $p\in
N_{s}(W)$ has distance exactly $s$ to each vertex in $W$. In other words, for
each vertex $w_{\ell}\in W$ there exists a vertex $u^{\ell}_{s-1}\in
N_{s-1}(w_{\ell})$ such that $pu^{\ell}_{s-1}\in E(G)$. Note that
$N_{s-1}(w_{\ell})\subseteq N_{s-1}[W]$. Moreover, by Lemma 9 we may assume
that $|N_{s-1}[W]|<k^{2}$. In particular: $|N_{s-1}(W)|<k^{2}$. Since
$|N_{s}(W)|\geq k^{2|W|+1}$, by the pigeonhole principle there exists a set
$\\{u^{1}_{s-1},u^{2}_{s-1},\ldots,u^{|W|}_{s-1}\\}$ with $u^{\ell}_{s-1}\in
N_{s-1}(w_{\ell})$ for $\ell\in[|W|]$ such that the set $P\coloneqq
N_{s}(W)\cap\bigcap_{\ell\in[|W|]}N(u^{\ell}_{s-1})$ has size at least $k$.
The size bound follows from the observation that each $N_{s-1}(w_{\ell})$ has
size at most $k^{2}$ and we have exactly $|W|$ many of these sets. By the
definition of vertex $u^{\ell}_{s-1}$, there exists for each $i\in[s-2]$ a
vertex $u_{i}^{\ell}\in N_{i}(w_{\ell})$ such that
$w_{\ell},u_{1}^{\ell},\ldots,u_{s-1}^{\ell}$ is a path of length $s-1$ in
$G$. We define the set
$U\coloneqq\\{u_{i}^{\ell}\mid\ell\in[|W|],i\in[s-1]\\}$. Next, we show that
$Z\coloneqq P\cup W\cup U$ induces an $s$-club.

First, observe that all vertices in $P$ have distance at most $2$ to each
other since they have the common neighbor $u^{1}_{s-1}$. Second, note that the
vertices $w_{\ell}$, $u^{\ell}_{1},\ldots,u^{\ell}_{s-1}$,
$p,u^{j}_{s-1},\ldots,u^{j}_{1},w_{j}$ form a cycle with $2s+1$ vertices, for
each $p\in P$ and each two indices $j,\ell\in[|W|]$. Each vertex in this cycle
has distance at most $s$ to each other vertex in that cycle. Hence, $Z$ is
indeed an $s$-club.∎

Recall that Lemma 9 showed that the number of vertices with distance _at most_
$s-1$ to $W$ is bounded by $k^{2}$. Together with Lemma 12 now Theorem 4.1 is
proven.

###  4.2 Intractable Cases

Now, we show hardness for some of the remaining cases.

###### Theorem 4.3

Let $H$ be a fixed graph. Seeded $s$-Club is W[1]-hard parameterized by $k$
even if $G[W]$ is isomorphic to $H$, when

  * •

$s=2$ and $H$ contains at least two non-adjacent vertices, or if

  * •

$s\geq 3$ and $H$ contains at least two connected components.

#### Hardness for $s=2$.

First, we prove hardness for $s=2$ when $H$ contains at least one non-edge.
For an illustration of Construction 4.4 we refer to Figure 3.

$x_{u}$$y_{u}$$z_{u}$$G_{u}$$x_{v}$$y_{v}$$z_{v}$$G_{v}$$p$$u^{*}$$v^{*}$$u$$v$$R$$W$
Figure 3: Illustration of Construction 4.4.

###### Construction 4.4

Let $(G,k)$ be an instance of Clique. We construct an equivalent instance
$(G^{\prime},k^{\prime})$ of Seeded $s$-Club as follows. Initially, we add the
set $W$ to $G^{\prime}$, and add edges such that $G^{\prime}[W]$ is isomorphic
to $H$. Since $H$ is not a clique, there exist two vertices $u,v\in V(H)$ such
that $uv\notin E(H)$. Let $R\coloneqq W\setminus\\{u,v\\}$. Next, we add two
copies $G_{u}$ and $G_{v}$ of $G$ to $G^{\prime}$, make $u$ adjacent to each
vertex in $V(G_{u})$, and make $v$ adjacent to each vertex in $V(G_{v})$. We
denote with $x_{u}$, and $x_{v}$ the copies of $x$ in $G_{u}$ and $G_{v}$,
respectively. Next, we add the edge $x_{u}x_{v}$ for each $x\in V(G)$.
Furthermore, we add a new vertex $p$ and make it adjacent to each vertex in
$W$. Next, we add a new vertex $u^{*}$ adjacent to $p$, each vertex in
$V(G_{u})$, and each vertex in $R$. Analogously, we add a new vertex $v^{*}$
which is adjacent to $p$, each vertex in $V(G_{v})$, and each vertex in $R$.
Finally, we set $k^{\prime}\coloneqq 2k+|W|+3$.

Now, we prove the correctness of Construction 4.4.

###### Lemma 13

For any graph $H$ which is not a clique, Seeded $2$-Club parameterized by $k$
is W[1]-hard if $G^{\prime}[W]$ is isomorphic to $H$.

###### Proof

We prove that $G$ contains a clique of size $k$ if and only if $G^{\prime}$
contains a $2$-club $S$ containing $W$ of size $k^{\prime}=2k+|W|+3$.

Let $K$ be a clique of size $k$ in $G$ and let $K_{u}$ and $K_{v}$ be the
copies of $K$ in $G_{u}$ and $G_{v}$. We argue that $S\coloneqq K_{u}\cup
K_{v}\cup W\cup\\{u^{*},v^{*},p\\}$ is a $2$-club of size at least
$k^{\prime}$ containing $W$. Clearly, $|S|=k^{\prime}$ and $S$ contains $W$.
Thus, it remains to show that $G[S]$ is a $2$-club.

First, we show that each vertex in $R$ has distance at most $2$ to each vertex
in $S$: All vertices in $R$ have the common neighbors $p$, $u^{*}$, and
$v^{*}$. Since $u$ and $v$ are neighbors of $p$, each vertex in $V(G_{u})$ is
a neighbor of $u^{*}$, and since each vertex in $V(G_{v})$ is a neighbor of
$v^{*}$ we conclude that each vertex in $R$ has distance at most $2$ to any
vertex in $S$.

Second, we show that each vertex in $K_{u}$ has distance at most $2$ to each
vertex in $S\setminus R$. Observe that $\\{u,u^{*},x_{v}\\}\cup K_{u}\subseteq
N[x_{u}]$ for each vertex $x_{u}\in K_{u}$. Hence, $x_{u}$ has distance at
most $2$ to $p$ via $u^{*}$, $v$, and $v^{*}$ via $x_{v}$, each vertex, and
each vertex in $K_{v}$ via the corresponding vertex in $K_{u}$. By symmetric
arguments the statement also holds for each vertex in $K_{v}$.

Finally, each pair of vertices of $\\{p,u,u^{*},v,v^{*}\\}$ has distance at
most $2$ to each other since $u,u^{*},v,v^{*}\in N(p)$.

Thus, $S$ is indeed a $2$-club.

Conversely, suppose that $G^{\prime}$ contains an $2$-club $S$ of size at
least $2k+|W|+3$ which contains all vertices of $W$. Observe that we have
$N(x_{u})\cap N(v)=\\{x_{v}\\}$ for each vertex $x_{u}\in V(G_{u})$, and
symmetrically $N(x_{v})\cap N(u)=\\{x_{u}\\}$ for each vertex $x_{v}\in
V(G_{v})$. Hence, $x_{u}\in S$ if and only if $x_{v}\in S$. Let
$K_{u}\coloneqq S\cap V(G_{u})$. By definition of $k^{\prime}$ we obtain that
$|K_{u}|\geq k$. Assume towards a contradiction that $K_{u}$ contains a pair
of nonadjacent vertices $x_{u}$ and $y_{u}$. By the argumentation above we
obtain $y_{v}\in S$. Now, observe that
$N(x_{u})=\\{u,u^{*},x_{v}\\}\cup\bigcup\\{z_{u}\mid xz\in E(G)\\}$ and that
$N(y_{v})=\\{v,v^{*},y_{u}\\}\cup\bigcup\\{z_{v}\mid yz\in E(G)\\}$. Since
$xy\notin E(G)$ we thus obtain $N(x_{u})\cap N(y_{v})=\emptyset$, a
contradiction. Thus, $G$ contains a clique of size $k$.∎

#### Hardness for seeds with at least two connected components and $s\geq 3$.

Now, we show W[1]-hardness for the case $s\geq 3$ when the seed contains at
least two connected components. Fix a graph $H$ with at least two connected
components. We show W[1]-hardness for $s\geq 3$ even if $G[W]$ is isomorphic
to $H$.

###### Construction 4.5

Let $(G,k)$ be an instance of Clique. We construct an equivalent instance
$(G^{\prime},k^{\prime})$ of Seeded $s$-Club as follows. Initially, we add the
set $W$ to $G^{\prime}$, and add edges such that $G^{\prime}[W]$ is isomorphic
to $H$. Let $D_{1}$ be one connected component of $G^{\prime}[W]$. By
assumption, $D_{2}\coloneqq W\setminus D_{1}$ is not empty. Next, we add two
copies $G_{1}$ and $G_{2}$ of $G$ to $G^{\prime}$. Then, we add edges to
$G^{\prime}$ such that each vertex in $D_{1}$ is adjacent to each vertex in
$V(G_{1})$ and such that each vertex in $D_{2}$ is adjacent to each vertex in
$V(G_{2})$. Furthermore, we add a path $(p_{1},\ldots,p_{s-1})$ consisting of
exactly $s-1$ new vertices to $G^{\prime}$, make $p_{1}$ adjacent to each
$u\in D_{1}$, and make $p_{s-1}$ adjacent to each $v\in D_{2}$. By
$P\coloneqq\\{p_{i}\mid i\in[s-1]\\}$ we denote the set of these newly added
vertices. Now, for each $x\in V(G)$ we do the following. Consider the copies
$x_{1}\in V(G_{1})$ and $x_{2}\in V(G_{2})$ of vertex $x\in V(G)$. We add a
path $(x_{1},q_{1}^{x},\ldots,q_{s-2}^{x},x_{2})$ consisting of $s-2$ new
vertices to $G^{\prime}$. By $Q_{x}\coloneqq\\{q^{x}_{i}\mid i\in[s-2]\\}$ we
denote the set of the new internal path vertices. Finally, we set
$k^{\prime}\coloneqq sk+|W|+s-1$.

Now, we prove the correctness of Construction 4.5.

###### Lemma 14

Let $H$ be a fixed graph with at least two connected components. Seeded
$s$-Club parameterized by $k$ is W[1]-hard even if $G[W]$ is isomorphic to
$H$.

###### Proof

We show that $G$ contains a clique of size $k$ if and only if $G^{\prime}$
contains a $W$-seeded $s$-club of size at least $k^{\prime}=sk+|W|+s-1$.

Let $K$ be a clique of size $k$ in $G$. Furthermore, let $K_{1}$ and $K_{2}$
denote the copies of $K$ in $G_{1}$ and $G_{2}$, respectively. We show that
$S\coloneqq W\cup P\cup K_{1}\cup K_{2}\cup\bigcup_{x\in K}Q_{x}$ is a
$W$-seeded $s$-club of size at least $k^{\prime}$. Clearly, $|S|=k^{\prime}$
and $S$ contains $W$. Thus, it remains to verify that $G[S]$ is an $s$-club.
Note that since each vertex in $V(G_{1})$ is adjacent to each vertex in
$D_{1}$, each two vertices in $D_{1}$ have distance at most $2$, and similarly
each two vertices in $V(G_{1})$ have distance at most $2$. Analogously, we can
show that each two vertices in $D_{2}$ and each two vertices in $V(G_{2})$
have distance at most $2$. Furthermore, the vertices
$(x,p_{1},p_{2},\ldots,p_{s-1},y,u_{2},q^{u}_{s-2},\ldots,q^{u}_{1},u_{1})$
for each vertex $x\in D_{1}$, each vertex $y\in D_{2}$, and each vertex $u\in
K$ form a $C_{2s+1}$, a cycle with $2s+1$ vertices. Observe that also the
vertices
$(u_{1},q^{u}_{1},\ldots,q^{u}_{s-2},u_{2},v_{2},q^{v}_{s-2},\ldots,q^{v}_{1},v_{1})$
form a $C_{2s}$ for each two vertices $u,v\in K$. Since all remaining
distances are covered by these two cycles, we conclude that $S$ is indeed an
$s$-club.

Conversely, suppose that $G^{\prime}$ contains a $W$-seeded $s$-club $S$ of
size at least $k^{\prime}$. Let
$Q^{\prime}_{v}\coloneqq\\{v_{1},q^{v}_{1},\ldots,q^{v}_{s-2},v_{2}\\}$ for
each $v\in V(G)$. We show that $Q^{\prime}_{v}\cap S\neq\emptyset$ if and only
if $Q^{\prime}_{v}\subseteq S$. Assume towards a contradiction, that
$Q^{\prime}_{v}\cap S\neq\emptyset$ for some $v\in V(G)$ such that
$Q^{\prime}_{v}\not\subseteq S$. If $v_{1}\notin S$, and also $v_{2}\notin S$,
then no vertex in $S\cap Q^{\prime}_{v}$ is connected to any vertex in
$S\setminus Q^{\prime}_{v}$. Hence, we can assume without loss of generality
that $v_{1}\in S$. Note that $N(D_{2})=V(G_{2})\cup\\{p_{s-1}\\}$.
Furthermore, observe that $\operatorname{dist}(v_{1},p_{s-1})=s$, that
$\operatorname{dist}(v_{1},q^{v}_{s-2})=s-2$, and that
$\operatorname{dist}(v_{1},q^{u}_{s-2})\geq s-1$ for each $u\in
V(G)\setminus\\{v\\}$. Thus, the unique path of length at most $s$ from
$v_{1}$ to $D_{2}$ contains all vertices in $Q^{\prime}_{v}$. Hence,
$Q^{\prime}_{v}\cap S\neq\emptyset$ if and only if $Q^{\prime}_{v}\subseteq
S$. By the definition of $k^{\prime}$ we may thus conclude that
$Q^{\prime}_{v}\subseteq S$ for at least $k$ vertices $v\in V(G)$.

Now, assume towards a contradiction that $Q^{\prime}_{u}\subseteq S$ and
$Q^{\prime}_{v}\subseteq S$ such that $uv\notin E(G)$. We consider the
vertices $v_{1}$ and $u_{2}$. Observe that by construction each path from
$v_{1}$ to $u_{2}$ containing any vertex $p_{i}$ has length at least $s+1$.
Hence, each shortest path from $v_{1}$ to $u_{2}$ contains the vertex set of
$Q^{\prime}_{w}$ for some $w\in V(G)$. Since the path induced by each
$Q^{\prime}_{w}$ has length $s-1$, we conclude that $w=u$ or $w=v$. Assume
without loss of generality that $w=v$. Hence, the $(s-1)$th vertex on the path
from $v_{1}$ is $v_{2}$. Since $uv\notin E(G)$ we have by construction that
$u_{2}v_{2}\notin E(G^{\prime})$. Hence, $\operatorname{dist}(v_{1},u_{2})\geq
s+1$, a contradiction to the fact that $S$ is an $s$-club. Thus, $\\{v\mid
Q^{\prime}_{v}\subseteq S\\}$ is a clique of size at least $k$ in $G$.∎

##  5 Conclusion

We provided a complexity dichotomy for Vertex Triangle $s$-Club and Edge
Triangle $s$-Club for the standard parameter solution size $k$ with respect to
$s$ and $\ell$. Furthermore, we also provided a complexity dichotomy for
Seeded $2$-Club for $k$ in terms of the structure of $G[W]$. For Seeded
$s$-Club with $s\geq 3$ we provided an FPT-algorithm with respect to $k$ when
$G[W]$ is a clique and we showed W[1]-hardness for $k$ when $G[W]$ contains at
least 2 connected components. Hence, an immediate open question is the
parameterized complexity of Seeded $s$-Club for $s\geq 3$ when $G[W]$ is
connected but not a clique. One aim should be to also provide a dichotomy for
$k$ for Seeded $s$-Club with $s\geq 3$ for all possible structures of $G[W]$.
It is particularly interesting to study seeds of constant size since this
seems to be the most interesting case for applications.

For future work, it seems interesting to study the complexity of the
considered variants of $s$-Club with respect to further parameters, for
example with respect to structural parameters of the input graph $G$ such as
the treewidth of $G$. Additionally, the parameterized complexity of further
robust variants of $s$-Club such as $t$-Hereditary $s$-Club [16, 14] with
respect to $k$ remains open. It is also interesting to study other problems
for detecting communities with seed constraints. One prominent example is
$s$-Plex. This problem is also NP-hard for $W\neq\emptyset$, since an
algorithm for the case when $|W|=1$ can be used as a black box to solve the
unseeded variants. From a practical perspective, we plan to implement
combinatorial algorithms for all three problem variants for the most important
special case $s=2$. Based on experience with previous implementations for
$2$-Club [10] and some of its robust variants [14] we are optimistic that
these problems can be solved efficiently on sparse real-world instances.

## References

  * [1] Almeida, M.T., Brás, R.: The maximum _l_ -triangle _k_ -club problem: Complexity, properties, and algorithms. Computers & Operations Research 111, 258–270 (2019)
  * [2] Balasundaram, B., Butenko, S., Trukhanov, S.: Novel approaches for analyzing biological networks. Journal of Combinatorial Optimization 10(1), 23–39 (2005)
  * [3] Bodlaender, H.L., Downey, R.G., Fellows, M.R., Hermelin, D.: On problems without polynomial kernels. Journal of Computer and System Sciences 75(8), 423–434 (2009)
  * [4] Bourjolly, J., Laporte, G., Pesant, G.: An exact algorithm for the maximum $k$-club problem in an undirected graph. European Journal of Operational Research 138(1), 21–28 (2002)
  * [5] Carvalho, F.D., Almeida, M.T.: The triangle $k$-club problem. Journal of Combinatorial Optimization 33(3), 814–846 (2017)
  * [6] Chang, M., Hung, L., Lin, C., Su, P.: Finding large $k$-clubs in undirected graphs. Computing 95(9), 739–758 (2013)
  * [7] Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer (2015)
  * [8] Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Texts in Computer Science, Springer (2013)
  * [9] Golovach, P.A., Heggernes, P., Kratsch, D., Rafiey, A.: Finding clubs in graph classes. Discrete Applied Mathematics 174, 57–65 (2014)
  * [10] Hartung, S., Komusiewicz, C., Nichterlein, A.: Parameterized algorithmics and computational experiments for finding 2-clubs. Journal of Graph Algorithms and Applications 19(1), 155–190 (2015)
  * [11] Hartung, S., Komusiewicz, C., Nichterlein, A., Suchý, O.: On structural parameterizations for the 2-club problem. Discrete Applied Mathematics 185, 79–92 (2015)
  * [12] Kanawati, R.: Seed-centric approaches for community detection in complex networks. In: Proceedings of the 6th International Conference on Social Computing and Social Media (SCSM ’14). Lecture Notes in Computer Science, vol. 8531, pp. 197–208. Springer (2014)
  * [13] Komusiewicz, C.: Multivariate algorithmics for finding cohesive subnetworks. Algorithms 9(1), 21 (2016)
  * [14] Komusiewicz, C., Nichterlein, A., Niedermeier, R., Picker, M.: Exact algorithms for finding well-connected 2-clubs in sparse real-world graphs: Theory and experiments. European Journal of Operational Research 275(3), 846–864 (2019)
  * [15] Mokken, R.J., et al.: Cliques, clubs and clans. Quality & Quantity 13(2), 161–173 (1979)
  * [16] Pattillo, J., Youssef, N., Butenko, S.: On clique relaxation models in network analysis. European Journal of Operational Research 226(1), 9–18 (2013)
  * [17] Schäfer, A., Komusiewicz, C., Moser, H., Niedermeier, R.: Parameterized computational complexity of finding small-diameter subgraphs. Optimization Letters 6(5), 883–891 (2012)
  * [18] Veremyev, A., Boginski, V.: Identifying large robust network clusters via new compact formulations of maximum $k$-club problems. European Journal of Operational Research 218(2), 316–326 (2012)
  * [19] Whang, J.J., Gleich, D.F., Dhillon, I.S.: Overlapping community detection using seed set expansion. In: Proceedings of the 22nd ACM International Conference on Information and Knowledge Management (CIKM ’13). pp. 2099–2108. ACM (2013)
  * [20] Yezerska, O., Pajouh, F.M., Butenko, S.: On biconnected and fragile subgraphs of low diameter. European Journal of Operational Research 263(2), 390–400 (2017)