The parameterized complexity of finding secluded solutions to some classical
optimization problems on graphs✩
René van Beverna,b,1, Till Fluschnikc,2 , George B. Mertziosd, Hendrik Molterc,3 , Manuel Sorgec,e,4,
Ondřej Suchýf,5
a

Novosibirsk State University, Novosibirsk, Russian Federation,
Sobolev Institute of Mathematics of the Siberian Branch of the Russian Academy of Sciences, Novosibirsk,
Russian Federation
c
Institut für Softwaretechnik und Theoretische Informatik, TU Berlin, Germany,
d
School of Engineering and Computing Sciences, Durham University, Durham, UK,
Department of Industrial Engineering and Management, Ben-Gurion University of the Negev, Be’er Sheva, Israel
f
Faculty of Information Technology, Czech Technical University in Prague, Prague, Czech Republic

arXiv:1606.09000v4 [cs.CC] 1 Jun 2017

b

e

Abstract
This work studies the parameterized complexity of ﬁnding secluded solutions to classical combinatorial optimization problems on graphs such as ﬁnding minimum s-t separators, feedback vertex sets, dominating
sets, maximum independent sets, and vertex deletion problems for hereditary graph properties: Herein, one
searches not only to minimize or maximize the size of the solution, but also to minimize the size of its
neighborhood. This restriction has applications in secure routing and community detection.
Keywords:
Neighborhood, Feedback Vertex Set, Vertex Deletion, Separator, Dominating Set

1. Introduction
In many optimization problems on graphs, one searches for a minimum or maximum cardinality subset
of vertices and edges satisfying certain properties, like a shortest s-t path, a maximum independent set, or a
minimum dominating set. Chechik et al. [12] ﬁrst studied the problem of ﬁnding secluded solutions, which
additionally limit the exposure of the solution as measured by the size of the neighborhood. They motivate
these problems by protecting sensitive information that is sent through a network and potentially intercepted
by neighbors of its travel path. However, given that there are eﬀective means of encrypting and signing
sensitive information, the following application seems more realistic: a convoy travelling from a vertex s to
a vertex t along an s-t path in a transportation network can potentially be attacked from roads incident
to this path. Thus, one arrives at the problem of ﬁnding an s-t path with a small closed neighborhood.
✩ A preliminary version of this work appeared in the proceedings of IPEC 2016 [5]. This version provides full proof details
and additionally shows that Small Secluded s-t-Separator is ﬁxed-parameter tractable parameterized by the combination
of the solution size and the open neighborhood size (Theorem 3.5).
Email addresses: rvb@nsu.ru (René van Bevern), till.fluschnik@tu-berlin.de (Till Fluschnik),
george.mertzios@durham.ac.uk (George B. Mertzios), h.molter@tu-berlin.de (Hendrik Molter), sorge@post.bgu.ac.il
(Manuel Sorge), ondrej.suchy@fit.cvut.cz (Ondřej Suchý)
1 Results in Section 5 were obtained under support of the Russian Science Foundation, grant 16-11-10041.
2 Supported by the DFG, project DAMM (NI 369/13).
3 Supported by the DFG, project DAPA (NI 369/12).
4 Supported by the People Programme (Marie Curie Actions) of the European Union’s Seventh Framework Programme
(FP7/2007-2013) under REA grant agreement number 631163.11 and by the Israel Science Foundation (grant no. 551145/14).
5 Supported by grant 17-20065S of the Czech Science Foundation.

Another motivation for limiting the exposure of solutions is the search for segregated communities in social
networks [31]. Herein, we search for dense subgraphs that are exposed to few neighbors in the rest of the
graph. The constrained exposure models the concept of inter-cluster sparsity, which states that communities
have weak connections to the rest of the network [26]. In addition to being a natural constraint in the above
applications, restricting the exposure of the solution may also yield more eﬃcient algorithms [28, 30, 31, 33].
Chechik et al. [12] and Fomin et al. [25] previously studied secluded paths and Steiner trees, respectively.
Our aim in this paper is to study the classical and parameterized complexity of secluded variants of classical
combinatorial optimization problems in graphs.
Following Chechik et
S al. [12], we measure the exposure of a solution S by the size of the closed neighborhood NG [S] = S ∪ v∈S NG (v) of S in the input graph G. Given a predicate Π(G, S) that determines
whether S is a solution for input graph G, we study the following general problem.
Problem (Secluded Π).
Input: A graph G = (V, E) and an integer k.
Question: Is there a vertex subset S ⊆ V such that S satisﬁes Π(G, S) and |NG [S]| ≤ k?
In some cases, it may be necessary to control the size of the solution and its neighborhood independently:
For example, when routing a convoy from s to t as above, we may simultaneously aim to minimize its travel
time, that is, the number of vertices on its route, and to limit the exposure. Hence, another measure for the
exposure of the solution is the size of the open neighborhood NG (S) = NG [S] \ S. We thus introduce and
study the complexity of the following problem.
Problem (Small (Large) Secluded Π).
Input: A graph G = (V, E) and two integers k, ℓ.
Question: Is there a vertex subset S ⊆ V such that S satisﬁes Π(G, S), |S| ≤ k, and |NG (S)| ≤ ℓ (or
|S| ≥ k, and |NG (S)| ≤ ℓ, respectively)?
Our contributions. We study Secluded Π and Small Secluded Π in the framework of parameterized
complexity, a framework allowing for a ﬁne-grained complexity analysis and for proving the eﬀectivity of
polynomial-time data reduction (we give formal deﬁnitions in Section 2): a problem is fixed-parameter
tractable with respect to some parameter k if it can be solved in f (k) · nO(1) time, where n is the input size.
Thus, for small parameters k, ﬁxed-parameter algorithms can potentially lead to eﬃcient algorithms for NPhard problems. In contrast, if a problem is W[1]-hard with respect to a parameter k, then it is presumably
not ﬁxed-parameter tractable with respect to that parameter. Our results are summarized in Table 1.
We analyze the impact of the parameter k on the complexity of Secluded Π and the impact of the
parameters k and ℓ on the complexity of Small Secluded Π. The predicates Π(G, S) that we study are
– s-t Separator,
– Feedback Vertex Set (FVS),
– F -free Vertex Deletion (F -FVD) (for an arbitrary ﬁnite family F of graphs), encompassing
Cluster Vertex Deletion, for example, and
– Independent Set (IS).
Perhaps surprisingly, we ﬁnd that Secluded s-t-Separator is polynomial-time solvable, whereas Small
Secluded s-t Separator is NP-complete. The remaining secluded problem variants are NP-complete.
For them, roughly speaking, we prove that ﬁxed-parameter tractability results for Π parameterized by the
solution size carry over to Secluded Π parameterized by the closed neighborhood size k. For Small
Secluded Π parameterized by the open neighborhood size ℓ, however, we mostly obtain W[1]-hardness.
On the positive side, for Small Secluded F -FVD and Small Secluded s-t-Separator, we prove
ﬁxed-parameter tractability when parameterized by k + ℓ.
We also study, for two integers p < q, the p-secluded version of q-Dominating Set (q-DS): a vertex
set S is a q-dominating set if every vertex of V \ S has distance at most q to some vertex in S. Herein, by
2

Complexity
Secluded
Small Secl.

Parameterized Complexity / Kernelization
Secluded
Small Secl.
k
k
ℓ
k+ℓ
P

Problem
s-t Separator

q-Dom. Set,
2p ≤ q
q-Dom. Set,
2p > q

P

NP-c.

(Thm. 3.1)

(Thm. 3.4)

NP-c.

NP-c.*

(Thm. 4.3)

NP-c.

NP-c.

Feedback
Vertex Set

NP-c.

Independent Set

W[1]-h.

FPT/noPK

(Thm. 3.4)

(Thm. 3.4)

(Thm. 3.5/Thm. 3.8)

→

→

W[2]-h.

(Thm. 4.4)

NP-c.*

(Thm. 4.3)

F -free
Vertex Deletion

W[2]-h.

W[1]-h.

FPT/noPK

(Cor. 4.7)

W[2]-h.*

?

(Cor. 4.9/Thm. 4.3)

NP-c.*

(Thm. 5.1)

FPT/PK

(Cor. 4.7/Thm. 4.8)

?

?

(Thm. 5.2)

NP-c.*

(Thm. 6.1)

FPT/PK
(Thm. 6.2)

Large Secl.
NP-c.*

FPT/noPK

FPT/?
(Thm. 5.7)

?

W[1]-h.

? /?

(Thm. 6.14)

Large Secl.
→
→

W[1]-h.
(Thm. 7.1)

Table 1: Overview of our results. PK stands for polynomial kernel. The results marked by an asterisk follow by a straightforward
reduction from the non-secluded variant. The complexity for combinations marked by an arrow are resolved by a stronger result
in a farther column.

p-secluded we mean that we upper bound the size of the distance-p-neighborhood of the solution S. This
problem admits a complexity dichotomy: Whenever 2p > q, (Small) p-Secluded q-Dominating Set is
ﬁxed-parameter tractable with respect to k (with respect to k + ℓ), but it is W[2]-hard otherwise.
Finally, we also study the possibility for eﬀective polynomial-time data reduction. We observe that the
polynomial-size problem kernels for Feedback Vertex Set and F -free Vertex Deletion carry over to
their Secluded variants, but otherwise we obtain mostly absence of polynomial-size problem kernels unless
the polynomial hierarchy collapses.
Related work. Secluded Path and Secluded Steiner Tree were introduced and proved NP-complete
by Chechik et al. [12]. They obtained approximation algorithms for both problems with approximation
factors related to the maximum degree. They also showed that Secluded Path is ﬁxed-parameter tractable
with respect to the maximum vertex degree of the input graph, whereas vertex weights lead to NP-hardness
for maximum degree four.
Fomin et al. [25] studied the parameterized complexity of Secluded Path and Secluded Steiner
Tree, showing that both are ﬁxed-parameter tractable even in the vertex-weighted setting. Furthermore,
they showed that Secluded Steiner Tree is ﬁxed-parameter tractable with respect to k − s + p, where p
is the number of terminals, k is the desired size of the closed neighborhood of the solution, and s is the size
of an optimum Steiner tree. On the other hand this problem is co-W[1]-hard when parameterized by k − s
only [25].
The small secluded concept can be found in the context of separator problems in graphs [24, 36]. Marx [36]
introduced the Cutting k Vertices problem, which asks, given a graph G = (V, E) and two integers k ≥ 1
and ℓ ≥ 0, whether there is a non-empty set S ⊆ V such that |S| ≤ k and |NG (S)| = ℓ. It follows from the
work of Bui and Jones [8] that the problem is NP-hard and Marx [36] proved that the problem is W[1]-hard
with respect to k + ℓ. Moreover, for the problem variant where the set S is required to induce a connected
3

subgraph in G, he proved that it becomes ﬁxed-parameter tractable when parameterized by k + ℓ, while
staying W[1]-hard with respect to k or ℓ. Fomin et al. [24] studied the variant of Cutting k Vertices
where |NG (S)| ≤ ℓ, thus resembling our small secluded concept. They proved that this variant is W[1]hard with respect to k, but becomes ﬁxed-parameter tractable when parameterized by ℓ. As to the latter,
we remark that for none of our studied small secluded problems we observed ﬁxed-parameter tractability
with respect to ℓ. Somewhat surprisingly, if it is additionally required that S has to contain a predeﬁned
vertex s ∈ V , then this variant becomes W[1]-hard with respect to ℓ while staying ﬁxed-parameter tractable
when parameterized by k + ℓ [24].
The concept of isolation states that the solution should have few edges to the rest of the graph and
was originally introduced for ﬁnding cliques [31]. Isolation was subsequently explored also for more general
deﬁnitions of dense subgraphs [28, 30, 31, 33]. Herein, chieﬂy the constraint that the vertices in the solution
shall have maximum/minimum/average outdegree bounded by a parameter was considered [28, 31, 33],
leading to various parameterized tractability and hardness results. Also the overall number of edges outgoing
the solution has been studied recently [30]. Finding isolated vertices without constraint on their topology
was already studied by Downey et al. [17].
Small Secluded Π and Large Secluded Π can be seen as special cases of Fixed Cardinality
Optimization [7, 10, 11, 32]. Hence, we can derive some corollaries for secluded problems from results from
the literature on Fixed Cardinality Optimization, see below.
Preliminary observations. Concerning the classical computational complexity, the Small (Large) Secluded variant of a problem is at least as hard as the nonsecluded problem, by a simple reduction in which
we set ℓ = n, where n denotes the number of vertices in the graph. Since this reduction is a parameterized
reduction with respect to k, parameterized hardness results for this parameter transfer, too. Furthermore,
observe that hardness also transfers from Secluded Π to Small Secluded Π for all problems Π, since
Secluded Π allows for a parameterized Turing reduction to Small Secluded Π: try out all k ′ and ℓ′
with k = k ′ + ℓ′ . Additionally, many tractability results (in particular polynomial time solvability and
ﬁxed-parameter tractability) transfer from Small Secluded Π parameterized by (k + ℓ) to Secluded Π
parameterized by k.
Observation 1.1. Secluded Π parameterized by k is parameterized Turing reducible to Small Secluded
Π parameterized by (k + ℓ) for all predicates Π.
Therefore, for the Small (Large) Secluded variants of the problems the interesting cases are those where
the base problem is tractable (deciding whether input graph G contains a vertex set S of size k that satisﬁes
Π(G, S)) or where the size ℓ of the open neighborhood is a parameter.
Small Secluded Π can be solved using techniques for Fixed Cardinality Optimization [7, 10],
where we are given an objective function φ over subsets of some universe (usually via an oracle or eﬃcient
algorithm) and we seek to optimize it over all k-element subsets: Deﬁne the universe as the vertex set in
the input graph, and set φ(S) = ∞ whenever Π(G, S) is not satisﬁed. Otherwise φ(S) = |N (S)|. Iterating
over all i = 1, . . . , k, minimizing φ for i-vertex subgraphs, and checking whether a solution S with φ(S) ≤ ℓ
exists thus solves Small Secluded Π.
In Small Secluded Π no vertex of degree greater than k + ℓ can be part of the solution. Hence, the
above formulation makes Small Secluded Π amenable to the random separation framework for Fixed
Cardinality Optimization in graphs with bounded degree [11]: Roughly, we can restrict the domain
of φ to the set of vertices of degree smaller than k + ℓ, eﬀectively removing large-degree vertices from the
graph, while their contribution to satisfying Π and to the neighborhoods of other vertices is still present in φ.
Applying then a ﬁxed-parameter algorithm with respect to the maximum degree for Fixed Cardinality
Optimization given by Cai et al. [11, Theorem 4], we can thus derive ﬁxed-parameter algorithms with
respect to k + ℓ for some Small Secluded Π problems. Herein, Π(G, S) must be computable in ﬁxedparameter time and fulﬁll certain conditions which roughly state that subgraphs of G that fulﬁll Π and have
a certain distance from each other in G can be combined via the disjoint union into one subgraph fulﬁlling Π.
For example, ﬁnding secluded subgraphs of ﬁxed minimum degree, subgraphs of even degree, subgraphs that
induce matchings, and subgraphs of ﬁxed diameter is ﬁxed-parameter tractable with respect to k + ℓ through
4

that approach. Furthermore, as a special case we obtain that, if Π(G, S) is ﬁxed-parameter tractable with
respect to k + ℓ and each vertex subset S satisfying Π(G, S) is connected, then Small Secluded Π is
ﬁxed-parameter tractable with respect to k + ℓ.
Note that a similar strategy as above does not work for Large Secluded Π, because we cannot bound
the maximum degree in the same fashion: Neighbors of a solution vertex may be taken into the (arbitrarily
large) solution to keep the neighborhood of the solution small.
Organization. We give basic deﬁnitions from graph theory and parameterized complexity theory in Section 2.
Each of the subsequent sections is dedicated to one of the studied problems. We study s-t-Separator in
Section 3, q-Dominating Set in Section 4, F -free Vertex Deletion in Section 5, Feedback Vertex
Set in Section 6, and Independent Set in Section 7. Section 8 summarizes results and gives directions
for future research.
2. Preliminaries
We use standard notions from parameterized complexity [14, 18, 22, 39] and graph theory [15, 42]. We
use [p] to denote the set {1, . . . , p}.
Graph theory. Let G = (V, E) be an undirected graph (all graphs in this paper are undirected). We denote
by V (G) the vertex set of G and by E(G) the edge set of G. For a vertex set W ⊆ V (G) (edge set F ⊆ E(G)),
we denote by G[W ] (G[F ]) the subgraph of G induced by the vertex set W (edge set F ), respectively. We
also denote by G − W the graph G[V (G) \ W ].
A graph with vertex set {v0 , . . . , vx } and edge set {{vi−1 , vi } | i ∈ [x]} is called a path (with endpoints
v0 and vx , also referred to as v0 -vx path). The length of a path is the number of edges. A graph with vertex
set {v0 , . . . , vx } and edge set {{vi−1 , vi } | i ∈ [x]} ∪ {vx , v0 } is called a cycle (of length x + 1).
We denote dG (u, v) the distance between vertices u and v in G, that is, the number of edges of a
shortest u-v path in G. For a set V ′ of vertices and a vertex v ∈ V we let the distance of v from V ′ be
d
d
d
dG (v, V ′ ) := min{dG (u, v) | u ∈ V ′ }. We use NG
[V ′ ] = {v | dG (v, V ′ ) ≤ d} and NG
(V ′ ) = NG
[V ′ ] \ V ′ for
0
′
any d ≥ 0 (hence NG (V ) = ∅). We omit the index if the graph is clear from context and also use N [V ′ ]
for N 1 [V ′ ] and N (V ′ ) for N 1 (V ′ ). If V ′ = {v}, then we write N d [v] in place of N d [{v}]. The diameter of a
graph G is the maximum distance between v and w over all v, w ∈ V (G).
A subset V ′ ⊆ V (G) is called an s-t separator in G for two distinct vertices s and t if there is no s-t path
in G − V ′ . An s-t separator V ′ is called minimal if for all V ′′ ( V ′ holds that there is an s-t path in G − V ′′ .
Parameterized complexity. Parameterized complexity has been introduced to more eﬀectively but optimally
solve NP-hard problems: one accepts the apparently inevitable combinatorial explosion in algorithms for
NP-hard problems, yet decouples it from the input size and limits it to one aspect of the problem—some
small parameter. The instances (x, k) of a parameterized problem P ⊆ Σ∗ × N consist of an input x and a
parameter k. A parameterized problem P is fixed-parameter tractable (FPT) if, for every (x, k) ∈ Σ∗ × N, it
can be decided in f (k) · |x|O(1) time whether (x, k) ∈ P , where f is an arbitrary computable function only
depending on k. The ﬁxed-parameter tractable parameterized problems form the parameterized complexity
class FPT.
Parameterized complexity provides means to show intractability: There is a hierarchy of parameterized
complexity classes FPT ⊆ W[1] ⊆ W[2] ⊆ · · · ⊆ W[P], where all inclusions are conjectured to be strict. A
parameterized reduction from parameterized problem P1 to parameterized problem P2 is an algorithm that
maps an instance (x, k) of P1 to an instance (x′ , k ′ ) of P2 in time f (k) · poly(|x|) such that (x, k) and (x′ , k ′ )
are equivalent and k ′ ≤ g(k), where f and g are arbitrary computable functions only depending on k. We say
that an instance (x, k) of parameterized problem P1 is equivalent with an instance (x′ , k ′ ) of parameterized
problem P2 if (x, k) ∈ P1 ⇐⇒ (x′ , k ′ ) ∈ P2 . A polynomial-parameter transformation is a parameterized
reduction for which both f and g are polynomial. Note that such a reduction is also a polynomial-time
many-one reduction from P1 to P2 considered in classical complexity theory (also called Karp reduction). A
5

parameterized problem P2 is W[t]-hard if there is a parameterized reduction from each problem P1 ∈ W[t]
to P2 . No W[t]-hard problem is ﬁxed-parameter tractable unless FPT = W[t].
A parameterized Turing reduction from parameterized problem P1 to parameterized problem P2 is an
algorithm that decides whether (x, k) ∈ P1 in f (k) · |x|O(1) time if it is provided with access to an oracle that
can decide instances (x′ , k ′ ) of P2 with k ′ ≤ g(k) in constant time. Here f and g are arbitrary computable
functions only depending on k.
Problem kernelization. Parameterized complexity introduced the concept of kernelization to measure the
eﬀect of polynomial-time data reduction. A kernelization is a polynomial-parameter transformation of a
parameterized problem P to itself, transforming an instance (x, k) of P into an instance (x′ , k ′ ) (the kernel ),
such that |x′ | + k ′ ≤ f (k) for some computable function f only depending on k. We call f the size of
the kernel. If f ∈ k O(1) , then we say that P admits a polynomial-size kernel. A decidable parameterized
problem is ﬁxed-parameter tractable if and only if it admits a kernel [14].
Using the following cross-composition method, one can show that a problem does not have polynomialsize kernels unless the polynomial-time hierarchy collapses to the third level.
An equivalence relation R on the instances of some problem L is a polynomial equivalence relation if
(i) one can decide for any two instances in time polynomial in their sizes whether they belong to the same
equivalence class, and
(i) for any ﬁnite set S of instances, R partitions the set into at most (maxx∈S |x|)O(1) equivalence classes.
An OR-cross-composition of an NP-hard problem L into a parameterized problem P (with respect to a
polynomial equivalence relation R on the instances of L) is an algorithm that takes ℓ R-equivalent inP
stances x1 , . . . , xℓ of L and constructs in time polynomial in ℓi=1 |xi | an instance (x, k) of P such that
– k is polynomially upper-bounded in max1≤i≤ℓ |xi | + log(ℓ) and
– (x, k) ∈ P if and only if there is at least one ℓ′ ∈ [ℓ] such that xℓ′ ∈ L.
If an NP-hard problem L OR-cross-composes into a parameterized problem P , then P does not admit a
polynomial-size kernel, unless NP ⊆ coNP/ poly [14], which would cause a collapse of the polynomial-time
hierarchy to the third level.
3. s-t-Separator
In this section, we show that Secluded s-t-Separator is in P, while Small Secluded s-t-Separator
is NP-hard and W [1]-hard with respect to the size of the open neighborhood and with respect to the size of
the solution. Moreover, we show that, parameterized by the sum of the sizes of the open neighborhood and
the solution, the problem is ﬁxed-parameter tractable yet does not allow for polynomial-size kernels.
3.1. Secluded s-t-Separator
In this subsection we show that the following problem can be solved in polynomial time.
Problem (Secluded s-t-Separator).
Input: A graph G = (V, E), two distinct vertices s, t ∈ V , and an integer k.
Question: Is there an s-t separator S ⊆ V \ {s, t} such that |NG [S]| ≤ k?
Theorem 3.1. Secluded s-t-Separator can be solved in polynomial time.
In order to prove Theorem 3.1, we show that it is enough to compute a separator of size k in the third
power of a graph that is obtained from G by adding two new terminals to s and t:
Definition 3.2. For x ∈ N the x-th power of a graph G = (V, E) is a graph G′ = (V, E ′ ) where for each
pair of distinct vertices u, v ∈ V we have {u, v} ∈ E ′ if and only if dG (u, v) ≤ x.
6

That is, the x-th power of a graph G is obtained by adding edges between vertices that are at distance
at most x in G. This can be done in polynomial time.
Lemma 3.3. Let G = (V, E) be an undirected graph with two distinct vertices s, t ∈ V . Let G′′ be the graph
obtained from G by adding two vertices s′ , t′ and two edges {s′ , s}, {t, t′ }. Then there is an s-t-separator S
in G with |N [S]| ≤ k if and only if there is an s′ -t′ -separator S ′ with |S ′ | ≤ k in the third power G′ of G′′ .
Proof. (⇒) Let S be an s-t-separator in G with |N [S]| ≤ k. Observe that S then also constitutes an s′ -t′ separator in G′′ as every path in G′′ from s′ must go through s and every path to t′ must go through t.
We claim that S ′ = N [S] is an s′ -t′ -separator in G′ . Suppose for contradiction that there is an s′ -t′ path
P = p0 , p1 , . . . , pq in G′ −S ′ . Let A′ be the set of vertices of the connected component of G′′ −S containing s′
and let a be the largest index such that pa ∈ A′ (note that p0 = s′ ∈ A′ and pq = t′ ∈
/ A′ by deﬁnition).
′
′
′
′′
It follows that pa+1 ∈
/ A and, since {pa , pa+1 } ∈ E , there is a pa -pa+1 path P in G of length at most
three. As we have pa ∈ A′ and pa+1 ∈ V \ (A′ ∪ S ′ ) and G[A′ ] is a connected component of G′′ − S, there
must be a vertex x of S on P ′ . Since neither pa nor pa+1 is in S ′ = N [S], it follows that dG (pa , x) ≥ 2 and
dG (pa+1 , x) ≥ 2. This contradicts P ′ having length at most 3.
(⇐) Let S ′ be an s′ -t′ -separator in G′ of size at most k. Let A′ be the vertex set of the connected
component of G′ − S ′ containing s′ . Consider the set S = {v ∈ S ′ | dG′′ (v, A′ ) = 2}. We claim that S is an
s-t-separator in G and, moreover, that N [S] ⊆ S ′ and, hence, |N [S]| ≤ k. As to the second part, we have
S ⊆ S ′ by deﬁnition. Suppose for contradiction that there was a vertex u ∈ N (S) \ S ′ that is a neighbor of
v ∈ S. Then, since dG′′ (v, A′ ) = 2, we have dG′′ (u, A′ ) ≤ 3, meaning that u has a neighbor in A′ in G′ , and,
thus u is in A′ . This implies that dG′′ (v, A′ ) = 1, a contradiction. Hence, |N [S]| ≤ k.
It remains to show that S is an s-t-separator in G. For this, we prove that S is an s′ -t′ -separator in
′′
G . Since it contains neither s nor t, it follows that it must be also an s-t-separator in G. Assume for
contradiction that there is an s′ -t′ path in G′′ − S. This implies that d(G′′ −S) (t′ , A′ ) is well deﬁned (and
ﬁnite). Let q := d(G′′ −S) (t′ , A′ ) and let P be a corresponding shortest path in G′′ − S. Let us denote
P = p0 , . . . , pq with pq = t′ and p0 ∈ A′ . If dG′′ (t′ , A′ ) ≤ 3, then t′ has a neighbor in A′ in G′ , and therefore
it is in A′ contradicting our assumption that S ′ is an s′ -t′ -separator in G′ . As t′ = pq , we have q > 3. Since
dG′′ (p0 , A′ ) = 0, dG′′ (pq , A′ ) > 3, and dG′′ (pi+1 , A′ ) ≤ dG′′ (pi , A′ ) + 1 for every i ∈ {0, . . . q − 1}, there is
an a such that dG′′ (pa , A′ ) = 2. Note that each vertex v with dG′′ (v, A′ ) ≤ 3 is either in A′ or in S ′ . If
pa is not in S ′ , then pa is in A′ , contradicting our assumptions on P and q as a ≥ 2. Therefore we have
dG′′ (pa , A′ ) = 2 and pa is in S ′ . It follows that pa is in S, a contradiction.
As a minimum s-t separator can be computed in polynomial time using standard methods, for example,
based on network ﬂows, Theorem 3.1 follows immediately from Lemma 3.3.
3.2. Small Secluded s-t-Separator
In this subsection we prove hardness and tractability results for the following problem.
Problem (Small Secluded s-t-Separator).
Input: A graph G = (V, E), two distinct vertices s, t ∈ V , and two integers k, ℓ.
Question: Is there an s-t separator S ⊆ V \ {s, t} such that |S| ≤ k and |NG (S)| ≤ ℓ?
We show that, in contrast to Secluded s-t-Separator, the above problem is NP-hard. Moreover, at the
same time, we show parameterized hardness with respect to k and with respect to ℓ. Later, however, we
will show a ﬁxed-parameter algorithm for the combined parameter k + ℓ.
Theorem 3.4. Small Secluded s-t-Separator is NP-hard and W [1]-hard when parameterized by k or
by ℓ.
In the proof of the theorem, we reduce from the Cutting at Most k Vertices with Terminal [24]
problem, which asks, given a graph G = (V, E), a vertex s ∈ V , and two integers k ≥ 1, ℓ ≥ 0, whether
there is a set S ⊆ V such that s ∈ S, |S| ≤ k, and |NG (S)| ≤ ℓ. Fomin et al. [24] proved that Cutting at
Most k Vertices with Terminal is NP-hard and W[1]-hard when parameterized by k or by ℓ.
7

Proof. We give a polynomial-parameter transformation from Cutting at Most k Vertices with Terminal to Small Secluded s-t-Separator.
Construction. Let I := (G = (V, E), s, k, ℓ) be an instance of Cutting at Most k Vertices with
Terminal. We construct an instance I ′ := (G′ , s′ , t′ , k ′ , ℓ′ ) of Small Secluded s-t-Separator equivalent
to I as follows. To obtain G′ from G we add to G two vertices s′ and t′ and two edges {s′ , s} and {s, t′ }. Note
that G = G′ − {s′ , t′ }. We set k ′ = k and ℓ′ = ℓ + 2. Hence, we ask for an s′ -t′ separator S ⊆ V (G′ ) \ {s′ , t′ }
in G′ of size at most k ′ with |NG′ (S)| ≤ ℓ′ . Clearly, the construction can be carried out in polynomial time.
Correctness. We show that I is a yes-instance of Cutting at Most k Vertices with Terminal if
and only if I ′ is a yes-instance of Small Secluded s-t-Separator.
(⇒) Let I be a yes-instance and let S ⊆ V (G) be a solution to I, that is, s ∈ S, |S| ≤ k, and |NG (S)| ≤ ℓ.
We claim that S is also a solution to I ′ . Since s ∈ S and s′ and t′ are both only adjacent to s, S separates
s′ from t′ in G′ . Moreover, |S| ≤ k = k ′ and, as NG′ (S) = NG (S) ∪ {s′ , t′ }, we have |NG′ (S)| ≤ ℓ + 2 = ℓ′ .
Hence, S ′ is a solution to I ′ , and I ′ is a yes-instance.
(⇐) Let I ′ be a yes-instance and let S ′ ⊆ V (G′ ) \ {s′ , t′ } be an s′ -t′ separator in G′ with |S ′ | ≤ k ′
and |NG′ (S ′ )| ≤ ℓ′ . We claim that S ′ is also a solution to I. Note that |S ′ | ≤ k ′ = k. Since S ′ is an
s′ -t′ separator in G′ and s′ and t′ are both adjacent to s, it follows that s ∈ S ′ and s′ , t′ ∈ NG′ (S ′ ). Thus,
we have s ∈ S ′ and |NG (S ′ )| = |NG′ −{s′ ,t′ } (S ′ )| = |NG′ (S ′ )| − 2 ≤ ℓ′ − 2 = ℓ. Hence, S ′ is a solution to I
and I is a yes-instance.
Note that, in the reduction, k ′ and ℓ′ only depend on k and ℓ, respectively. Since Cutting at Most k
Vertices with Terminal parameterized by k or by ℓ is W[1]-hard [24], it follows that Small Secluded
s-t-Separator parameterized by k or by ℓ is W[1]-hard.
Note that the above reduction exploits the fact that we can increase the separator size to decrease the
number of vertices in its neighborhood. In fact, most of the vertices declared to be in the separator do not
serve to separate the terminals at all. To avoid this idiosyncrasy we suggest to study secluded inclusion-wise
minimal separators in future work.
In the following, we prove that Small Secluded s-t-Separator is FPT when parameterized by k + ℓ.
Theorem 3.5. Small Secluded s-t-Separator is ﬁxed-parameter tractable with respect to the combined
parameter k + ℓ, where k is the separator size and ℓ its open neighborhood size.
To prove Theorem 3.5, we exploit that Small Secluded s-t-Separator is eﬃciently solvable on graphs
of small treewidth:
Lemma 3.6. Small Secluded s-t-Separator can be solved in f (k, ℓ, w)·n time on graphs of treewidth w.
Proof. By Courcelle’s theorem [13], it is enough to express the existence of an s-t-separator of cardinality k
and open neighborhood size ℓ in a formula of the monadic second-order logic of graphs such that this
formula has a size depending only on k and ℓ.6 More speciﬁcally, using Courcelle’s theorem, we want to
verify whether our graph G = (V, E) of treewidth w satisﬁes
∃S ⊆ V : separates(s, S, t) ∧ card-le(S, k) ∧ ∀N ⊆ V : (open-nh(N, S) ⇒ card-le(N, ℓ))
where the predicate
card-le(S, k) ≡ ∀v1 ∀v2 . . . ∀vk+1 :

k+1
^
i=1

k k+1


_
_
vi = vj
vi ∈ S ⇒
i=1 j=i+1

is true if and only if |S| ≤ k and this predicate has a size depending only on k,
open-nh(N, S) ≡ ∀v ∈ V : v ∈ N ⇔ (v ∈
/ S ∧ ∃u ∈ S : adj(u, v))
6 We refrained from giving a tedious dynamic program on a tree-decomposition and opted for Courcelle’s theorem instead
for clarity and because a singly exponential running time is out of reach due to the use of the treewidth reduction technique
that we will apply later.

8

is a constant-size predicate that is true if and only if N = N (S), and, ﬁnally,
separates(s, S, t) ≡ ∃A ⊆ V ∃B ⊆ V : (∀v : v ∈ A ∨ v ∈ B ∨ v ∈ S) ∧ s ∈ A ∧ t ∈ B
∧ (∀u∀v : adj(u, v) ⇒ (u ∈
/ A∨v ∈
/ B) ∧ (u ∈
/ B ∨v ∈
/ A))
is a constant-size predicate that is true if and only if S separates s from t. Namely it is true if and only if
the vertex set V \ S can be divided into two sets A and B such that s ∈ A, t ∈ B, and there are no edges
between the sets A and B.
In view of Lemma 3.6, to prove Theorem 3.5 it is enough to reduce Small Secluded s-t-Separator to
the case where the input graph has treewidth bounded by some function in k + ℓ. To this end, we use the
following treewidth reduction technique. Let G be a graph and W ⊆ V (G). The torso torso(G, W ) is a
graph obtained from G[W ] by taking each connected component C in G \ W and making N (C) into a clique
in G[W ]. The following lemma is implied by Marx et al.’s Lemma 2.11 [37]:
Lemma 3.7 (Marx et al. [37]). Let s, t be two vertices of a graph G and let r ∈ N. Let W ′ be the union of
all inclusion-wise minimal s-t separators of size at most r. Then, there is an f (r) · (n + m)-time algorithm
that returns a set W ⊇ W ′ ∪ {s, t} such that torso(G, W ) has treewidth upper bounded by some function
depending only on r.
The algorithm for Theorem 3.5 now proceeds in three stages. First, we use random separation [11]: we
randomly color all vertices red or green. With some probability, all separator vertices will be colored green
and all their neighbors red. We will henceforth assume to have such a coloring. Second, we prepare a graph
of low treewidth containing our solution. This we do by ﬁrst contracting each green component in the graph
to make our desired separator an inclusion-wise minimal one. Relying on this, we then use the treewidth
reduction technique (Lemma 3.7) to compute a vertex subset containing the solution which induces a graph
of small treewidth. In this vertex subset, however, neighbors of some s-t separators may be missing, possibly
introducing false positives. Furthermore, paths between s and t may be missing, introducing false positives
as well. Hence, we make some modiﬁcations to reintroduce the corresponding information. To the resulting
graph, we then apply Lemma 3.6.
Proof of Theorem 3.5. In the following we simultaneously describe the algorithm and gather arguments to
show that, if there is a solution, then the algorithm will accept. For this purpose, assume that the input is
a yes-instance and, among all separators with at most k vertices and open neighborhood of size at most ℓ,
let K be a separator with minimum number of vertices. We will argue in the end that, if the input is a
no-instance, then the algorithm will reject.
Random separation stage: We present this stage already in derandomized form. We use Naor et al.’s
construction of universal sets [38]. An (n, d)-universal set F over some universe U of size n is a family of
subsets of U such that, for each A ⊆ U of size exactly d, the family {A ∩ S | S ∈ F } contains A and all
subsets of A. Naor et al. [38] showed that an (n, d)-universal set of size 2d dO(log d) log n can be computed
in 2d dO(log d) n log n time. In the random separation stage, we compute an (n − 2, k + ℓ)-universal set F over
the vertex set V \ {s, t} of the input graph. We iterate over all the sets F ∈ F and in each such iteration
perform all the algorithm steps described later. Call the vertices in F green and the vertices in V \ F red.
Note that, in one of these iterations, we have that each vertex in K is green and each vertex in N (K) is red,
by the deﬁnition of universal sets. Call such an iteration good for K. Our aim is to show that, if we are in
a good iteration for K, we will accept.
Building a graph of low treewidth: We call an inclusion-wise maximal connected set of green vertices of G
a green component of G. We construct a graph G1 from G by contracting each green component into one
vertex. We remove all self-loops introduced in the process. In the following, we call component vertices the
vertices in G1 corresponding to green components in G. Let m : V (G) → V (G1 ) be the function mapping
each red vertex to itself and each green vertex to the corresponding component vertex.
If we are in a good iteration for K, each green component in G is either contained in K or disjoint from
it. We claim that then K induces an inclusion-wise minimal s-t separator K ′ in G1 , where K ′ = m(K), that
9

is, we obtain K ′ from K by replacing each green component in K by the corresponding component vertex
in G1 . Clearly, K ′ is an s-t separator in G1 . Observe that K ′ is an independent set in G1 . Now, for the sake
of a contradiction, assume that there is an inclusion-wise minimal separator K1′ strictly contained in K ′ .
Since K ′ is an independent set, |NG1 (K1′ )| ≤ |NG1 (K ′ )| ≤ ℓ. Hence, m−1 (K1′ ) is an s-t separator in G with
|m−1 (K1′ )| < |K| ≤ k and |NG (m−1 (K1′ ))| = |NG1 (K1′ )| ≤ ℓ. This is a contradiction to the fact that K has
minimum number of vertices among s-t separators in G with at most k vertices and neighborhood size at
most ℓ. Thus, indeed, K ′ is inclusion-wise minimal.
We next use treewidth reduction (Lemma 3.7) to compute a vertex set W containing the vertices s, t and
all inclusion-wise minimal s-t separators in G1 of size at most k such that torso(G1 , W ) has treewidth upper
bounded by a function of k alone. Clearly, K ′ ⊆ W . In the following, we construct a graph G4 from G1 [W ]
so that we can simply compute a small secluded s-t separator in G4 instead of the input graph. (We bypass
torso(G1 , W ) and use it only to show that G4 has bounded treewidth.) The construction of G4 is as follows.
1) Initially, let G2 = G1 [W ].
2) Denote B = NG (m−1 (W )). Add B to G2 and for each b ∈ B and each v ∈ NG (b) if m(v) is in W , then
make b adjacent to m(v).
3) Let C be the set of connected components of the graph G1 − W . For each C ∈ C introduce new vertex cC
to G2 and make it adjacent to each vertex in m−1 (C) ∩ B. For reference later on, let D = {cC | C ∈ C}.
4) Let us now distinguish the following subsets of W . Recall that F is the set of green vertices and m(F ) is
the set of component vertices. The set R = W \ m(F ) is the set of red vertices in W . The set H = {a ∈
W | |m−1 (a)| > k} is the set of component vertices in W corresponding to huge green components that
cannot take part in the solution. Finally, the set A = {a ∈ m(F ) ∩ W | |m−1 (a)| ≤ k} = W \ (R ∪ H) is
the set of component vertices in W allowed in the solution.
Construct G3 from G2 as follows. Replace each component vertex a in A by a clique on vertex set m−1 (a)
and make each vertex of the clique adjacent to each neighbor of a in G2 . Note that, as the neighbors
of a green component are all red, none of the neighbors are being replaced in the current step. Let
A′ = m−1 (A) ⊆ F be the set of vertices newly (re-)introduced to G3 .
5) Finally, to obtain G4 from G3 , for each vertex in R∪H ∪B∪D introduce k+ℓ+1 new degree-one neighbors.
We claim that G4 satisﬁes the following properties.
(i) If we are in a good iteration for K, then K ⊆ V (G4 ), |NG4 (K)| ≤ ℓ, and K is an s-t separator in G4 .
(ii) If there is an s-t separator L in G4 of size at most k and |NG4 (L)| ≤ ℓ, then there is also such a
separator in G. (Regardless of whether we are in a good iteration.)
(iii) There is a function f such that the treewidth of G4 is bounded from above by f (k).
Let us prove Property (i). Assume that we are in a good iteration for K. Recall that K ′ ⊆ W .
Hence, K ′ is present in G2 after Step 1 and, clearly, is not modiﬁed in Steps 2 and 3. Furthermore, each
component vertex in K ′ corresponds to a green connected component in G of size at most k. Hence, in
Step 4, K ′ is replaced by K and thus K ⊆ V (G4 ). Furthermore, NG4 (K) ⊆ W ∪ B. By construction we
have NG4 (K) ∩ W = NG3 (K) ∩ W = NG2 (K ′ ) ∩ W = NG1 (K ′ ) ∩ W . Thus, for each vertex r ∈ NG4 (K) ∩ W
there is a vertex v ∈ K such that r and v are adjacent in G by the construction of G1 . Also, by construction,
we have NG4 (K) ∩ B = NG3 (K) ∩ B = NG2 (K ′ ) ∩ B and for each b ∈ NG4 (K) ∩ B there is a vertex v ∈ K
such that b and v are adjacent in G by the construction of G2 . Hence, NG4 (K) ⊆ NG (K) and |NG4 (K)| ≤ ℓ.
To prove Property (i) it remains to show that K is an s-t separator in G4 . Suppose for contradiction
that there is an s-t path P in G4 − K. Since G4 and G3 only diﬀer in degree-one vertices, P is an s-t path
also in G3 . If P uses vertices in A′ = {m−1 (a) | a ∈ A}, then we can replace a part of P between the
ﬁrst and last vertex in m−1 (a) by a. This way we obtain an s-t path P2 in G2 − K ′ . If P2 uses vertices
10

outside W then let Q be the set of vertices appearing on P2 between two consecutive vertices a1 and a2
of W and observe that Q ⊆ B ∪ D. We claim that we can remove Q from P2 and replace it by a path P ′
between a1 and a2 in G1 and, hence, obtain a path P1 in G1 . To see this, note that the vertices b ∈ B are
only connected to vertices in W ∩NG1 (C) and to cC for a connected component C of G1 − W with m(b) ∈ C.
Furthermore, cC ∈ D is only connected to vertices in B. It follows that there is a connected component C
of G1 − W such that Q ⊆ {cC } ∪ {b ∈ B | m(b) ∈ C} and {a1 , a2 } ⊆ NG1 (C). Hence, there is the claimed
path P ′ between a1 , a2 in G1 and we can replace Q in P2 with P ′ . Doing this with each part of P2 outside W ,
we obtain an s-t path in G1 − K ′ , a contradiction. Hence, K is an s-t separator in G4 .
We now prove Property (ii). We may assume that L does not contain any vertex that has been introduced in Step 5 as they could be removed from L, yielding another separator that ﬁts the deﬁnition of L.
Furthermore, L does not contain any vertex in R ∪ H ∪ B ∪ D, because L’s neighborhood has size at most ℓ.
Hence, we have L ⊆ A′ ⊆ V (G).
Suppose for contradiction that there is an s-t path P in G − L. As shown above, no (part of a) green
component of size more than k in G is contained in L. Furthermore, since green components of size at most k
have been contracted in G1 , and then replaced by a clique of vertices with identical neighborhood in G3 , we
may assume without loss of generality, that each green component of G is either completely contained in L
or disjoint from it. Hence, contracting green parts of path P we obtain an s-t path P1 in G1 − m(L). For
each part of P1 using vertices outside of W we do the following. Obviously, each such part must stay within
one connected component C of G1 − W . Let b1 and b2 be the ﬁrst and last vertex of C on P1 . We replace
the part of P1 between b1 and b2 by the vertex cC . Doing this with each part of P1 outside of W , we obtain
an s-t path P2 in G2 − m(L). If we replace each vertex a ∈ A on P2 with an arbitrary vertex of m−1 (a), we
obtain an s-t path P3 in G3 − L. This path is also present in G4 − L, contradicting L being an s-t separator
in G4 . Hence, L is an s-t separator in G.
To prove Property (ii) it remains to show that the neighborhood of L in G has size at most ℓ. We show
that NG (L) ⊆ NG4 (L). Recall that L ⊆ A′ . Let b be a vertex of NG (L) and v one of its neighbors in L.
Obviously m(v) is in A ⊆ W and |m−1 (m(v))| ≤ k. If b is in F , then m(b) = m(v) and b is in NG4 (L), since
m−1 (m(v)) is a clique in G4 . Otherwise, m(b) = b. If b is in W , then b is a neighbor of m(v) in G1 [W ],
yielding that b is in NG4 (L). Finally, if b is in G1 − W , then b is in B, b is adjacent to m(v) in G2 , meaning
that b is in NG4 (L). Hence, NG (L) ⊆ NG4 (L), implying that |NG (L)| ≤ ℓ.
We now prove Property (iii). By Lemma 3.7 there exists a tree decomposition T for torso(G1 , W ) and
a function f ′ such that T has width f ′ (k). We show how to adapt T into a tree decomposition for G4
without increasing its width too much. Clearly, T is also a tree decomposition for G1 [W ]. Recall that
the neighborhood of each connected component C of G1 − W is a clique in torso(G1 , W ). Hence, this
neighborhood NG1 (C) occurs in one bag Q of T . Thus, to incorporate cC and its adjacent edges into T , we
make a copy Q′ of bag Q, add cC to Q′ and make Q′ a child of Q in T . Then for each b ∈ B adjacent to cC
in G2 we add a child bag of Q′ with vertex set Q′ ∪ {b}. Since all neighbors of b in G2 are in Q′ and vertices
of D only have neighbors in B, we obtain a valid tree decomposition for G2 . This increases the width of T
by at most 2. In Step 4 we can replace each component vertex by the at most k vertices in the corresponding
green component in G, increasing the width of T by at most a factor of k and obtaining a tree decomposition
for G3 . Then for each vertex v to receive degree-one neighbors in Step 5 we ﬁnd an arbitrary bag Q of T
containing v and for each of the degree one neighbors of v we create a child bag of Q containing v and the
degree one vertex. Since each of these bags is of size 2, this does not increase the width of T . Making these
changes to T , we obtain a tree decomposition for G4 of width at most f ′ (k) · k + 2, as required.
Conclusion: Let us show that the above properties together with Lemma 3.6 conclude the proof. In each
iteration of the random separation phase, we build the graph G4 and the tree decomposition for it and run
the algorithm of Lemma 3.6. If any of the iterations accepts, then we accept, otherwise we reject. On one
hand, if K is an s-t separator in G of size at most k and |NG (K)| ≤ ℓ, then at least one iteration is good
for it and the algorithm will accept the input by Property (i). On the other hand, if the algorithm accepts,
then there is an s-t separator L in G4 of size at most k and |NG4 (L)| ≤ ℓ and by Property (ii) L is such a
separator in G. Thus, the algorithm accepts if and only if we face a yes-instance.
The running time can be upper bounded as follows. Computing the universal set F takes 2k+ℓ (k +
11

ℓ)O(log(k+ℓ)) n log n time. For each of the 2k+ℓ (k + ℓ)log(k+ℓ) log n elements we make one iteration, each of
which takes the following computation time.
Graph G1 can be constructed in linear time, by ﬁrst ﬁnding the green components in linear time. Then,
we compute the neighborhood for all green components simultaneously by scanning over the adjacency lists
of each contained vertex, and marking it as neighbor for that component. Finally, we scan over all vertices,
ﬁnding the neighborhoods of the corresponding component vertices.
Next, Step 1 can clearly be computed in linear time and simultaneously we can ﬁnd in the same fashion
as before the connected components in G1 − W , their neighborhoods in W , as well as the set B together
with, for each vertex in B its connected component in G1 − W . Using this information, we can compute
Step 2 and 3 in linear time.
Since each vertex in A corresponds to a connected component of size at most k, Step 4 can be computed
in O(k(n + m)) time. Step 5 can be computed in O((k + ℓ)(n + m)) time, because each of the sets R, H, B, D
can be computed in linear time alongside the previous computations.
Hence, for each element of the universal set we have made a constant number of O((k + ℓ)(n + m))-time
computations so far. After that, we ﬁnd a tree decomposition for G4 in f (k) · (n + m) time, using a ﬁxedparameter constant-factor approximation algorithm [6] (recall that G4 has treewidth bounded by a function
of k by Property (iii)). Finally, Lemma 3.6 again uses ﬁxed-parameter linear time with respect to k + ℓ.
Thus, each of the steps has f (k + ℓ) · (n + m) running time.
In contrast to Theorem 3.5, we show that, under standard assumptions, the problem does not admit a
polynomial-size kernel with respect to the parameter k + ℓ:
Theorem 3.8. Unless NP ⊆ coNP/poly, Small Secluded s-t-Separator parameterized by k + ℓ does
not admit a polynomial kernel.
Proof. We apply an OR-cross-composition with input problem Small Secluded s-t-Separator (SSstS)
to Small Secluded s-t-Separator parameterized by k + ℓ.
We say that an instance (Gi , si , ti , ki , ℓi ) of SSstS is malformed if min{ki , ℓi } < 0 or max{ki , ℓi } > |V (Gi )|.
We deﬁne the polynomial equivalence relation R on the instances of SSstS as follows. Two instances
(Gi , si , ti , ki , ℓi ) and (Gj , sj , tj , kj , ℓj ) are R-equivalent if ki = kj and ℓi = ℓj , or both instances are malformed. Note that R-equivalence of two instances can be veriﬁed in time polynomial in the instance
sizes. Moreover, any set of instances {(Gq , sq , tq , kq , ℓq ) | q ∈ [p]} is partitioned by R into at most
(maxq∈[pb] {kq , ℓq } + 1)2 + 1 equivalence classes. It follows that R is indeed a polynomial equivalence relation
on the instances of SSstS.
Let (Iq = (Gq , sq , tq , kq , ℓq ))q=1,...,p be R-equivalent instances of Small Secluded s-t-Separator. If
the instances are malformed, we can decide each of them in polynomial time and return a trivial constant
size instance equivalent to the OR of the input instances. Hence, we can assume that the instances are
non-malformed and, thus, ki = kj and ℓi = ℓj for all i, j ∈ [p]. We OR-cross-compose into one instance
I = (G, s1 , tp , k, ℓ) of Small Secluded s-t-Separator, with k := ki and ℓ := ℓi for any i ∈ [p].
Construction: Initially, let G be the disjoint union of G1 , . . . , Gp , that is G = G1 ∪ · · · ∪ Gp . Identify
each tq with sq+1 for all q ∈ [p − 1]. Call the obtained vertex stq , q ∈ [p − 1]. For each stq , q ∈ [p − 1], add
k + ℓ + 1 vertices xq1 , . . . , xqk+ℓ+1 , and connect them by an edge with stq . We will also refer to s1 as s and
as st0 and to tp as t and as stp . This ﬁnishes the construction of the instance.
Correctness: We claim that I is a yes-instance if and only if there exists q ∈ [p] such that Iq is a
yes-instance.
(⇐) Let q ∈ [p] such that Iq is a yes-instance of SSstS. Let S ⊆ V (Gq ) \ {sq , tq } be an sq -tq -separator of
size at most k in Gq such that NGq (S) ≤ ℓ. By construction of G, for all V ′ ⊆ V (Gr ) \ {sr , tr }, r ∈ [p], it
holds that NG (V ′ ) = NGr (V ′ ). Moreover, since G is obtained by a “serial” composition of I1 , . . . , Ip , every st path in G contains s = st0 , st1 , . . . , stp−1 , stp = t in this order. Hence, any vertex set V ′ ⊆ V (Gr ) \ {sr , tr }
separating str−1 and str in G, r ∈ [p], also separates s and t in G. Altogether, S is an s-t-separator in G of
size at most k with NG (S) = NGq (S) ≤ ℓ. Thus, I is a yes-instance of SSstS.
(⇒) Let S ⊆ V (G) \ {s, t} be a minimal s-t separator (of size at most k) such that NG (S) ≤ ℓ. Observe
that S ∩ {st1 , . . . , stp−1 } = ∅, since every str , r ∈ [p − 1], is incident to at least k + ℓ + 1 vertices. Moreover,
12

no vertex xij , i ∈ [p − 1], j ∈ [k + ℓ + 1] is contained in S since S is chosen as minimal and xij is of degree
one and hence not participating in any minimal s-t separator in G. We claim that there exists a q ∈ [p]
with S ⊆ V (Gq ) \ {sq , tq }. Following the argumentation above, since S separates s and t, there is at least
one r ∈ [p] such that S separates str−1 and str . Let q be the minimal index such that S separates stq−1
and stq Suppose there is an r 6= q such that S ∩ V (Gr ) \ {sr , tr } =
6 ∅. Since S separates s from stq ,
S ′ = S ∩ (V (Gq ) \ {sq , tq }) is an s-t-separator of G of size smaller than S. This contradicts the minimality
of S. Hence, S ⊆ V (Gq ) \ {sq , tq }. Since S separates stq−1 and stq in G, it follows that S separates sq
and tq in Gq . Together with |S| ≤ k and NGq (S) = NG (S) implying |NG (S)| ≤ ℓ, it follows that Iq is a
yes-instance.
4. q-Dominating Set
In this section, for two constants p, q ∈ N with 0 ≤ p < q, we study the following problems:
Problem (p-Secluded q-Dominating Set).
Input: A graph G = (V, E) and an integer k.
q
p
Question: Is there a set S ⊆ V such that V = NG
[S] and |NG
[S]| ≤ k?
Problem (Small p-Secluded q-Dominating Set).
Input: A graph G = (V, E) and two integers k, ℓ.
q
p
Question: Is there a set S ⊆ V such that V = NG
[S], |S| ≤ k, and |NG
(S)| ≤ ℓ?
For p = 0, the size restrictions in both cases boil down to |S| ≤ k. This is the well-known case of qDominating Set (also known as q-Center) which is NP-hard and W[2]-hard with respect to k (see Lokshtanov et al. [35], for example). Therefore, for the rest of the section we focus on the case p > 0. Additionally,
by a simple reduction from q-Dominating Set, letting ℓ = |V (G)|, we arrive at the following observation.
Observation 4.1. For any 0 < p < q, Small p-Secluded q-Dominating Set is W[2]-hard with respect
to k.
Furthermore, let us make the following observation which we will use at multiple occasions in the proofs.
Observation 4.2. Let (G = (V, E), k) be a yes-instance of p-Secluded q-Dominating Set and S ⊆ V
p
be a q-dominating set of G with |NG
[S]| ≤ k. If G contains a clique C with |C| > k, then for any v ∈ V and
any c ∈ C such that dG (v, c) < p we have v ∈
/ S.
Proof. Let S be a p-secluded q-dominating set of G and C be a clique in G with |C| > k. Assume for
contradiction that there is a vertex v ∈ S and a vertex c ∈ C with dG (v, c) < p. Then we have that
p
p
dG (v, c′ ) ≤ p for any c′ ∈ C, which implies that C ⊆ NG
[S] and hence |NG
[S]| > k, a contradiction.
We now go on to show NP-hardness and W[2]-hardness with respect to k for p-Secluded q-Dominating
Set. We reduce from the following problem:
Problem (Set Cover).
Input: A ﬁnite universe U , a family F ⊆ 2U , and an integerSk.
Question: Is there a subset X ⊆ F such that |X| ≤ k and x∈X x = U ?
S
S
We write X short for x∈X x. It is known that Set Cover is NP-complete, W[2]-hard with respect to
k, and admits no polynomial kernel with respect to |F |, unless NP ⊆ coNP/poly [16].
Theorem 4.3. For any 0 < p < q, p-Secluded q-Dominating Set is NP-hard. Moreover, it does not
admit a polynomial kernel with respect to k, unless NP ⊆ coNP/poly.

13

Proof. We give a polynomial-parameter transformation from Set Cover parameterized by |F |. Let (U, F, k)
be an instance of Set Cover. Without loss of generality we assume that 0 ≤ k < |F |.
Construction. Let k ′ = p + 1 + |F | · p + k. We construct the graph G of a p-Secluded q-Dominating
Set instance (G, k ′ ) as follows. We start the construction by taking two vertices s and r and three vertex
′
sets VU = {u | u ∈ U }, VF = {vA | A ∈ F }, and VF′ = {vA
| A ∈ F }. We connect vertex r with vertex s
by a path of length exactly q. For each A ∈ F we connect vertices vA and r by an edge and vertices vA
′
A
A
A
A
′
and vA
by a path tA
0 , t1 , . . . , tp of length exactly p, where t0 = vA and tp = vA . Let us denote T the set
of vertices on all these paths (excluding the endpoints). All introduced paths are internally disjoint and the
′
internal vertices are all new. We connect a vertex vA
∈ VF′ with a vertex u ∈ VU by an edge if and only if
u ∈ A. Furthermore, we introduce a clique CU of size k ′ and make all its vertices adjacent to each vertex in
VF′ ∪ VU .
If q − p ≥ 2, then for each u ∈ U we create a path bu0 , bu1 , . . . , buq−p−2 of length exactly q − p − 2 such
that bu0 = u and the other vertices are new. Let us denote the set of all new vertices introduced in this step
B. Furthermore, in this case, for each h ∈ {0, . . . , q − p − 2} we introduce a clique Chu of size k ′ and make all
its vertices adjacent to vertex buh . Let us denote the set of all vertices introduced in this step C. If q − p = 1
we do not introduce any new vertices.
Correctness: We show that the original instance of Set Cover is a yes-instance if and only if the
constructed instance of p-Secluded q-Dominating Set is a yes-instance.
S
(⇒) Let us next show that if there is an X ⊆ F such that |X| ≤ k and X = U , then there is a subset S
q
p
of V (G) such that V (G) = NG [S], and |NG [S]| ≤ k ′ . Indeed, take a set S = {r} ∪ {vA | A ∈ X}. It is a
q
routine to check that all the following vertices are in distance at most q to r and, hence, they are in NG
[S]:
vertex s and the vertices on the path between r and s, vertices in S
VF and VF′ and vertices on the paths
′
between them. For each u ∈ VU there is A ∈ X such that u ∈ A (as X = U ). As u is adjacent to vA
, u is
q
in distance (at most) p + 1 ≤ q to vA and, thus, it is in NG [S]. The same holds for vertices of CU . Moreover,
for q − p ≥ 2, each vertex in B ∪ C is in distance at most q − p − 1 to some vertex in VU . Therefore, all
q
q
[S].
[S] and V (G) = NG
vertices in B ∪ C are in NG
p
It remains to bound |NG [S]|. The p-neighborhood of r is formed by p vertices on the path to s, the
vertices in VF , and p − 1 vertices on each path between VF and VF′ , hence the closed p-neighborhood is of
size exactly p + 1 + |F | · p. For each vertex in VF , its p-neighborhood is only formed by vertices already in
p
the neighborhood of r, except for the corresponding vertex in VF′ . We get that |NG
[S]| ≤ p + 1 + |F | · p + k.
q
(⇐) For the other direction, let us assume that there is a subset S of V (G) such that V (G) = NG
[S]
p
and |NG [S]| ≤ k ′ .
We ﬁrst observe that S ∩ (B ∪ C ∪ T ∪ VF′ ∪ VU ∪ CU ) = ∅. Notice that for every buh ∈ B we have
that {buh } ∪ Chu is a clique of size k ′ + 1 and hence, by Observation 4.2, for v ∈ B ∪ C we have that v ∈
/ S.
′
′
Similarly, for any vA
∈ VF′ we have that {vA
} ∪ CU is a clique of size k ′ + 1 and furthermore we have
′
′
that for each t ∈ T there is a vA
∈ VF′ such that dG (t, vA
) < p. It follows by Observation 4.2 that for
every v ∈ T ∪ VF′ ∪ CU we have that v ∈
/ S. For any u ∈ VU we have that {u} ∪ CU is a clique of size k ′ + 1.
Observation 4.2 yields that S ∩ VU = ∅. Hence, S may only contain vertices in VF and the vertices on the
path between s and r (including endpoints).
Now suppose r ∈
/ S. Then S contains one vertex of VF for each vertex of VF′ (since these are the only
vertices to dominate VF′ and each vertex of VF can dominate one vertex of VF′ ) and at least one vertex of the
p
path between s and r (as no vertex in VF dominates s). It follows that |NG
[S]| ≥ p + 1 + |F | · (p + 1) > k ′ , a
p
contradiction. Hence S must contain r. Note that for S = {r} we have that |NG
[S]| = p + 1 + |F | · p = k ′ − k.
Adding a vertex from VF to S increases the size of the closed p-neighborhood of S by one. It follows that
S may contain at most k vertices from VF .
Now, let us denote
X = {A | vA ∈ S}. We claim that X is a set cover for U of size at most k, that
S
is, |X| ≤ kSand X = U . We already know that |X| ≤ k. Suppose X is not a set cover. Then there is
a u ∈ U \ X. If q − p = 1, then, since S is a solution, there must be a vertex in S in distance at most q
′
from u in G. As VU ∩ S = ∅, this vertex must be in distance at most q − 1 = p from vA
for some A ∈ F ,
u ∈ A. If q − p ≥ 2, then, since S is a solution, there must be a vertex in S in distance at most q from
u
any vertex in Cq−p−2
in G. As (T ∪ VU ∪ CU ∪ B ∪ C) ∩ S = ∅, this vertex must also be in distance at
′
most q − (q − p − 1) − 1 = p from vA
for some A ∈ F , u ∈ A. In both cases it follows that the vertex of S is
14

s

c

q

p

Cr

r
p

p

p

tA
0 = vA

p

...

tA
1
tA
2

tB
0 = vB

VF

′
tB
p = vB

VF′

..
.

..
.

tA
3q−p
tA
3q−p+1
..
.

...

′
tA
p = vA

CU

bu0 1 = u1
C0u1

bu1 1

C1u1

..
.

...

u2

u|U|

VU

..
.

..
.

..
.
1
buq−p−2

u1
Cq−p−2

Figure 1: Illustration of the construction from Theorem 4.4 for 3p ≥ q and p > 1. Dash-dotted lines represent paths (where the
corresponding length is labeled next to each). The ellipses labeled Cr , CU and Ciu for some i correspond to cliques of size k ′ .
If a vertex is connected to such a clique, then there is an edge connecting the vertex with each vertex of the clique (illustrated
by multiple lines). Vertices represented by empty circles form the set containing a p-secluded q-dominating set (if any exists).

S
in VF and it is the vertex vA . But then A ∈ X and u ∈ X—a contradiction.
Since the construction can be performed in polynomial time and k ′ is linear in |F |, the results follows.
In the following, we observe that the parameterized complexity of both problems varies for diﬀerent choices
of p and q.
Theorem 4.4. For any 0 < p ≤ 21 q, p-Secluded q-Dominating Set is W[2]-hard with respect to k.
We prove Theorem 4.4 via a polynomial parameter transformation from Set Cover parameterized by
the size of the solution k. To this end, we apply the following construction.
Construction 4.5. Let (U, F, k) be an instance of Set Cover. Let k ′ = (k + 1) · (2p + 1) if 3p < q
and k ′ = 2p + 1 + k · [p + 21 (3p − q + 1)(q − p)] otherwise. We construct a graph G as follows.
We start the construction (illustrated in Figure 1) by creating three vertices s, c, and r and three vertex
′
sets VU = {u | u ∈ U }, VF = {vA | A ∈ F }, and VF′ = {vA
| A ∈ F }. We connect the vertices s and c by a
15

′
path of length exactly q and c with r by a path of length exactly p. We connect a vertex vA
∈ VF′ with a
vertex u ∈ VU by an edge if and only if u ∈ A.
We introduce a clique Cr of size k ′ and make all its vertices adjacent to r, and we introduce a clique CU
of size k ′ and make all its vertices adjacent to each vertex in VF′ ∪ VU . If q − p ≥ 2, then for each u ∈ VU
u
u
u
u
we further introduce a path bu,
0 , b1 , . . . , bq−p−2 , where b0 = u and bh is a new vertex for each h ≥ 1. Let B
denote the set of all these vertices. Furthermore, in such a case, let us introduce for each u ∈ VU a set of
u
cliques C0u , C1u , . . . , Cq−p−2
, each of size k ′ , and for each h ∈ {0, . . . , q − p − 2} connect every vertex in Chu
u
by an edge to bh . Let C denote the union of vertices in these cliques.
′
A
A
Then we connect for each A ∈ F the vertex vA ∈ VF with the vertex vA
∈ VF′ by a path tA
0 , t1 , . . . , t p
A
A
′
of length p, where t0 = vA and tp = vA . Let T denote the set of vertices on all these paths (excluding the
endpoints).
Now let us distinguish two cases. If 3p ≥ q, then we connect r by paths of length p to vertices tA
h for
all A ∈ F and h ∈ {0, . . . , 3p − q} (note that 3p − q ≤ p as 2p ≤ q). If 3p < q, then we connect r by paths
of length q − 2p to vertices tA
0 = vA for all A ∈ F . Note that in this case q − 2p > p and that in both
′
cases the distance between c and any vA
is exactly q. Indeed, in the ﬁrst case the shortest path contains
A
A
′
vertices c, r, t3p−q , and tp = vA and the distances are p, p, and p − (3p − q) = q − 2p, respectively. In
′
the later case, the shortest path contains vertices c, r, vA , and vA
and the distances are p, q − 2p, and p,
′
respectively. Let us denote T the set of vertices introduced in this step. This ﬁnishes the construction of
the graph G.

Let us now explain the intuition behind Construction 4.5 (cf. Figure 1). Vertex c can q-dominate all
vertices in VF , VF′ , Cr , vertices r and s and the paths connecting these. Furthermore, vertex c q-dominates
the most vertices among all vertices that q-dominate s and, thus, we can assume that c is any optimal
solution of (G, k ′ ). The vertices of G that remain to be q-dominated are the vertices in CU , VU and the
corresponding vertices in C. Our construction enforces that the vertices in VF are the only ones suitable for
that and, hence, their selection corresponds to a set cover in the original instance.
Lemma 4.6. Let (U, F, k) be an instance of Set Cover and 0 < p ≤ 12 q. Let (G, k ′ ) be the instance
obtained from (U, F, k) by applying Construction 4.5. Then (U, F, k) is a yes-instance of Set Cover if and
only if (G, k ′ ) is a yes-instance of p-Secluded q-Dominating Set.
S
Proof. (⇒) Let us ﬁrst show that if there is X ⊆ F such that |X| ≤ k and X = U , then there is a
q
p
subset S of V (G) such that V (G) = NG
[S], and |NG
[S]| ≤ k ′ . Indeed, take a set S = {c} ∪ {vA | A ∈ X}.
It is a routine to check that all the following vertices are in distance at most q to c and, hence, they are in
q
NG
[S]: vertices s and r and the vertices on the paths between c S
and these vertices, vertices in Cr , T ′ , T ,
′
′
VF , and VF . For each u ∈ VU there is A ∈ X such that u ∈ A (as X = U ). As u is adjacent to vA
, u is in
q
distance (at most) p + 1 to vA and, thus, it is in NG [S]. The same holds for all vertices in CU . Moreover,
each vertex in B ∪ C is in distance at most q − p − 1 to some vertex in VU . Therefore, all vertices in B ∪ C
q
q
are in NG
[S] and V (G) = NG
[S].
p
It remains to bound |NG [S]|. The p-neighborhood of c is formed by p vertices on the path to s and p
vertices on the path to r (including r itself), hence it is of size exactly 2p. For each vertex in VF , its
p-neighborhood is only formed by vertices in T ∪ T ′ ∪ VF′ ∪ {r}. In particular, if 3p ≥ q, then the pA
neighborhood of vA contains p vertices of the form tA
h for h ∈ {1, . . . , p}, p− 1 vertices on the path from t0 to
A
A
A
r (excluding vA = t0 , and r) and p−h vertices on the path from th to r (excluding th ) for h ∈ {1, . . . , 3p−q}.
This, together gives
1+p+

3p−q
X
h=0

1
(p − h) − 1 = p + (3p − q + 1)(q − p).
2

(1)

If 3p < q, then the p-neighborhood of vA contains p vertices of the form tA
h for h ∈ {1, . . . , p} and p vertices
p
on the path from vA to r, that is, 2p vertices in total. It follows, that |NG
[S]| ≤ k ′ .
q
(⇐) For the other direction, let us assume that there is a subset S of V (G) such that V (G) = NG
[S],
p
′
and |NG [S]| ≤ k .
16

We ﬁrst observe, that S ∩ (B ∪ C ∪ T ∪ VF′ ∪ VU ∪ CU ) = ∅. Notice that for every buh ∈ B we have
that {buh } ∪ Chu is a clique of size k ′ + 1 and hence, by Observation 4.2, for v ∈ B ∪ C we have that v ∈
/ S.
′
′
Similarly, for any vA
∈ VF′ we have that {vA
} ∪ CU is a clique of size k ′ + 1 and furthermore we have
′
′
that for each t ∈ T there is a vA
∈ VF′ such that dG (t, vA
) < p. It follows by Observation 4.2 that for
′
every v ∈ T ∪ VF ∪ CU we have that v ∈
/ S. For any u ∈ VU we have that {u} ∪ VU is a clique of size k ′ + 1.
Observation 4.2 yields that S ∩ VU = ∅. Further observe that in case 3p ≥ q we have that dG (t′ , r) < p for
each t′ ∈ T ′ and, by Observation 4.2, S ∩ T ′ = ∅. It follows that S only contains vertices from VF and from
the path from s to c. In case 3p < q the set S may also contain vertices from the set T ′ , but notably, all
these vertices are in distance at least p + 1 to any vertex in VU .
Now, let us S
denote X = {A | vA ∈ S}. We claim that X is a set cover for
S U of size at most k, that
is, |X| ≤ k and X = U . Suppose it is not a set cover. Then there is a u ∈ U \ X. If q − p = 1, then, since
S is a solution, there must be a vertex in S in distance at most q from u in G. As VU ∩ S = ∅, this vertex
′
must be in distance at most q − 1 = p from vA
for some A ∈ F , u ∈ A. Similarly, if q − p ≥ 2, then, since S
u
is a solution, there must be a vertex in S in distance at most q from v ∈ Cq−p−2
. As (B ∪ C ∪ VU ) ∩ S = ∅,
′
this vertex must be in distance at most q − (q − p) = p from vA for some A ∈ F , u ∈ A. Since this vertex is
not in (B ∪ C ∪ VU ∪ T ∪ VF′ ), and ifS3q ≥ p also not in T ′ , it follows that this vertex is in VF and it is the
vertex vA . But then A ∈ X and u ∈ X—a contradiction.
Before we show that |X| ≤ k, observe that in S, there must be a vertex on the path between c and s
(possibly one of the endpoints), this vertex is not in VF , and has a p-neighborhood of size at least p + 1.
For 3p < q each vertex of VF has p vertices of the path to r and to the corresponding vertex of VF′ in its
closed p-neighborhood. These 2p + 1 vertices are not in p-neighborhood of any other vertex in VF . It follows
′
= (k+1)·(2p+1)−(p+1)
< k + 1. Finally, in case 3p ≥ q, the p neighborhood of
that |X| ≤ |S ∩ VF | ≤ k −(p+1)
2p+1
2p+1
1
each vertex in VF contains p+ 2 (3p−q +1)(q −p) vertices (see Equation 1) which are not in a p-neighborhood
of any other vertex in VF . It follows that
|X| = |S ∩ VF |
≤

k ′ − (p + 1)
p + 12 (3p − q + 1)(q − p)

2p + 1 + k · [p + 12 (3p − q + 1)(q − p)] − (p + 1)
p + 12 (3p − q + 1)(q − p)
p
=k+
1
p + 2 (3p − q + 1)(q − p)
=

< k + 1.
Thus in all cases |X| ≤ k, ﬁnishing the proof of equivalence of the instances. Since the construction can be
performed in polynomial time and k ′ is linear in k, the result follows.
As Construction 4.5 can be done in polynomial time, Theorem 4.4 immediately follows from Lemma 4.6.
For Small p-Secluded q-Dominating Set, we remark that we can adapt the reduction for Theorem 4.3:
instead of restricting the size of the closed neighborhood of the q-dominating set to at most p + 1 + |F | · p + k,
we restrict the size of the q-dominating set to at most k + 1 and the size of its open neighborhood to at
most p+ |F |·p. Analogously, we can adapt the reduction for Theorem 4.4. This yields the following hardness
results.
Corollary 4.7. For any 0 < p < q, Small p-Secluded q-Dominating Set is NP-hard. Moreover, it does
not admit a polynomial kernel with respect to (k + ℓ) unless NP ⊆ coNP/poly. For any 0 < p ≤ 12 q, Small
p-Secluded q-Dominating Set is W[2]-hard with respect to (k + ℓ).
Now we look at the remaining choices for p and q, that is all p, q with p > 12 q. In these cases we can show
ﬁxed-parameter tractability.
Theorem 4.8. For any p > 12 q, Small p-Secluded q-Dominating Set can be solved in O(mk k+2 (k+ℓ)qk )
time and, hence, it is ﬁxed-parameter tractable with respect to k + ℓ.
17

Proof. Consider a solution S for an instance (G, k, ℓ) of Small p-Secluded q-Dominating Set. If x ∈ S,
then |N p [x]| ≤ k + ℓ, since |S| ≤ k and |N p (S)| ≤ ℓ. Moreover, |N p [x]| ≤ k + ℓ implies |N [v]| ≤ k + ℓ for
every v ∈ N p−1 [x]. It follows that, if |N p [y]| ≤ k + ℓ and y ∈
/ S, then for each x ∈ N q [y] ∩ S every vertex
on every x-y path of length at most 2p − 1 ≥ q has degree at most k + ℓ − 1, since each such vertex has
distance at most p − 1 to x or y.
If k + ℓ = 1, then either G has at most one vertex or (G, k, ℓ) is a no-instance. Hence, in the following, we
assume k + ℓ ≥ 2. We call vertices u and v linked, if there is a path of length at most q between u and v in
G such that the degree of every vertex on the path is at most k + ℓ − 1. Let B[u] = {v | u and v are linked}.
We claim that |B[v]| ≤ (k + ℓ)q for any v.
To prove the claim, let us denote B i [v] the set of vertices u such that there is a path of length at
most i between u and v in G such that the degree of every vertex on the path is at most k + ℓ − 1.
Obviously, B q [v] = B[v]. We prove by induction, that |B i [v]| ≤ (k + ℓ)i for every i ∈ Z+
0 . The claim then
follows. For i = 0 we have B i [v] = {v} and |B i [v]| = 1 ≤ (k + ℓ)0 = 1, showing the basic step. For i ≥ 1
and u ∈ B i [v] \ B i−1 [v], let p0 , p1 , . . . , pi be the u-v path showing that u ∈ B i [v], i.e., p0 = u, pi = v, and
for every j ∈ {0, . . . , i} we have deg pj ≤ k + ℓ − 1. Then p1 ∈ B i−1 [v] and u is a neighbor of p1 . Since the
vertices in B i−1 [v] have in total at most (k+ℓ−1)·|B i−1 [v]| neighbors and |B i−1 [v]| ≤ (k+ℓ)i−1 by induction
hypothesis, we have |B i [v]| ≤ |B i−1 [v]|+(k+ℓ−1)·|B i−1 [v]| = (k+ℓ)·|B i−1 [v]| ≤ (k+ℓ)·(k+ℓ)i−1 = (k+ℓ)i .
This gives the induction step and ﬁnishes the proof of the claim.
Let Y = {y | |N p [y]| ≤ k + ℓ}. Obviously, we have S ⊆ Y , since |N p [S]| ≤ k + ℓ. If yS∈ Y \ S,
then there is x ∈ S such that x and y are linked. It follows that y ∈ B[x] and, thus, Y ⊆ x∈S B[x].
Hence, |Y | ≤ k · (k + ℓ)q ≤ (k + ℓ)q+1 .
This suggests the following algorithm for Small p-Secluded q-Dominating Set: Find the set Y .
If |Y | > k · (k + ℓ)q , then answer “no”. Otherwise, for each k ′ ≤ k and each size-k ′ subset S ′ of Y , check
whether S ′ is a p-secluded q-dominating set in G. If any such set is found, return it. Otherwise, answer
“no”. Since S ⊆ Y , this check is exhaustive.
As to the running time, the set Y can be determined in O(n(k + ℓ)) time by running a BFS from each
vertex and stopping it after it discovers
k + ℓ vertices or all vertices in distance at most p, whichever occurs
q
k+1
earlier. Then, there are k · k·(k+ℓ)
≤
k
(k + ℓ)qk candidate subsets of Y . For each such set S ′ we can
k
check whether it is a p-secluded q-dominating set in G by running a BFS from each vertex of S ′ and marking
the vertices which are in distance at most p and at most q, respectively. This takes O(mk) time. Hence, in
total, the algorithm runs in O(mk k+2 (k + ℓ)qk ) time.
By Observation 1.1, the previous result transfers to p-Secluded q-Dominating Set parameterized by k.
Corollary 4.9. For any p > 12 q, p-Secluded q-Dominating Set is ﬁxed-parameter tractable with respect
to k.
5. F -free Vertex Deletion
In this section, we study the F -free Vertex Deletion (F -FVD) problem for families F of graphs with at
most a constant number c of vertices, that is, the problem of destroying all induced subgraphs isomorphic to
graphs in F by at most k vertex deletions. The problem can, in particular, model various graph clustering
tasks [4, 29], where the secluded variants can be naturally interpreted as removing a small set of outliers
that are weakly connected to the clusters.
5.1. Secluded F -free Vertex Deletion
In this section, we prove a polynomial-size problem kernel for Secluded F -free Vertex Deletion,
where F is a family of graphs with at most a constant number c of vertices:
Problem (Secluded F -free Vertex Deletion).
Input: A graph G = (V, E) and an integer k.
Question: Is there a set S ⊆ V such that G − S is F -free and |NG [S]| ≤ k?
18

Henceforth, we call a set S ⊆ V such that G − S is F -free an F -free vertex deletion set.
Note that Secluded F -free Vertex Deletion can be polynomial-time solvable for some families F
for which F -FVD is NP-hard: Vertex Cover (where F contains only the graph consisting of a single
edge) is NP-hard, yet any vertex cover S satisﬁes N [S] = V . Therefore, an instance to Secluded Vertex
Cover is a yes-instance if and only if k ≥ n. In general, however, one can show that Secluded F Free Vertex Deletion is NP-complete for every family F that includes only graphs of minimum vertex
degree two (Theorem 5.1). We mention in passing that, from this peculiar diﬀerence of the complexity of
Vertex Cover and Secluded Vertex Cover, it would be interesting to ﬁnd properties of F which
govern whether Secluded F -free Vertex Deletion is NP-hard or polynomial-time solvable along the
lines of the well-known dichotomy results [21, 34].
Theorem 5.1. For each family F containing only graphs of minimum vertex degree two, Secluded F -Free
Vertex Deletion is NP-complete.
Proof. We reduce from F -free Vertex Deletion, which is NP-complete for all F that contain only
graphs of minimum vertex degree two [34]. Given an instance (G, s) of F -free Vertex Deletion where
G contains n vertices, we add n + 1 new degree-one neighbors to each vertex in G. In this way, we obtain
an instance (G′ , k) of Secluded F -free Vertex Deletion by setting k = s · (n + 1) + n.
Clearly, each F -free vertex deletion set S of size at most s for G is a F -free vertex deletion set for G′ as
each graph in F contains no degree-one vertices. Furthermore, clearly, |NG′ [S]| ≤ s · (n + 1) + n = k.
In the other direction, for each F -free vertex deletion set S for G′ we may assume that no degree-one
vertex is contained in S, hence, S is a F -free vertex deletion set for G. Furthermore, as each vertex in V (G)
incurs at least n + 1 vertices in the closed neighborhood NG′ (S), if this neighborhood has size at most k,
then there are at most s vertices in S.
It is easy to see that Secluded F -free Vertex Deletion is ﬁxed-parameter tractable. More speciﬁcally,
it is solvable in ck · poly(n) time: simply enumerate all inclusion-minimal F -free vertex deletion sets S of
size at most k using the standard search tree algorithm described by Cai [9] and check |N [S]| ≤ k for each
of them. This works because, for any F -free vertex deletion set S with |N [S]| ≤ k, we can assume that S is
an inclusion-minimal F -free vertex deletion set since |N [S ′ ]| ≤ |N [S]| for every S ′ ( S.
We complement this observation of ﬁxed-parameter tractability by the following kernelization result.
Theorem 5.2. Secluded F -free Vertex Deletion has a problem kernel comprising O(k c+1 ) vertices,
where c is the maximum number of vertices in any graph of F .
Our proof of Theorem 5.2 exploits expressive kernelization algorithms for d-Hitting Set [2, 3, 19], which
preserve inclusion-minimal solutions and that return subgraphs of the input hypergraph as kernels: Herein,
given a hypergraph H = (U, C) with |C| ≤ d for each C ∈ C, and an integer k, d-Hitting Set asks whether
there is a hitting set S ⊆ U with |S| ≤ k, that is, C ∩ S 6= ∅ for each C ∈ C. Our kernelization for
Secluded F -free Vertex Deletion is based on transforming the input instance (G, k) to a d-Hitting
Set instance (H, k), computing an expressive d-Hitting Set problem kernel (H ′ , k), and outputting a
Secluded F -free Vertex Deletion instance (G′ , k), where G′ is the graph induced by the vertices
remaining in H ′ together with at most k + 1 additional neighbors for each vertex in G.
Definition 5.3. Let (G = (V, E), k) be an instance of Secluded F -free Vertex Deletion. For a
vertex v ∈ V , let Nj (v) ⊆ NG (v) be j arbitrary
neighbors of v, or Nj (v) := NG (v) if v has degree less
S
than j. For a subset S ⊆ V , let Nj (S) := v∈S Nj (v). Moreover, let
c := maxF ∈F |V (F )| be the maximum number of vertices in any graph in F ,
H = (U, C) be the hypergraph with U := V and C := {S ⊆ V | G[S] ∈ F },
H ′ = (U ′ , C ′ ) be a subgraph of H with |U ′ | ∈ O(k c ) such that each set S ⊆ U with |S| ≤ k is an inclusionminimal hitting set for H if and only if it is for H ′ , and
G′ = (V ′ , E ′ ) be the subgraph of G induced by U ′ ∪ Nk+1 (U ′ ).
19

To prove Theorem 5.2, we show that (G′ , k) is a problem kernel for the input instance (G, k). The subgraph H ′ exists and is computable in linear time from H [3, 19]. Moreover, for constant c, one can compute
H from G and G′ from H ′ in polynomial time. It is obvious that the number of vertices of G′ is O(k c+1 ).
Hence, it remains to show that (G′ , k) is a yes-instance if and only if (G, k) is. This is achieved by the
following two lemmas.
Lemma 5.4. For any S ⊆ U ′ with |NG′ [S]| ≤ k, it holds that NG [S] = NG′ [S].
Proof. Since S ⊆ U ′ ⊆ V ′ ∩ V and since G′ is a subgraph of G, it is clear that NG [S] ⊇ NG′ [S]. For the
opposite direction, observe that each v ∈ S has degree at most k in G′ . Thus, v has degree at most k in G
since, otherwise, k + 1 of its neighbors would be in G′ by construction. Thus, NG′ (v) ⊇ Nk+1 (v) = NG (v)
for all v ∈ S and, thus, NG′ [S] ⊇ NG [S].
Lemma 5.5. Graph G allows for an F -free vertex deletion set S with |NG [S]| ≤ k if and only if G′ allows
for an F -free vertex deletion set S with |NG′ [S]| ≤ k.
Proof. Let S be an inclusion-minimal F -free vertex deletion set with |NG [S]| ≤ k for G. Then S is an
inclusion-minimal hitting set for H and, by construction, also for H ′ . Thus, S consists only of vertices of G′ .
Since G′ is an induced subgraph of G, it holds that G′ − S is an induced subgraph of G − S, which is F -free.
Thus, G′ − S is also F -free and S is an F -free vertex deletion set for G′ . Moreover, |NG′ [S]| ≤ |NG [S]| ≤ k
follows since G′ is a subgraph of G.
Now, let S be an F -free vertex deletion set with |NG′ [S]| ≤ k for G′ . Then S ∩ U ′ is a hitting set for H ′ :
if there was a set C ∈ C ′ with C ∩ S = ∅, then, by construction of H ′ and G′ , G′ [C] = G[C] ∈ F would
remain a forbidden induced subgraph in G′ − S. Thus, S contains an inclusion-minimal hitting set S ′ ⊆ U ′
for H ′ . Since |S ′ | ≤ k, it is, by construction of H ′ , also a hitting set for H. Now, by construction of H
from G, S ′ is a F -free vertex deletion set for G. Finally, since |NG′ [S ′ ]| ≤ |NG′ [S]| ≤ k, we also have
|NG [S ′ ]| = |NG′ [S ′ ]| ≤ k by Lemma 5.4.
5.2. Small Secluded F -free Vertex Deletion
In this subsection, we present a ﬁxed-parameter algorithm for the following problem parameterized
by ℓ + k.
Problem (Small Secluded F -free Vertex Deletion).
Input: A graph G = (V, E) and two integers k, ℓ.
Question: Is there a subset S ⊆ V such that G − S is F -free, |S| ≤ k, and |NG (S)| ≤ ℓ?
As before, we call a set S ⊆ V such that G − S is F -free an F -free vertex deletion set.
In the previous section, we discussed a simple search tree algorithm for Secluded F -free Vertex
Deletion that was based on the fact that we could assume that our solution is an inclusion-minimal F -free
vertex deletion set. However, an F -free vertex deletion set S with |S| ≤ k and |NG (S)| ≤ ℓ is not necessarily
inclusion-minimal: some vertices may have been added to S just in order to shrink its open neighborhood.
However, the following simple lemma limits the number of possible candidate vertices that can be used to
enlarge S in order to shrink N (S), which we will use in a branching algorithm.
Lemma 5.6. Let S be an F -free vertex deletion set and S ′ ⊇ S such that |S ′ | ≤ k and |NG (S ′ )| ≤ ℓ, then
|NG (S)| ≤ ℓ + k.
Proof. |NG (S)| = |NG [S] \ S| ≤ |NG [S ′ ] \ S| ≤ |NG [S ′ ]| ≤ |NG (S ′ ) ∪ S ′ | ≤ ℓ + k.
Theorem 5.7. Small Secluded F -free Vertex Deletion can be solved in max{c, k+ℓ}k ·poly(n)-time,
where c is the maximum number of vertices in any graph of F .
Proof. First, enumerate all inclusion-minimal F -free vertex deletion sets S with |S| ≤ k. This is possible
in ck · poly(n) time using the generic search tree algorithm described by Cai [9]. For each k ′ ≤ k, this
′
search tree algorithm generates at most ck sets of size k ′ . For each enumerated set S of k ′ elements, do the
following:
20

1. If |NG (S)| ≤ ℓ, then output S as our solution.
2. If |NG (S)| > ℓ + k, then S cannot be part of a solution S ′ with NG (S ′ ) ≤ ℓ by Lemma 5.6, we proceed
with the next set.
3. Otherwise, initiate a recursive branching: recursively branch into at most ℓ + k possibilities of adding
a vertex from NG (S) to S as long as |S| ≤ k.
The recursive branching initiated at step 3 stops at depth k − k ′ since, after adding k − k ′ vertices to S, one
obtains a set of size k. Hence, the total running time of our algorithm is
poly(n) ·

k
X

′

′

ck (ℓ + k)k−k = poly(n) ·

k′ =1

k
X

max{c, ℓ + k}k = poly(n) · max{c, ℓ + k}k .

k′ =1

Given Theorem 5.7, a natural question is whether the problem allows for a polynomial kernel.
6. Feedback Vertex Set
In this section, we study secluded versions of the Feedback Vertex Set (FVS) problem, which asks,
given a graph G and an integer k, whether there is a set W ⊆ V (G), |W | ≤ k, such that G − W is cycle-free.
6.1. Secluded Feedback Vertex Set
We show in this subsection that the problem below is NP-hard and admits a polynomial kernel.
Problem (Secluded Feedback Vertex Set (SFVS)).
Input: A graph G = (V, E) and an integer k.
Question: Is there a set S ⊆ V such that G − S is cycle-free and |NG [S]| ≤ k?
Theorem 6.1. Secluded Feedback Vertex Set is NP-hard.
The proof is by a reduction from the FVS problem and works by attaching to each vertex in the original
graph a large set of new degree-one neighbors.
Proof. We provide a polynomial time many-one reduction from Feedback Vertex Set. Let (G =
(V, E), k) be an instance of Feedback Vertex Set. We construct an equivalent instance (G′ = (V ′ , E ′ ), k ′ )
of SFVS as follows. To obtain G′ , for each vertex v ∈ V (G) add n2 vertices and connect them to v. Observe
that the added vertices have degree one and thus are never part of a cycle in G′ . Further, set k ′ = k ·(n2 + n).
We claim that (G, k) is a yes-instance of FVS if and only (G′ , k ′ ) is a yes-instance of SFVS.
(⇒) Let S ⊆ V (G) be a feedback vertex set in G. Then the corresponding vertices in G′ form a
feedback vertex set in G′ . Moreover, we have k vertices, each having at most n2 + n neighbors. Thus,
|NG′ [S]| ≤ k · (n2 + n) = k ′ . It follows that (G′ , k ′ ) is a yes-instance of SFVS.
(⇐) Conversely, let S be a minimal solution to (G′ , k ′ ), that is, S is a feedback vertex set in G′ such that
|NG′ [S]| ≤ k ′ and S \ {v} is not a feedback vertex set in G′ for every v ∈ S. By minimality of S, and since
the added vertices do not appear in any cycle in G′ , S does not contain any of the added vertices. Hence
S ⊆ V and, thus |S| ≤ k as each vertex in V has at least n2 private neighbors in G′ . Thus, since S forms a
feedback vertex set in G′ , S also forms a feedback vertex set in G. It follows that (G, k) is a yes-instance of
FVS.
On the positive side, SFVS remains ﬁxed-parameter tractable with respect to k:
Theorem 6.2. Secluded Feedback Vertex Set admits a kernel with O(k 5 ) vertices.

21

In the remainder of this section, we describe the data reduction rules that yield the polynomial-size problem
kernel. The reduction rules are inspired by the kernelization algorithm for the Tree Deletion Set problem
given by Giannopoulou et al. [27].
We start by introducing the following notation. A 2-core [40] of a graph G is a maximum subgraph H of
G such that, for each v ∈ V (H), we have degH (v) ≥ 2. Note that a 2-core H of a given graph G is unique
and can be found in polynomial time [40]. If H is a 2-core of G, then we use degH|0 (v) to denote degH (v)
if v ∈ V (H) and degH|0 (v) = 0 if v ∈
/ V (H).
Observation 6.3. Let G be a graph, H its 2-core, and C a connected component of G − V (H). Then
|N (C) ∩ V (H)| ≤ 1 and |N (H) ∩ V (C)| ≤ 1.
Proof. We only show the ﬁrst statement. The second statement follows analogously. Towards a contradiction, assume that |N (C) ∩ V (H)| ≥ 2. Then, there are vertices x, y ∈ V (H) with x 6= y such that x and y
have neighbors a, b ∈ V (C). If a = b, then G′ = G[V (H) ∪ {a}] is a subgraph of G such that degG′ (v) ≥ 2
for every v ∈ V (G′ ), contradicting the choice of H as the 2-core of G. If a 6= b, then, since C is connected,
there is a path PC in C connecting a and b. Thus, G′ = G[V (H) ∪ V (PC )] is a subgraph of G such that
degG′ (v) ≥ 2 for every v ∈ V (G′ ), again contradicting the choice of H as the 2-core of G.
Note that only the vertices in the 2-core are involved in cycles of G. However, the vertices outside the 2-core
can inﬂuence the size of the closed neighborhood of the feedback vertex set. Next, we apply the following
reduction rules to our input instance with G given its 2-core H.
We say that a feedback vertex set F in G is secluded if |N [F ]| ≤ k. Further, we say that a secluded
feedback vertex set F in G is minimal, if F \ {v} is not a secluded feedback vertex set in G for all v ∈ F .
Reduction Rule 6.4. If degH|0 (v) = 0 for every v ∈ N [u], then delete u.
Proof of correctness. Let F be a minimal secluded feedback vertex set in G. Since degH|0 (v) = 0 for all
v ∈ N [u], none of them is involved in a cycle. Hence, N [u]∩F = ∅. In particular, it follows from N (u)∩F = ∅
that u 6∈ N [F ]. Hence, F is a secluded feedback vertex set in G − {u} as well.
Conversely, let F be a minimal secluded feedback vertex set in Gu := G − {u}. We have to show that F
is a secluded feedback vertex set in G as well. First observe that since degH|0 (v) = 0 for all v ∈ NG [u], H
is also the 2-core of Gu . As only vertices in H participate in cycles of Gu and F is chosen as minimal, none
of the vertices NG (u) ⊆ V (Gu ) is contained in F . If follows that |NG [F ]| = |NGu [F ]| ≤ k, and thus F is a
secluded feedback vertex set in G as well.
Note that, if Reduction Rule 6.4 has been exhaustively applied, then degH|0 (v) = 0 implies that v has
exactly one neighbor, which is in the 2-core of the graph.
Reduction Rule 6.5. If v0 , v1 , . . . , vℓ , vℓ+1 is a path in the input graph such that ℓ ≥ 3, degH|0 (vi ) = 2 for
every i ∈ {1, . . . , ℓ}, degH|0 (v0 ) ≥ 2, and degH|0 (vℓ+1 ) ≥ 2, then let r = min{degG (vi ) | i ∈ {1, . . . , ℓ}} − 2
and remove vertices v1 , . . . , vℓ and their neighbors not in the 2-core. Then introduce two new vertices u1
and u2 with edges {v0 , u1 }, {u1 , u2 }, and {u2 , vl+1 } and 2r further new vertices and connect u1 with r of
them and u2 with another r of them.
Proof of correctness. Let F be a minimal secluded feedback vertex set in G, and let G′ be the graph obtained
from G by applying Reduction Rule 6.5. Suppose F ∩ {v1 , . . . , vℓ } 6= ∅. Since degH|0 (vi ) = 2 for all
i ∈ [ℓ], each of the vertices v1 , . . . , vℓ participates in the same set of cycles of G. Hence, it follows that
F ∩ {v1 , . . . , vℓ } = {vq } for some q ∈ [ℓ]. Moreover, the set of cycles where v1 , . . . , vℓ appear in is a subset of
the set of cycles where v0 appears in and a subset of the set of cycles where vℓ+1 appears in. Hence, due to
minimality of F we have that vq ∈ F implies v0 6∈ F and vℓ+1 6∈ F . Due to the deﬁnition of r the number
of neighbors of vq not in the 2-core is at least r. Then F ′ = (F \ {vq }) ∪ {u1 } is a secluded feedback vertex
set of G′ with |F ′ | = |F | and |NG [F ]| ≥ |NG′ (F ′ )|.
Suppose F ∩ {v1 , . . . , vℓ } = ∅ but F ∩ {v0 , vℓ+1 } =
6 ∅. Then |F ∩ {v0 , vℓ+1 }| = |NG [F ] ∩ {v1 , vℓ }| =
|NG′ [F ] ∩ {u1 , u2 }|. It follows that F is a secluded feedback vertex set in G′ with |NG′ [F ]| = |NG [F ]|.
The case where F ∩ {v0 , . . . , vℓ+1 } = ∅ is trivial.
22

Conversely, let F be a minimal secluded feedback vertex set in G′ . Suppose that F ∩ {u1 , u2 } =
6 ∅. Since
F is minimal, either u1 or u2 is contained in F , since both vertices participate in the same set of cycles in G′ .
Without loss of generality, let u1 ∈ F . Moreover, F ∩ {v0 , vℓ } = ∅, as otherwise F \ {u1 } is a smaller secluded
feedback vertex set in G′ , contradicting the minimality of F . By the choice of r, there exists q ∈ [ℓ] such
that degG (vq ) − 2 = r. Then F ′ := (F \ {u1 }) ∪ {vq } is a feedback vertex set in G with |NG [F ′ ]| = |NG′ [F ]|.
Suppose that F ∩ {v0 , vℓ+1 } 6= ∅. Since F is minimal, it follows that F ∩ {u1 , u2 } = ∅. Observe that F is
also a feedback vertex set in G, as v0 and vℓ+1 participate in each cycle containing any vertex in {v1 , . . . , vℓ }.
Since |F ∩ {v0 , vℓ+1 }| = |NG′ [F ] ∩ {u1 , u2 }| = |NG [F ] ∩ {v1 , vℓ }|, it follows that |NG [F ]| = |NG′ [F ]|. Hence,
F is a secluded feedback vertex set in G.
The case where F ∩ {v0 , u1 , u2 , vℓ+1 } = ∅ is trivial.
For x ∈ V (G), we denote by petal(x) the maximum number of cycles only intersecting in x.
Reduction Rule 6.6. If there is a vertex x ∈ V (G) such that petal(x) ≥ ⌈ k2 ⌉, then output that (G, k) is a
no-instance of SFVS.
Proof of correctness. There are at least ⌈ k2 ⌉ cycles in G, which are vertex-disjoint except for x. Assume that
G allows a feedback vertex set F with |NG [F ]| ≤ k. Clearly, F must contain at least one vertex in each
of the cycles. Therefore N [F ] must contain at least three vertices of each cycle. As only x can be shared
among these triples, we get |NG [F ]| ≥ 2 · ⌈ k2 ⌉ + 1 > k. It follows that G does not admit a secluded feedback
vertex set.
Reduction Rule 6.7. If v ∈ V (G) is a vertex such that degG (v) > k, but degH|0 (v) < degG (v), then
remove one of its neighbors not in the 2-core.
Proof of correctness. First observe that, as degG (v) > k, vertex v cannot be contained in any secluded
feedback vertex set. As additionally degH|0 (v) < degG (v), we know that there is a vertex w ∈ N (v) \ V (H).
Since w is not in the 2-core, it is not involved in the cycles of G. Since degG (v) > k, removing w from G
results in degG−{w} (v) ≥ k and hence, v cannot be contained in any secluded feedback vertex set of G− {w}.
Altogether, G has a feedback vertex set F with |NG [F ]| ≤ k if and only if G − {w} has a feedback vertex
set F ′ with |NG−{w} [F ′ ]| ≤ k.
Reduction Rule 6.8. Let x, y be two vertices of G. If there are at least k internally vertex disjoint paths
of length at least 2 between x and y in G, then output that (G, k) is a no-instance of SFVS.
Proof of correctness. Observe then that if neither x nor y belong to a feedback vertex set D of G we need at
least k −1 vertices to hit all the cycles, since otherwise there are at least two distinct paths P1 , P2 of length at
least 2 between x and y with (V (P1 ) ∪ V (P2 )) ∩ D = ∅ and thus the graph induced by V (P1 ) ∪ V (P2 ) ∪ {x, y}
contains a cycle. Since each of the k − 1 vertices has at least two vertices in its open neighborhood and only
the vertices x and y can be shared among these, the closed neighborhood contains at least k + 1 vertices.
On the other hand, the open neighborhood of both x and y contains one vertex from each of the k paths.
Therefore, their closed neighborhood is of size at least k + 1 and they cannot be included in the solution.
Note that Reduction Rules 6.4, 6.5, 6.7 and 6.8 can be applied trivially in polynomial time. Reduction
Rule 6.6 can be applied exhaustively in polynomial time due to the following.
Proposition 6.9 ([41]). Let G be a graph and x be a vertex of G. In polynomial time we can either ﬁnd a
set of ℓ + 1 cycles only intersecting in x (proving that petal(x) ≥ ℓ + 1) or a set of vertices Z ⊆ V (G) \ {x}
of size at most 2ℓ intersecting every cycle containing x.
An instance (G, k) of SFVS is called reduced if none of the Reduction Rules 6.4 to 6.8 can be applied.
Following the proof by Giannopoulou et al. [27], we ﬁrst give structural decomposition lemma, then bound the
size of components of the decomposition, and ﬁnally bound the number of components in the decomposition
to obtain the polynomial kernel for SFVS parameterized by k. We start with the following structural
decomposition lemma, which identiﬁes the set B.
23

Lemma 6.10. There is a polynomial time algorithm that given a reduced instance (G, k) of SFVS either
correctly decides that (G, k) is a no-instance or ﬁnds two sets F and M ′ such that, denoting B = F ∪ M ′ ,
the following holds.
(i) F is a feedback vertex set of G.
(ii) Each connected component of G − B has at most 2 neighbors in M ′ .
(iii) For every connected component C in G − B and x ∈ B, |NG (x) ∩ C| ≤ 1, that is, every vertex y of F
and every vertex x of M ′ have at most one neighbor in every connected component C of G − B.
(iv) |B| ≤ 4k 2 + 2k.
Similar to Giannopoulou et al. [27], we also make use of the following concept. For a rooted tree T
and vertex set M in V (T ) the lowest common ancestor-closure (LCA-closure) lcac(M ) is obtained by the
following process. Initially, set M ′ = M . Then, as long as there are vertices x and y in M ′ whose lowest
common ancestor w is not in M ′ , add w to M ′ . Finally, output M ′ as the LCA-closure of M .
Lemma 6.11 (Fomin et al. [23]). Let T be a tree and M ⊆ V (T ). If M ′ = lcac(M ) then |M ′ | ≤ 2|M | and
for every connected component C of T − M ′ , |NT (C)| ≤ 2.
We continue with proving our structural decomposition lemma.
Proof of Lemma 6.10. Note that if there is a feedback vertex set of G with closed neighborhood of size at
most k, then it is also a feedback vertex set in G of size at most k. Thus, we can apply the 2-approximation
algorithm for Feedback Vertex Set on G due to Bafna et al. [1] to ﬁnd in polynomial time a feedback
vertex set F of G. If |F | > 2k, then we output that (G, k) is a no-instance of SFVS. Hence, we assume
|F | ≤ 2k in the following. Since F is a feedback vertex set in G, property (i) is trivially fulﬁlled. Moreover,
G − F is a collection of trees T1 , . . . , Tℓ . We select for each of the trees Ti some root vertex vi ∈ V (Ti ). It
remains to construct the set M ′ such that F ∪ M ′ fulﬁlls conditions (ii)–(iv).
Recall that the instance (G, k) is reduced. Hence, Reduction Rule 6.6 is not applicable, and hence
petal(x) < ⌈ k2 ⌉ for all x ∈ F . We apply Proposition 6.9 to each vertex in v ∈ F , obtaining a set Zv ⊆
V (G) \ {v} intersecting each cycle containing v with |Zv | ≤ k. Let Z := Z1 ∪ . . . ∪ Z|F | denote the
′
union of these sets. Observe that |Z| ≤ 2k 2 . We set Mi := Ti ∩ Z
S and M′ i := lcac(Mi ) for′ all i ∈ [ℓ].
′
′
Observe that, by Lemma 6.11, |Mi | ≤ 2|Mi |. Finally, we set M = i∈[ℓ] Mi and B = F ∪ M (note that
P
P
F ∩ M ′ = ∅). Observe that |M ′ | ≤ i∈[ℓ] |Mi′ | ≤ i∈[ℓ] 2|Mi | ≤ 2|Z| ≤ 4k 2 and by Lemma 6.11, for every
connected component C in G − B it holds that |NG−F (C)| ≤ 2 (hence, property (ii) is fulﬁlled). Altogether,
|B| = |F | + |M ′ | ≤ 2k + 4k 2 , yielding property (iv). It remains to show that property (iii) is fulﬁlled.
Let C be a connected component of G − B and x ∈ B some vertex. Suppose that x has two neighbors
in C. Then Cx := C ∪ {x} induces a cycle in G as C is connected. If x ∈ F , then this contradicts the set
Zx ⊆ Z ⊆ M ′ ∪ (F \ {x}) hitting every cycle containing x. If x ∈ M ′ , then this contradicts the set F hitting
each cycle in G. Hence, property (iii) is fulﬁlled.
Next, we show that if B is as in Lemma 6.10, then the size and the number of the connected components in
the G − B is polynomial upper-bounded in the size k of the closed neighborhood of the feedback vertex set
in question. We ﬁrst upper-bound the size of the connected components in G − B in the following.
Lemma 6.12. Let (G, k) and B be as in Lemma 6.10, and let C be a connected component of G − B. Then
the number of vertices |V (C)| of the connected component C is at most (12k + 7)(k + 1).
Proof. Le H be the 2-core of G. We distinguish two cases on the size of CH := V (C) ∩ V (H), namely
|CH | = 0 on the one hand, and |CH | > 0 on the other hand.
Case |CH | = 0: Observe that C is a connected component in G−V (H). Hence, by Observation 6.3, there
is at most one vertex in C adjacent to H. If x ∈ V (C) is adjacent to H, no other vertex of C is adjacent to H.
Suppose that |V (C)| > 1. Since C is connected, there is a vertex u ∈ V (C) such that N [u] ⊆ G − V (H).
24

Existence of such vertex would contradict the instance being reduced with respect to Reduction Rule 6.4.
Hence, |V (C)| ≤ 1.
Case |CH | > 0: Recall that (G, k) is reduced. On the one hand, due to Reduction Rule 6.4, we know that
every vertex in C − V (H) has a neighbor in CH . On the other hand, due to Reduction Rule 6.7, each vertex
in CH has at most k neighbors in C − V (H). Hence, it follows that |V (C)| ≤ (k + 1) · |CH |. Consequently,
it remains to bound the number of vertices in CH .
In the following we count the number of vertices in G[CH ] having degree 1, 2, and at least 3 in G[CH ].
1
1
Let DH
⊆ CH be the set of vertices in G[CH ] having degree exactly one. Since DH
⊆ V (H), it holds that
1
degH|0 (v) ≥ 2 for each v ∈ DH . Since there is exactly one neighbor of v in G[CH ], at least one other neighbor
is contained in V (H) ∩ B. Let BC denote the vertices of C having at least one neighbor in B. Note that
1
DH
⊆ BC . Due to Lemma 6.10(ii), C has at most two neighbors in M ′ (recall B = F ∪ M ′ ). Moreover, due
to Lemma 6.10(iii), each vertex in B has at most one neighbor in C. It follows that |BC | ≤ |F | + 2 ≤ 2k + 2,
1
and hence |DH
| ≤ 2k + 2.
≥3
Let DH ⊆ CH be the set of vertices in G[CH ] having degree at least three. Since G[CH ] is acyclic (recall
1
that F ⊆ B is a feedback vertex set), it follows that DH
forms the leaves in G[CH ]. A basic observation on
trees is that the number of inner vertices of degree at least three is at most the number of leaves minus one.
≥3
1
Hence, |DH
| ≤ |DH
| − 1 ≤ 2k + 1.
≥3
−2
−2
Let DH := BC ∪ DH
. Observe that CH \ DH
only contains vertices having degree exactly two
−2
−2
in G[CH ]. Moreover, these vertices participate only in paths connecting vertices in DH
. Since |DH
|≤
2k + 2 + 2k + 1 = 4k + 3, and G[CH ] is acyclic, there are at most 4k + 3 − 1 = 4k + 2 many of these paths.
Moreover, due to Reduction Rule 6.5, these paths contain at most two vertices not being the endpoints.
−2
−2
Hence, |CH | ≤ |CH \ DH
| + |DH
| ≤ 2 · (4k + 2) + 4k + 3 = 12k + 7. It follows that |V (C)| ≤ (k + 1) · |CH | ≤
(k + 1) · (12k + 7).
Having an upper bound on the sizes of the set B and of each connected component in G − B, it remains
to count the number of connected components in G − B.
Remark. It is easy to polynomially upper-bound the number of connected components in G − B. To
this end, ﬁrst observe that by Reduction Rule 6.4, each connected component in G − B has at least one
neighbor in B. Next, consider those connected components in G − B having exactly one neighbor in B. Due
to Reduction Rule 6.6, each vertex in B is incident to at most k connected components in G − B having
exactly one neighbor in B. Hence, the number of these connected components in G − B is upper bounded by
|B| · (k + 1). Last, consider those connected components in G − B having at least two neighbors in B. Then
it follows from Reduction Rule 6.8 that two vertices in B are together contained in the neighborhood of at
most k connected components in G−B. Indeed, each connected component C of G−B with {x, y} ⊆ NG (C)
provides a separate path between x and y. Altogether, the number of connected components in G − B is
upper bounded by |B|2 · (k + 1) ∈ O(k 5 ). Hence, together with Lemma 6.12, we obtain a polynomial kernel
of size O(k 7 ) for SFVS.
With the next lemma, we give an O(k 3 ) upper bound on the number of connected components in G − B.
Lemma 6.13. Let (G, k) and B be as in Lemma 6.10. Then the number of connected components in G − B
is at most 15k 3 + 8k 2 − k − 1.
Proof. We partition the connected components of G−B by the number of their neighbors in B, namely having
exactly one neighbor and having at least two neighbors in B. For x ∈ B, denote by Bx , the set of connected
components in G − B having vertex x as their only neighbor in B. Further, for x, y ∈ B, denote by Bxy , the
set of connected components having
S at least x and y as their neighbors in B. Observe that the connected
components of G − B are exactly {x,y}⊆B (Bx ∪ Bxy ), and hence the number of the connected components
S
S
S
of G − B is at most | x∈B Bx | + | {x,y}⊆B Bxy |. Further observe that | x∈B Bx | ≤ |B|k ≤ 4k 3 + 2k 2 .

25

Hence, it remains to upper-bound the cardinality of
[

[

(Bxy ) =
|

{x,y}⊆B (Bxy ).

[

(Bxy ) ∪
{z

:=B 1

}

|

To this end, observe that

(Bxy ) ∪

x∈F,y∈M ′

{x,y}⊆F

{x,y}⊆B

S

{z

:=B̃ 2

[

(Bxy ) .

(2)

{x,y}⊆M ′

} |

{z

:=B 3

}

Notice that the equality is still true if we replace B̃ 2 by B 2 := B̃ 2 \ B 3 , since B 3 appears in the union on the
right hand-side. Hence, in the remainder of this proof,
the size of the sets B 1 , B 2 , and B 3 .
 we upper-bound
2k
1
3
2
Observe that the size of B is upper bounded by 2 (k + 1) = 2k + k − k.
Next, we upper-bound the size of B 2 . To this end, let x ∈ F be arbitrary but ﬁxed. Consider the set Sx
of vertices in M ′ such that there are at least two connected components of G − B neighboring with both x
and y. Observe that for each y ∈ Sx , the set of connected components in B 2 neighboring with both x and y is
unique, as otherwise there is a connected component in B 2 containing two vertices in M ′ and hence belonging
to B 3 , contradicting our deﬁnition of B 2 := B̃ 2 \ B 3 . Since for each y ∈ Sx there are at least two connected
components in B 2 , they together with x and y form a cycle in G. Hence, due to Reduction Rule 6.6, the
number of vertices in Sx is at most k/2. On the other hand, there are at most k connected components
neighboring with both x and y for any y ∈ Sx due to Reduction Rule 6.8, since each such component provides
a separate path of length at least 2 between x and y. Finally, observe that the number of vertices y ∈ M ′ such
that there is at most one connected component of
PG−B neighboring with both x and y is trivially bounded by
|M ′ | ≤ 4k 2 . Altogether, we obtain that |B 2 |S≤ x∈F (4k 2 +(k/2)(k+1)) ≤ 2k(4k 2 +(k/2)(k+1)) = 9k 3 +k 2 .
Last, we upper-bound the size of B 3 = {x,y}⊆M ′ . Observe that due to Lemma 6.10(ii), for each x, y ∈
′
M each connected component C in Bxy only neighbors with x and y out of M ′ , that is, N (C)∩M ′ = {x, y}.
Moreover, by the connectedness of C, x and y are connected via a path through C. By known facts on
forests and trees, we know that if there are at least r paths connecting vertex pairs out of r vertices in a
graph, then there is a cycle in the graph. Hence, since F is a feedback vertex set in G, there are at most
|M ′ | − 1 connected components in B 3 . Recalling that |M ′ | ≤ 4k 2 , we obtain that |B 3 | ≤ |M ′ | − 1 ≤ 4k 2 − 1.
Altogether, the number of connected components in G − B is at most
[
Bxy | ≤ 4k 3 + 2k 2 + |B 1 | + |B 2 | + |B 3 |
4k 3 + 2k 2 + |
{x,y}⊆B

≤ 4k 3 + 2k 2 + 2k 3 + k 2 − k + 9k 3 + k 2 + 4k 2 − 1
= 15k 3 + 8k 2 − k − 1.
Finally, putting all together, we can prove the the main result of this section.
Proof of Theorem 6.2. Let (G′ , k) be the input instance of SFVS. We compute the 2-core H of G. We
apply Reduction Rules 6.4 to 6.8 exhaustively to obtain an equivalent instance (G, k) such that (G, k) is
reduced. Next we apply Lemma 6.10 and obtain the set B in G with |B| ≤ 4k 2 + 2k. Let C denote the set
of connected components in G − B. By Lemma 6.13, we know that |C| ≤ 15k 3 + 8k 2 − k − 1. Moreover, due
to Lemma 6.12, for each C ∈ C it holds that |V (C)| ≤ (k +1)·(12k +7). If follows that the number of vertices
|V (G)| in G is at most |B|+|C|·maxC∈C |V (C)| ≤ 4k 2 +2k+(15k 3 +8k 2 −k−1)·(k+1)·(12k+7) ∈ O(k 5 ).
6.2. Small Secluded Feedback Vertex Set
In contrast to restricting the closed neighborhood of a feedback vertex set, restricting the open neighborhood by a parameter yields a W[1]-hard problem.
Problem (Small Secluded Feedback Vertex Set).
Input: A graph G = (V, E) and two integers k, ℓ.
Question: Is there a set S ⊆ V such that G − S is cycle-free, |S| ≤ k, and |NG (S)| ≤ ℓ?
Theorem 6.14. Small Secluded Feedback Vertex Set is W[1]-hard with respect to ℓ.
26

k ′ + ℓ vertices in L
...
u
V1

Vk

V2

···

vj2

vi1
{vi1 , vj2 } ∈ E(G)

Figure 2: Sketch of the construction of graph G′ on an input graph G = (V = V1 ∪ . . . ∪ Vk , E) as used in the proof of
Theorem 6.14. The ellipses correspond to cliques with vertex sets Vi , i ∈ {1, . . . , k}.

Proof. We provide a parameterized reduction from Multicolored Independent Set (MIS): given a kpartite graph G = (V, E) and its partite sets V1 ∪. . .∪Vk = V , the question is whether there is an independent
set I of size k such that I ∩ Vi 6= ∅ for each i ∈ {1, . . . , k}. MIS is W[1]-hard when parameterized by the
size k of the independent set [20].
Let G = (V, E) with partite sets V1 ∪ V2 ∪ . . . ∪ Vk = V be an instance of MIS. We can assume that
for each i ∈ {1, . . . , k} we have |Vi | ≥ 2 and there is no edge {v, w} ∈ E with v, w ∈ Vi . We create an
instance (G′ , k ′ , ℓ) of Small Secluded Feedback Vertex Set (SSFVS) with k ′ = |V | − k and ℓ = k + 1
as follows.
Construction: (Refer to Figure 2 for a sketch of the construction.) Initially, let G′ := G. For each
i ∈ {1, . . . , k} turn Vi into a clique, that is, add the edge sets {{a, b} | a, b ∈ Vi , a 6= b}. Next, add to G′ a
vertex u and a set L of k ′ + ℓ vertices. Finally, connect each vertex in V ∪ L to u by an edge.
Correctness: We show that (G, k) is a yes-instance of MIS if and only if (G′ , k ′ , ℓ) is a yes-instance of
SSFVS.
(⇒) Let (G, k) be a yes-instance of MIS and let I ⊆ V with |I| = k be a multicolored independent set
in G. We delete all vertices in S := V (G′ )\ (I ∪L ∪{u}) from G′ . Observe that |S| = |V |− k = k ′ . Moreover,
NG′ (S) = k + 1 = ℓ. Since there is no edge between any two vertices in I, G − S forms a star with center u
and k ′ + ℓ + 1 + k vertices. Since every star is acyclic, (G′ , k ′ , ℓ) is a yes-instance of SSFVS.
(⇐) Let (G′ , k ′ , ℓ) be a yes-instance of SSFVS and let S ⊆ V (G′ ) be a solution. Observe that G′ [Vi ∪{u}]
forms a clique of size |Vi | + 1 for each i ∈ {1, . . . , k}. Since the budget does not allow for deleting the vertex
u (i.e. u 6∈ S), all but at most one vertex in each Vi must be deleted. Since k ′ = |V | − k and |Vi | ≥ 2 for
all i ∈ {1, . . . , k}, S contains exactly |Vi | − 1 vertices of Vi for each i ∈ {1, . . . , k}. Hence, |S| = |V | − k and
NG′ (S) = k + 1 = ℓ. Let F := V \ S denote the set of vertices in V not contained in S. Recall that |F | = k
and |F ∩ Vi | = 1 for all i ∈ {1, . . . , k}. Next, suppose there is an edge between two vertices v, w ∈ F . Since
u 6∈ S and u is incident to all vertices in V , the vertices u, v, w form a triangle in G′ . This contradicts the
fact that S is a solution for (G′ , k ′ , ℓ), that is, that G′ − S is acyclic. It follows that E(G′ [F ]) = ∅, that is,
no two vertices in F are connected by an edge. Together with |F | = k and |F ∩ Vi | = 1 for all i ∈ {1, . . . , k},
it follows that F forms a multicolored independent set in G. Thus, (G, k) is a yes-instance of MIS.
7. Independent Set
For Independent Set, it makes little sense to bound the size of the closed neighborhood from above,
as in this case the empty set always constitutes a solution. One might ask for an independent set with
closed neighborhood as large as possible. However, for any inclusion-wise maximal independent set S, one
has N [S] = V . Hence, this question is also trivial. Therefore, in this section we only consider the following
problem.
27

c

a

c

b

e

a

b

e

d

d

Figure 3: Example of the construction used in the proof of Theorem 7.1. The left-hand side shows the original graph, the
right-hand side the graph constructed by the reduction, where the newly introduced edges between each pair of vertices of the
original graph are drawn in dashed grey. The vertices introduced for each edge of the original graph are ﬁlled red and black,
the corresponding new edges are drawn in black. Note that the enlarged, blue vertices of the original graph form a clique and
that the vertices corresponding to the edges of said clique (enlarged, ﬁlled red) form an independent set in the new graph.

Problem (Large Secluded Independent Set (LSIS)).
Input: A graph G = (V, E) and two integers k, ℓ.
Question: Is there an independent set S ⊆ V such that |S| ≥ k and |NG (S)| ≤ ℓ?
The case ℓ = |V | equals Independent Set and, thus, LSIS is W [1]-hard with respect to k. We show that
LSIS is also W[1]-hard when parameterized by k + ℓ.
Theorem 7.1. Large Secluded Independent Set is W [1]-hard with respect to k + ℓ.
Proof. We provide a polynomial-parameter transformation from Clique parameterized by the solution
size k.
Construction. Let (G, k) be an instance of Clique and assume without loss of generality that k <
|V (G)|−1 (otherwise, solve the instance in polynomial time). We construct an equivalent instance (G′ , k ′ , ℓ′ )
of Large Secluded Independent Set as follows (see Figure 3 for an example). Initially, let G′ be an
empty graph. Add all vertices of G to G′ . Denote the vertex set by V . If two vertices of G are adjacent,
we add a vertex to G′ , that is, G′ additionally to V contains the vertex set X := {xuv | {u, v} ∈ E}. Next,
connect xuv to u and v, that is, add the edge set E ′ = {{u, xuv }, {v, xuv } | {u, v} ∈ E}. Finally, connect

any two vertices in V by an edge. Graph G′ consists of the vertex set V ∪ X and of the edge set E ′ ∪ V2 .

Observe that X forms an independent set in G′ . Set k ′ := k2 and ℓ′ := k. We claim that (G, k) is a
yes-instance of Clique if and only if (G′ , k ′ , ℓ′ ) is a yes-instance of Large Secluded Independent Set.
(⇒) Let C ⊆ V (G) be a clique of size k = |C| in G. We claim that X ′ := {xu,v | u, v ∈ C} forms

an independent set of size k2 with |N (X ′ )| = k = ℓ′ in G′ . Since X ′ ⊆ X, X ′ forms an independent set.


Moreover, since C is a clique of size k, there are k2 edges in G[C], and thus |X ′ | = k2 . By construction,
each vertex in X is only adjacent to vertices in C. Hence, |N (X ′ )| = |C| = k. Therefore, X ′ witnesses that
(G′ , k ′ , ℓ′ ) is a yes-instance of Large Secluded Independent Set.
(⇐) Let U ⊆ V (G′ ) form an independent set of size k ′ with open neighborhood of size upper-bounded
by ℓ′ . Suppose that v ∈ V is contained in U (observe that U contains at most one vertex of V , as otherwise
it would not be independent). Then |N (U )| ≥ |V | − 1 > k = ℓ′ , which contradicts the choice of U . It follows
that U ∩ V = ∅, and hence U ⊆ X. By construction, for each xuv ∈ U , the vertices u, v are contained
in N (U ). Since each vertex in U corresponds to an edge in G, we have k2 edges incident with at most k
vertices. The only graph that fulﬁlls this property is the complete graph on k vertices. Hence, G contains
a clique of size k, and thus (G, k) is a yes-instance of Clique(k).
We remark that the proof above is similar to the W[1]-hardness proof for Cutting ℓ Vertices [36].

28

8. Summary and Future Work
In this paper, we studied the problem of ﬁnding solutions with small neighborhood to classical combinatorial optimization problems in graphs. We presented computational complexity results for secluded and
small secluded variants of s-t-Separator, q-Dominating Set, Feedback Vertex Set, F -free Vertex
Deletion, and for the large secluded variant of Independent Set. In the case of q-Dominating Set,
we leave as an open question the parameterized complexity of Small p-Secluded q-Dominating Set,
with 2p > q, when parameterized by ℓ. Concerning Secluded F -free Vertex Deletion, we would like
to point out that it is an interesting question which families F exactly yield NP-hardness as opposed to
polynomial-time solvability.
A natural way to generalize our results would be to consider vertex-weighted graphs and directed graphs.
This generalization was already investigated by Chechik et al. [12] for Secluded Path and Secluded
Steiner Tree. Furthermore, replacing the bound on the open neighborhood in the case of small secludedness by a bound on the outgoing edges of a solution would be an interesting modiﬁcation of the problem.
The variation follows the idea of the concept of isolation [28, 30, 31, 33]. As the number of outgoing edges is
at least as large as the open neighborhood, this might oﬀer new possibilities for ﬁxed-parameter algorithms.
Finally, we focused on solutions of size at most or at least an integer k and did not discuss the case of size
exactly k so far.
Acknowledgment. This research was initiated at the annual research retreat of the algorithms and complexity
group of TU Berlin, held in Krölpa, Thuringia, Germany, from April 3rd till April 9th , 2016.
We would like to thank the anonymous referees of IPEC for comments that helped to improve the
paper and for pointing us to the work of Fomin et al. [24]. The second author thanks Nikolay Karpov
(St. Petersburg Department of the Steklov Institute of Mathematics of the Russian Academy of Sciences)
for discussion on secluded problems.
Bibliography
References
[1] V. Bafna, P. Berman, and T. Fujito. A 2-approximation algorithm for the undirected feedback vertex set problem. SIAM
Journal on Discrete Mathematics, 12(3):289–297, 1999. doi:10.1137/S0895480196305124. Cited on page 24.
[2] R. van Bevern.
Fixed-Parameter Linear-Time Algorithms for NP-hard Graph and Hypergraph Problems Arising in Industrial Applications, volume 1 of Foundations of Computing. Universitätsverlag der TU Berlin, 2014.
doi:10.14279/depositonce-4131. Cited on page 19.
[3] R. van Bevern. Towards optimal and expressive kernelization for d-Hitting Set. Algorithmica, 70(1):129–147, 2014.
doi:10.1007/s00453-013-9774-3. Cited on pages 19 and 20.
[4] R. van Bevern, H. Moser, and R. Niedermeier. Approximation and tidying—a problem kernel for s-Plex Cluster Vertex
Deletion. Algorithmica, 62(3-4):930–950, 2012. ISSN 0178-4617. doi:10.1007/s00453-011-9492-7. Cited on page 18.
[5] R. van Bevern, T. Fluschnik, G. B. Mertzios, H. Molter, M. Sorge, and O. Suchý. Finding secluded places of
special interest in graphs. In Proc. 11th IPEC, volume 63 of LIPIcs, pages 5:1–5:16. Schloss Dagstuhl, 2017.
doi:10.4230/LIPIcs.IPEC.2016.5. Cited on page 1.
[6] H. L. Bodlaender, P. G. Drange, M. S. Dregi, F. V. Fomin, D. Lokshtanov, and M. Pilipczuk. A ck n 5-approximation
algorithm for treewidth. SIAM Journal on Computing, 45:317–378, 2016. doi:10.1137/130947374. Cited on page 12.
[7] M. Bruglieri, M. Ehrgott, H. W. Hamacher, and F. Maﬃoli. An annotated bibliography of combinatorial optimization problems with ﬁxed cardinality constraints.
Discrete Applied Mathematics, 154(9):1344–1357, 2006.
doi:10.1016/j.dam.2005.05.036. Cited on page 4.
[8] T. N. Bui and C. Jones. Finding good approximate vertex and edge partitions is NP-hard. Information Processing Letters,
42(3):153–159, 1992. doi:10.1016/0020-0190(92)90140-Q. Cited on page 3.
[9] L. Cai. Fixed-parameter tractability of graph modiﬁcation problems for hereditary properties. Information Processing
Letters, 58(4):171–176, 1996. doi:10.1016/0020-0190(96)00050-6. Cited on pages 19 and 20.
[10] L. Cai. Parameterized Complexity of Cardinality Constrained Optimization Problems. The Computer Journal, 51(1):
102–121, 2008. doi:10.1093/comjnl/bxm086. Cited on page 4.
[11] L. Cai, S. M. Chan, and S. O. Chan. Random Separation: A New Method for Solving Fixed-Cardinality Optimization
Problems. In Proc. 2nd IWPEC, pages 239–250. Springer, 2006. doi:10.1007/11847250_22. Cited on pages 4 and 9.
[12] S. Chechik, M. P. Johnson, M. Parter, and D. Peleg.
Secluded connectivity problems.
Algorithmica, 2016.
doi:10.1007/s00453-016-0222-z. In press. Cited on pages 1, 2, 3, and 29.

29

[13] B. Courcelle. The monadic second-order logic of graphs. I. Recognizable sets of ﬁnite graphs. Information and Computation,
85(1):12–75, 1990. doi:10.1016/0890-5401(90)90043-H. Cited on page 8.
[14] M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh. Parameterized
Algorithms. Springer, 2015. doi:10.1007/978-3-319-21275-3. Cited on pages 5 and 6.
[15] R. Diestel. Graph Theory, volume 173 of Graduate Texts in Mathematics. Springer, 4th edition, 2010. Cited on page 5.
[16] M. Dom, D. Lokshtanov, and S. Saurabh. Kernelization lower bounds through colors and IDs. ACM Transactions on
Algorithms, 11(2):13, 2014. doi:10.1145/2650261. Cited on page 13.
[17] R. Downey, V. Estivill-Castro, M. Fellows, E. Prieto, and F. Rosamond. Cutting up is hard to do: the parameterized complexity of k-Cut and related problems. Electronic Notes in Theoretical Computer Science, 78:209–222, 2003.
doi:10.1016/S1571-0661(04)81014-4. Cited on page 4.
[18] R. G. Downey and M. R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer,
2013. doi:10.1007/978-1-4471-5559-1. Cited on page 5.
[19] S. Faﬁanie and S. Kratsch. A shortcut to (sun)ﬂowers: Kernels in logarithmic space or linear time. In Proc. 40th MFCS,
volume 9235 of LNCS, pages 299–310. Springer, 2015. doi:10.1007/978-3-662-48054-0_25. Cited on pages 19 and 20.
[20] M. Fellows, D. Hermelin, F. Rosamond, and S. Vialette. On the parameterized complexity of multiple-interval graph
problems. Theoretical Computer Science, 410(1):53–61, 2009. doi:10.1016/j.tcs.2008.09.065. Cited on page 27.
[21] M. Fellows, J. Guo, H. Moser, and R. Niedermeier. A complexity dichotomy for ﬁnding disjoint solutions of vertex deletion
problems. ACM Transactions on Computation Theory, 2(2):5, 2011. doi:10.1145/1944857.1944860. Cited on page 19.
[22] J. Flum and M. Grohe. Parameterized Complexity Theory. Springer, 2006. doi:10.1007/3-540-29953-X. Cited on page 5.
[23] F. Fomin, D. Lokshtanov, N. Misra, and S. Saurabh. Planar F-Deletion: Approximation, kernelization and optimal FPT
algorithms. In Proc. 56th FOCS, pages 470–479. IEEE Computer Society, 2012. doi:10.1109/FOCS.2012.62. Cited on
page 24.
[24] F. Fomin, P. Golovach, and J. Korhonen. On the parameterized complexity of cutting a few vertices from a graph. In
Proc. 38th MFCS, volume 8087 of LNCS, pages 421–432. Springer, 2013. doi:10.1007/978-3-642-40313-2_38. Cited on
pages 3, 4, 7, 8, and 29.
[25] F. V. Fomin, P. A. Golovach, N. Karpov, and A. S. Kulikov. Parameterized complexity of secluded connectivity problems.
Theory of Computing Systems, 2016. doi:10.1007/s00224-016-9717-x. In press. Cited on pages 2 and 3.
[26] M. Gaertler. Clustering. In U. Brandes and T. Erlebach, editors, Network Analysis: Methodological Foundations [outcome
of a Dagstuhl seminar, 13-16 April 2004], volume 3418 of LNCS, pages 178–215. Springer, 2004. ISBN 3-540-24979-6.
doi:10.1007/978-3-540-31955-9_8. Cited on page 2.
[27] A. C. Giannopoulou, D. Lokshtanov, S. Saurabh, and O. Suchý. Tree deletion set has a polynomial kernel (but no OPTO(1)
approximation). SIAM Journal on Discrete Mathematics, 30(3):1371–1384, 2016. doi:10.1137/15M1038876. Cited on
pages 22, 23, and 24.
[28] F. Hüﬀner, C. Komusiewicz, H. Moser, and R. Niedermeier. Isolation concepts for clique enumeration: Comparison and
computational experiments. Theoretical Computer Science, 410(52):5384–5397, 2009. doi:10.1016/j.tcs.2009.05.008. Cited
on pages 2, 4, and 29.
[29] F. Hüﬀner, C. Komusiewicz, H. Moser, and R. Niedermeier. Fixed-parameter algorithms for cluster vertex deletion. Theory
of Computing Systems, 47(1):196–217, 2010. doi:10.1007/s00224-008-9150-x. Cited on page 18.
[30] F. Hüﬀner, C. Komusiewicz, and M. Sorge. Finding highly connected subgraphs. In Proc. 41st SOFSEM, volume 8939 of
LNCS, pages 254–265. Springer, 2015. doi:10.1007/978-3-662-46078-8_21. Cited on pages 2, 4, and 29.
[31] H. Ito, K. Iwama, and T. Osumi. Linear-time enumeration of isolated cliques. In Proc. 13th ESA, volume 3669 of LNCS,
pages 119–130. Springer, 2005. doi:10.1007/11561071_13. Cited on pages 2, 4, and 29.
[32] C. Komusiewicz and M. Sorge. An algorithmic framework for ﬁxed-cardinality optimization in sparse graphs applied to
dense subgraph problems. Discrete Applied Mathematics, 193:145–161, 2015. doi:10.1016/j.dam.2015.04.029. Cited on
page 4.
[33] C. Komusiewicz, F. Hüﬀner, H. Moser, and R. Niedermeier. Isolation concepts for eﬃciently enumerating dense subgraphs.
Theoretical Computer Science, 410(38-40):3640–3654, 2009. doi:10.1016/j.tcs.2009.04.021. Cited on pages 2, 4, and 29.
[34] J. Lewis and M. Yannakakis. The node-deletion problem for hereditary properties is NP-complete. Journal of Computer
and System Sciences, 20(2):219–230, 1980. doi:10.1016/0022-0000(80)90060-4. Cited on page 19.
[35] D. Lokshtanov, N. Misra, G. Philip, M. Ramanujan, and S. Saurabh. Hardness of r-dominating set on graphs of diameter
(r + 1). In Proc. 8th IPEC, volume 8246 of LNCS, pages 255–267. Springer, 2013. doi:10.1007/978-3-319-03898-8_22.
Cited on page 13.
[36] D. Marx.
Parameterized graph separation problems.
Theoretical Computer Science, 351(3):394–406, 2006.
doi:10.1016/j.tcs.2005.10.007. Cited on pages 3 and 28.
[37] D. Marx, B. O’Sullivan, and I. Razgon. Finding Small Separators in Linear Time via Treewidth Reduction. ACM
Transactions on Algorithms, 9(4):30:1–30:35, 2013. doi:10.1145/2500119. Cited on page 9.
[38] M. Naor, L. J. Schulman, and A. Srinivasan. Splitters and near-optimal derandomization. In Proceedings of IEEE 36th
Annual Foundations of Computer Science, pages 182–191. IEEE Computer Society, 1995. doi:10.1109/SFCS.1995.492475.
Cited on page 9.
[39] R. Niedermeier.
Invitation to Fixed-Parameter Algorithms.
Oxford University Press,
2006.
doi:10.1093/acprof:oso/9780198566076.001.0001. Cited on page 5.
[40] S. Seidman.
Network structure and minimum degree.
Social Networks,
5(3):269–287,
1983.
doi:10.1016/0378-8733(83)90028-X. Cited on page 22.
[41] S. Thomassé.
A 4k 2 kernel for feedback vertex set.
ACM Transactions on Algorithms, 6(2), 2010.
doi:10.1145/1721837.1721848. Cited on page 23.

30

[42] D. B. West. Introduction to Graph Theory. Prentice Hall, 2 edition, 2000. Cited on page 5.

31

