Fractals for Kernelization Lower Bounds∗
Till Fluschnik† ,1 , Danny Hermelin‡,2 , André Nichterlein1 , and Rolf Niedermeier1

arXiv:1512.00333v3 [cs.CC] 22 Dec 2017

1

Institut für Softwaretechnik und Theoretische Informatik, TU Berlin, Germany, {till.fluschnik,
andre.nichterlein, rolf.niedermeier}@tu-berlin.de
2
Department of Industrial Engineering and Management, Ben-Gurion University of the Negev, Israel,
hermelin@bgu.ac.il

Abstract
The composition technique is a popular method for excluding polynomial-size problem kernels
for NP-hard parameterized problems. We present a new technique exploiting triangle-based
fractal structures for extending the range of applicability of compositions. Our technique
makes it possible to prove new no-polynomial-kernel results for a number of problems dealing
with length-bounded cuts. In particular, answering an open question of Golovach and Thilikos
[Discrete Optim. 2011], we show that, unless NP ⊆ coNP / poly, the NP-hard LengthBounded Edge-Cut (LBEC) problem (delete at most k edges such that the resulting graph
has no s-t path of length shorter than ℓ) parameterized by the combination of k and ℓ has no
polynomial-size problem kernel. Our framework applies to planar as well as directed variants
of the basic problems and also applies to both edge and vertex deletion problems. Along the
way, we show that LBEC remains NP-hard on planar graphs, a result which we believe is
interesting in its own right.
Keywords: Parameterized complexity; polynomial-time data reduction; lower bounds; crosscompositions; graph modification problems; interdiction problems.

1

Introduction

Lower bounds are of central concern all over computational complexity analysis. With respect to
ﬁxed-parameter tractable problems [14, 19, 23, 40], currently there are two main streams in this
context:
(i) ETH-based lower bounds for the running times of exact algorithms [34] and
(ii) lower bounds on problem kernel sizes; more speciﬁcally, the exclusion of polynomial-size
problem kernels [33].
Both research directions for lower bounds rely on plausible complexity-theoretic assumptions,
namely the Exponential-Time Hypothesis (ETH) and NP 6⊆ coNP / poly, respectively. In this
work, we contribute to the second research direction, developing a new technique that exploits a
triangle-based fractal structure in order to exclude polynomial-size problem kernels (polynomial
kernels for short) for edge and vertex deletion problems in the context of length-bounded cuts.
∗ An extended abstract appeared in Proc. of the 43rd International Colloquium on Automata, Languages, and
Programming (ICALP 2016).
† Till Fluschnik acknowledges support by the DFG, project DAMM (NI 369/13-2).
‡ Danny Hermelin was supported by a DFG Mercator fellowship within the project DAMM (NI 369/13-2) while
staying at TU Berlin (August 2015). He has also received funding from 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).

1

Kernelization is a key method for designing ﬁxed-parameter algorithms [29, 33]; among all techniques of parameterized algorithm design, it has the presumably greatest potential for delivering
practically relevant algorithms. Hence, it is of key interest to explore its power and its limitations.
In a nutshell, the fundamental idea of kernelization is as follows. Given a parameterized problem
instance I with parameter k, in polynomial time preprocess I by applying data reduction rules
in order to simplify it and reduce it to an “equivalent” instance (the so-called (problem) kernel)
of the same problem. For NP-hard problems, the best one can hope for is a problem kernel of
size polynomial (or linear) in the parameter k. In a way, one may interpret kernelization (requested to run in polynomial time) as an “exact counterpart” of polynomial-time approximation
algorithms. Indeed, linear-size problem kernels often imply constant-factor approximation algorithms [37, page 15]. Approximation algorithmics has a highly developed theory (having produced
concepts such as MaxSNP-hardness and the famous PCP theory) for proving (relative to some
plausible complexity-theoretic assumption) lower bounds on the approximation factors [1, 44, 46].
We remark that there exist frameworks combining kernelization and approximation algorithms,
namely α-ﬁdelity kernelization [22] and lossy kernelization [35].
It is fair to say that in the younger ﬁeld of kernelization the arsenal for proving lower bounds
(particularly excluding polynomial kernels) so far is of smaller scope and needs further development. The ﬁrst results in this context were rather limited, and used approximation lower
bounds [13]. Following these, Bodlaender et al. [8] (using a lemma by Fortnow and Santhanam [25])
excluded polynomial kernels for several problems, such as Longest Path parameterized by solution size, under the assumption NP 6⊆ coNP / poly. The core tool for showing these are so-called
“OR-compositions”. The applicability of OR-compositions has meanwhile been developed further
in several other works, e.g. [10, 11, 18]. Dell and van Melkebeek [16] introduced a related framework that also allows to give lower bounds on the degree of the polynomial for problems admitting
a polynomial kernel. Finally, Drucker [20] recently showed that “AND-compositions” can also be
used to exclude polynomial kernels.
Next, we discuss in some more detail OR-compositions. Roughly speaking, the idea behind
an OR-composition for a parameterized problem is to encode the logical “or” of t instances with
parameter value k into a single instance of the same problem with parameter value k ′ = k O(1) log t.
In particular, given t instances, the obtained instance is a yes-instance if and only if at least one
of the given instances is a yes-instance. In this way an OR-composition can be viewed as a
polynomial-time computable OR-gate. An OR-composition for an NP-hard problem, along with
a polynomial kernel for the same problem, implies NP ⊆ coNP / poly [8, 25].
While for some problems, for example Longest Path with parameter solution size [8], a
simple disjoint union yields the desired OR-composition, other problems seem to require involved
constructions, for example Set Cover with parameter universe size [18]. Indeed, devising a ORcomposition can be quite challenging and the task becomes even harder when considering several,
seemingly orthogonal parameterizations at once.
To illustrate the problem with such combined parameters, let us consider the NP-hard problem
Length-Bounded Edge-Cut (LBEC). Herein, an undirected graph G = (V, E) with s, t ∈ V ,
and two integers k, ℓ ∈ N are given, and the question is whether it is possible to delete at most k
edges such that the shortest s-t path is of length at least ℓ. Using a simple branching algorithm, one
can show that LBEC(k, ℓ) is ﬁxed-parameter tractable for the combined parameter (k, ℓ) [4, 27].
Golovach and Thilikos [27] posed as an open problem whether LBEC(k, ℓ) admits a polynomial
kernel. To exclude the existence of a polynomial kernel for LBEC(k, ℓ), we would like to apply
the OR-composition framework to the problem.
A standard approach for applying the OR-composition technique to a problem like LBEC
would be to concatenate the input instances on the source and sink vertices, what one might refer
to as “serial composition” (see, e.g., [15, 24]). To this end, one needs some additional gadgets to
ensure that only in one instance edges are deleted. This form of composition, however, induces a
dependency of the second parameter ℓ on the number of instances, which is not allowed. Another
standard approach is introducing a global sink and source vertex, and connecting all source vertices
with the global source and all sink vertices with the global sink, what one might refer to as
a “parallel composition”. This form of composition would keep ℓ small enough, but induces a
2

Problem

edge deletion
directed
planar/general

LBEC(k, ℓ)
MDED(k, ℓ)
DSCT(k, ℓ)

No PK [Thm. 4/Thm. 2]
No PK [Thm. 8]
No PK [Thm. 11/Thm. 10]

planar

undirected
/general

No PK [Thm. 4/Thm. 1]
No PK [Thm. 7/Thm. 6]
PK [47]
?

Table 1: Survey of the concrete results of this paper (under the assumption that NP 6⊆
coNP / poly). PK stands for polynomial kernel and a “?” indicates that it is open whether a
polynomial kernel exists. We remark that the no-polynomial-kernel results for LBEC(k, ℓ) on
directed graphs still hold for directed acyclic graphs. Moreover, the results for the undirected
variants also hold for the combined parameter (k, ℓ, ω), where ω denotes the treewidth. Note that
we claim without proof that, except for the planar variants, our proofs also transfer to the vertex
deletion case, both for directed and undirected graphs.
dependency of the ﬁrst parameter k on the number of instances. Summarizing, the parameter k
seems to ask for a serial composition and the parameter ℓ seems to ask for a parallel composition.
For some problems using a tree as “instance selector” was helpful, see for example Bevern et al. [6]
or Bazgan et al. [3]. The problem with trees is that they introduce small (constant-size) s-t cuts,
which is problematic for Length-Bounded Edge-Cut.
In this work, we introduce a fractal structure as an instance selector which has the nice properties of trees but does not introduce small cuts. Our fractal structure allows avoiding the issues
discussed above for serial and parallel compositions. Thus, it can be used for excluding a polynomial kernel for LBEC, as well as for other problems. We mention that one can ﬁnd the fractal
structure in a proof by Guillemot et al. [28] refuting the existence of a polynomial kernel for a
graph-coloring problem.
Our contributions. Our main technical contribution is to introduce a family of graphs that
we call T-fractals and that build on triangles. T-fractals feature a fractal-like structure, in the sense
of self-similarity and scale-invariance. Using these T-fractals in OR-cross-compositions, we show
that the following parameterized graph modiﬁcation problems (deﬁnitions are stated subsequently)
and several of their variants do not admit polynomial kernels (unless NP ⊆ coNP / poly):
• Length-Bounded Edge-Cut(k, ℓ) (LBEC(k, ℓ));
• Minimum Diameter Edge Deletion(k, ℓ) (MDED(k, ℓ));
• Directed Small Cycle Transversal(k, ℓ) (DSCT(k, ℓ));
Table 1 surveys our no-polynomial-kernel results and spots an open question.
The graph edge-modiﬁcation problems Length-Bounded Edge-Cut (LBEC), Minimum
Diameter Edge Deletion (MDED), and Directed Small Cycle Transversal (DSCT)
are deﬁned as follows. The LBEC problem asks, given an undirected graph G = (V, E), two
vertices s, t ∈ V , and two integers k, ℓ, whether there are at most k edge deletions such that the
shortest s-t path is of length at least ℓ. The MDED problem asks, given an undirected connected
graph G = (V, E) and two integers k, ℓ, whether there are at most k edge deletions such that the
remaining graph remains connected and has diameter at least ℓ. The DSCT problem asks, given
a directed graph G = (V, E) and two integers k, ℓ, whether there are at most k edge deletions such
that the remaining graph has no cycle of length smaller than ℓ. In addition, we consider several
variants (planar, directed, vertex deletion) of these problems. We remark that we also show that
for the undirected (planar) variants, unless NP 6⊆ coNP / poly, LBEC and MDED parameterized
by (k, ℓ, ω) do not admit a polynomial kernel, where ω denotes the treewidth of the underlying
graph G.

3

2

Preliminaries

We use standard notation from parameterized complexity [14, 19, 23, 40] and graph theory [17, 45].
Throughout this paper we denote by log the logarithm with base two.
Graph Theory. Let G = (V, E) be a graph. 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 ). For C ⊆ V (G) (C ⊆ E(G))
we write G − C for the graph G where all vertices (edges) in C are deleted. Note that the deletion
of a vertex implies the deletion of all its incident edges.
A cycle is a connected graph where every vertex has degree exactly two. The length of a cycle
is the number of edges in the cycle. In directed graphs, a cycle is a connected graph where every
vertex has outdegree and indegree exactly one. The girth of a graph G is the length of the shortest
cycle (contained) in G.
A tree is a simple, connected and cycle-free graph. A path is a tree with no vertex of degree at
least three. We call the vertices with degree one the endpoints of the path. An s-t path is a path
where the vertices s and t are the endpoints of the path. The length of a path is the number of
edges in the path. In directed graphs, an s-t path is a path where all arcs are directed toward t.
The diameter of a graph G is the maximum length of any shortest v-w path over all v, w ∈ V (G),
v 6= w.
Let G be an undirected, connected graph. An edge cut C ⊆ E(G) is a set of edges such that
the graph G − C is not connected. Let s, t ∈ V (G) be two vertices in G. An s-t edge cut C is an
edge cut such that the vertices s and t are not connected in G − C. If G is a directed graph, then
C ⊆ E(G) is an s-t edge cut if there is no s-t path in G − C. An s-t edge cut C is called minimal
if C\{e} is not an s-t edge cut in G for all e ∈ C. An s-t edge cut C is called minimum if there is
no s-t edge cut C ′ in G such that |C ′ | < |C|.
Given a graph G = (V, E) and two non-adjacent vertices v, w ∈ V , we say we merge the vertices
v and w if we add a new vertex vw to V as well as the edge set {{vw, x} | {x, v} ∈ E} ∪ {{vw, x} |
{x, w} ∈ E} to E, and we delete the vertices v and w and all incident edges to v and w.
Parameterized Complexity. A parameterized problem is a set of instances (I, k) where
I ∈ Σ∗ for a ﬁnite alphabet Σ, and k ∈ N is the parameter. A parameterized problem L is fixedparameter tractable (fpt) if it can be decided in f (k) · |I|O(1) time whether (I, k) ∈ L, where f
is a computable function only depending on k. We say that two instances (I, k) and (I ′ , k ′ ) of
parameterized problems P and P ′ are equivalent if (I, k) is yes for P if and only if (I ′ , k ′ ) is
yes for P ′ . A kernelization is an algorithm that, given an instance (I, k) of a parameterized
problem P , computes in polynomial time an equivalent instance (I ′ , k ′ ) of P (the kernel ) such
that |I ′ |+k ′ ≤ f (k) for some computable function f only depending on k. We say that f measures
the size of the kernel, and if f ∈ k O(1) , we say that P admits a polynomial kernel. We remark
that a decidable parameterized problem is ﬁxed-parameter tractable if and only if it admits a
kernel [12].
In this paper we use the framework of Bodlaender et al. [10] which extends the notion of ORcomposition to OR-cross-composition. Given an NP-hard problem L, an equivalence relation R
on the instance of 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
(ii) for any ﬁnite set S of instances, R partitions the set into at most (maxx∈S |x|)O(1) equivalence
classes.
Definition 1. Given an NP-hard problem L, a parameterized problem P , and a polynomial equivalence relation R on the instances of L, an OR-cross-composition of L into P (with respect to R) is
an P
algorithm that takes ℓ R-equivalent instances I1 , . . . , Iℓ of L and constructs in time polynomial
in ℓi=1 |Iℓ | an instance (I, k) such that
4

σ

τ

σ

τ

σ

σ

τ

τ

Figure 1: T-fractals △1 , △2 , △3 , △4 . The two special vertices σ and τ are highlighted by empty
circles.
1. k is polynomially upper-bounded in max1≤i≤ℓ |Ii | + log(ℓ) and
2. (I, k) is yes for P if and only if there is at least one ℓ′ ∈ [ℓ] such that Iℓ′ is yes for L.
If a parameterized problem P admits an OR-cross-composition for some NP-hard problem L,
then P does not admit a polynomial kernel with respect to its parameterization, unless NP ⊆
coNP / poly [10]. We remark that we can assume that ℓ = 2j for some j ∈ N since we can add
trivial no-instances from the same equivalence class to reach a power of two. We refer to the
survey of Kratsch [33] for an overview on kernelization and lower bounds.

3

The “Fractalism” Technique

In this section, we describe our new technique based on triangle fractals (T-fractals for short).
We provide a general construction scheme for cross-compositions using T-fractals. To this end, we
ﬁrst deﬁne T-fractals and then discuss several of their properties in Section 3.1. Furthermore, we
present in Section 3.2 a directed variant and provide two “construction manuals” for an application
of T-fractals in cross-compositions in Section 3.3.
Roughly speaking, a T-fractal can be constructed by iteratively putting triangles on top of
each other, see Figure 1 for four examples.
Definition 2. For q ≥ 1, the q-T-fractal △q is the graph constructed as follows:
(1) Set △0 := {σ, τ } with {σ, τ } being a “marked edge” with endpoints σ and τ , subsequently
referred to as special vertices.
(2) Let F be the set of marked edges.
(3) For each edge e ∈ F , add a new vertex and connect it by two new edges with the endpoints
of e, and mark the two added edges.
(4) Unmark all edges in F .
(5) Repeat (2)-(4) q − 1 times.
The fractal structure of △q might be easier to see when considering the following equivalent
recursive deﬁnition of △q : For the base case we deﬁne △0 := {σ, τ } as in Deﬁnition 2. Then,
the q-T-fractal △q is constructed as follows. Take two (q − 1)-T-fractals △′q−1 and △′′q−1 , where
σ ′ , τ ′ and σ ′′ , τ ′′ are the special vertices of △′q−1 and △′′q−1 , respectively. Then △q is obtained
by merging the vertices τ ′ and σ ′′ , adding the edge {σ ′ , τ ′′ }, and setting σ = σ ′ and τ = τ ′′ as

5

σ

τ

Figure 2: Highlighting the diﬀerent boundaries of △4 by line-types (solid: boundary B0 ; dashed:
boundary B1 ; dotted: boundary B2 ; dash-dotted: boundary B3 ; dash-dot-dotted: boundary B4 ).
the special vertices of △q . We remark that we make use of the recursive structure in later proofs.
However, by construction, we immediately obtain the following (for the latter, see e.g. [7]).
Observation 1. The T-fractal is outerplanar and hence the treewidth of △q is ω(△q ) ≤ 2 for
every q ∈ N.
In the ith execution of (2)-(4) in Deﬁnition 2, we obtain 2i−1 new triangles. We say that these
triangles have depth i. The boundary Bi ⊆ E(△q ), i ∈ [q], are those edges of the triangles of depth
i which are not edges of the triangles of depth i − 1. As a convention, the edge {σ, τ } connecting
the two special vertices σ and τ forms the boundary B0 . We refer to Figure 2 for an illustration
of the boundaries in the T-fractal △4 . Moreover, by construction, we obtain the following:
Observation 2. In every T-fractal, each boundary forms a σ-τ path, and all boundaries are
pairwise edge-disjoint.
Note that the boundary Bq contains p = 2q edges. Thus, the number of edges in △q
P
q
i
q+1
is
− 1 = 2 · p − 1. Further observe that all vertices of △q are incident with
i=0 2 = 2
the edges in Bq , and Bq forms a σ-τ path. Hence, △q contains p + 1 vertices.
Reducing the Weighted to the Unweighted Case. The weighted T-fractal is the Tfractal equipped with edge costs, that is, the cost for deleting an edge in the T-fractal. If all edges
in △q are of the same edge cost c ∈ N, then we write △cq (we drop the superscript if c = 1). In
the remainder of the paper, we focus on the unweighted case of T-fractals without multiple edges
or loops. This is possible due to the following reduction of the weighted to the unweighted case.
Consider the weighted T-fractal △cq with c ≥ 2. To reduce to the case with an unweighted, simple
graph, we add c−1 further copies for each edge. Thus, to make two adjacent vertices non-adjacent,
it requires c edge-deletions. To make the graph simple, we subdivide each edge. We remark that
in this way we double the distances of the vertices in the original T-fractal. Thus, whenever we
consider distances in the fractal with edge cost and the graph obtained by the reduction above,
we have to take into account a factor of two.
Finally, let us remark that the treewidth of the graph G obtained by the modiﬁcation of the
T-fractal described above remains at most two, though it is not necessarily outerplanar anymore.
To see this, observe that outerplanar graphs are series-parallel. Moreover, a graph obtained by
replacing an edge in a series-parallel graph by a number of paths with the same endpoints remains
series-parallel. It follows that G has treewidth at most two.

3.1

Properties of T-Fractals

The goal of this subsection is to prove several properties of T-fractals that are used in later
constructions. Some key properties of T-fractals appear in the context of σ-τ edge cuts in △q . To
prove other properties, we later introduce the notion of the dual structure behind the T-fractals.
6

σ

τ

σ

τ

Figure 3: Left: The T-fractal △3 (circles and solid lines) and its dual graph (squares and dotted
lines). The ﬁlled square is the vertex dual to the outer face in the dual graph. Right: The Tfractal △3 (circles and solid lines) and its dual structure T3 , illustrated by squares and dotted
lines, where the ﬁlled square corresponds to the root of the dual structure.
The minimum edge cuts in △q will play a central role when using T-fractals in cross-compositions
since the minimum edge cuts serve as instance selectors (see Section 3.3). First, we discuss the
size and structure of the minimum edge cuts in △q .
Lemma 1. Every minimum σ-τ edge cut in △q is of size q + 1.
Proof. Let C be a minimum σ-τ edge cut in △q . Note that the degrees of σ and τ are exactly q +1,
and thus |C| ≤ q+1. Moreover, the boundaries in △q are pairwise edge-disjoint and each boundary
forms a σ-τ path (Observation 2). Since △q contains q + 1 boundaries, it follows that there are
at least q + 1 disjoint σ-τ paths in △q . Menger’s theorem [38] states that in a graph with distinct
source and sink, the maximum number of disjoint source-sink paths equals the minimum size of any
source-sink edge cut. Thus, by Menger’s theorem, it follows that |C| ≥ q+1. Hence |C| = q+1.
From the fact that the boundaries are pairwise edge-disjoint and each boundary forms a στ path, we can immediately derive the following from Lemma 1.
Corollary 1. Every minimum σ-τ edge cut in △q contains exactly one edge of each boundary.
In the following we describe a (hidden) dual structure in △q , that is, a complete binary tree
with p leaves. We refer to Figure 3 for an example of the dual structure in △3 . To talk about
the dual structure by means of duality of plane graphs, we need a plane embedding of △q . Hence
we assume that △q is embedded as in Figure 1 (iteratively extended). By Tq we denote the dual
structure in △q , where the vertex dual to the outer face is replaced by p + 1 vertices (split vertices)
such that each edge incident with the dual vertex is incident with exactly one split vertex. We
consider the split vertex incident with the vertex dual to the triangle containing the edge {σ, τ }
as the root vertex of the dual structure Tq . Thus, the other split vertices correspond to the leaves
of the dual structure Tq . Note that the depth of a triangle one-to-one corresponds to the depth of
the dual vertex in Tq .
Observe that there is a one-to-one correspondence between the edges in Tq and the edges in △q .
The following lemma states duality of root-leaf paths in Tq and minimum σ-τ edge cuts in △q ,
demonstrating the utility of the dual structure Tq .
Lemma 2. There is a one-to-one correspondence between root-leaf paths in the dual structure Tq
of △q and minimum σ-τ edge cuts in △q . Moreover, there are exactly p = 2q pairwise different
minimum σ-τ edge cuts in △q .
Proof. Observe that each path from the root to a leaf in the dual structure Tq corresponds to
a cycle in the dual graph. It is well-known that there is a one-to-one correspondence between
minimal edge cuts in a plane graph and cycles in its dual graph [17, Proposition 4.6.1]. Herein,
every cycle in the dual graph that “cuts” the edge {σ, τ } in △q is a root-leaf path in Tq . Thus,
the only minimal σ-τ edge cuts are those corresponding to the root-leaf paths. By the one-to-one
7

correspondence of the depth of the triangles in △q and the depth of the vertices in Tq , these
edge cuts are of cardinality q + 1. Hence, by Lemma 1, these edge cuts are minimum edge cuts.
Since |Bq | = p, there are exactly p leaves in Tq , and thus there are exactly p diﬀerent root-leaf
paths in Tq . It follows that the number of pairwise diﬀerent minimum σ-τ edge cuts in △q is
exactly p = 2q .
Further, we obtain the following.
Lemma 3. Let C be a minimum σ-τ edge cut in △q . Let {x, y} = C ∩ Bq , where x is in the same
connected component as σ in △q − C. Then dist(σ, x) + dist(y, τ ) = q in △q − C.
Proof. We prove the lemma by induction on q. For the base case q = 0, observe that C = {σ, τ }
and dist△0 −C (σ, x) + dist△0 −C (y, τ ) = 0.
For the induction step, assume that the statement of the lemma is true for △q−1 . Now, let C
be a minimum σ-τ edge cut in △q . Hence, {σ, τ } ∈ C. Denote by u the (unique) vertex that is
adjacent to the two special vertices σ and τ . Let △′q−1 and △′′q−1 be the two (q − 1)-T-subfractals
of △q , so that △′q−1 (△′′q−1 ) has the special vertices σ and u (u and τ ). By Lemma 2, the
minimum σ-τ edge cut C corresponds to a root-leaf path in Tq . Hence, C ′ := C \ {σ, τ } is either
a subset of E(△′q−1 ) or of E(△′′q−1 ). Assume w.l.o.g. that C ′ ⊆ E(△′q−1 ). It follows from the
induction hypothesis that dist△′q−1 −C ′ (σ, x) + dist△′q−1 −C ′ (y, u) = q − 1. Since dist△q −C (y, τ ) =
dist△′q−1 −C ′ (y, u) + 1, it follows that dist△q −C (σ, x) + dist△q −C (y, τ ) = q.
Remark 1. By an inductive proof like the one of Lemma 3, one can easily show that the maximum
degree ∆ of △q is exactly 2·q for q > 0. Moreover, due to Lemma 3, the diameter of △q is bounded
in O(q).
Another observation on △q is that any deletion of d edges increases the length of any shortest
σ-τ path to at most d + 1, unless the edge deletion forms a σ-τ edge cut.
Lemma 4. Let D ⊆ E(△q ) be a subset of edges of △q . If D is not a σ-τ edge cut, then there is
a σ-τ path of length at most |D| + 1 in △q − D.
Proof. We prove the statement of the lemma by induction on q. For the induction base with q = 0,
observe that since D is not a σ-τ edge cut, it follows that D = ∅ and, hence, σ and τ have distance
one.
For the induction step, assume that the statement of the lemma is true for △q−1 . Now,
let D ⊆ E(△q ) be a subset of edges of △q such that D is not a σ-τ edge cut. If {σ, τ } ∈
/ D,
then there is a σ-τ path of length one and the statement of the lemma holds. Now consider the
case {σ, τ } ∈ D. Denote by u the (unique) vertex that is adjacent to the two special vertices σ
and τ . If {σ, τ } ∈ D, then every σ-τ path in △q − D contains u and hence dist△q −D (σ, τ ) =
dist△q −D (σ, u) + dist△q −D (u, τ ). (If there is no σ-u-path or no u-τ -path in △q − D, then D is
a σ-τ edge cut; a contradiction to the assumption of the lemma.) Now let △′q−1 and △′′q−1 be
the two (q − 1)-T-subfractals of △q , so that △′q−1 (△′′q−1 ) has the special vertices σ and u (u
and τ ). It follows that D can be partitioned into D = D′ ∪ D′′ ∪ {σ, τ } with D′ ⊆ E(△′q−1 )
and D′′ ⊆ E(△′′q−1 ). By induction hypothesis, it follows that there is a σ-u path of length at
most |D′ | + 1 in △′q−1 − D′ and a u-τ path of length at most |D′′ | + 1 in △′′q−1 − D′′ . Hence, there
is a σ-τ path of length at most |D′ | + |D′′ | + 2 = |D| + 1 in △q − D.
By Lemma 4, the distance of the two special vertices σ and τ is upper-bounded by the number
of edge deletions, where the deleted edges do no form a σ-τ edge cut. Hence, if only few edges are
deleted in △q , then σ and τ are not far away from each other. The next lemma generalizes this
by stating that the distance of any vertex in △q to σ or to τ is quite small, even if a few edges are
deleted. Here “quite small” means that if O(q) edges are deleted, then the distance is still O(q)
which is logarithmic in the size of △q .
Lemma 5. Let D ⊆ E(△q ) be a subset of edges of △q and let x be an arbitrary vertex in V (△).

8

(A) If △q − D is connected, then dist△q −D (σ, x) ≤ q + |D| + 1 for all x ∈ V (△q ).
(B) If △q − D has exactly two connected components, with σ and τ being in different components,
then minz∈{σ,τ } {dist△q −D (z, x)} ≤ q + |D| − 1 for all x ∈ V (△q ).
Proof. We prove the two statements (A) and (B) simultaneously with an induction on depth q of
the T-fractal.
The base case is q = 0. For statement (A), observe that D = ∅. Thus, since τ has distance one
to σ, statement (A) follows. For statement (B), observe that D = {{σ, τ }}. Thus, statement (B)
holds.
As our induction hypothesis, we assume that (A) and (B) hold for 1, . . . , q − 1. We write
IH.(A) and IH.(B) for the induction hypothesis of (A) and (B), respectively. We introduce some
notation used for the induction step for both statements. Let △q , q > 0, the T-fractal with special
vertices σ and τ and let u be the (unique) vertex in △q that is adjacent to σ and τ , that is, u is on
the boundary B1 of △q . Denote with △′q−1 (△′′q−1 ) the left (right) subfractal of △q with special
vertices σ and u (u and τ ). Furthermore, let D′ (D′′ ) be the subset of edges of D deleted in △′q−1
(△′′q−1 ).
For the inductive step, we consider the two cases {σ, τ } 6∈ D and {σ, τ } ∈ D.
Case 1: {σ, τ } 6∈ D. Obviously, this case excludes (B), since σ and τ are in the same connected
component. Thus, we consider the induction step for (A). Let x be in the left subfractal △′q−1 .
If D′ does not form an edge cut in △′q−1 , then by IH.(A) it follows that dist△′q−1 −D′ (σ, x) ≤
q − 1 + |D′ | + 1 ≤ q + |D|. Thus, we consider the case where D′ forms an edge cut in △′q−1 .
Observe that such an edge cut fulﬁlls the requirements of statement (B) for △′q−1 . By IH.(B), it
follows that minz∈{σ,u} {dist△′q−1 −D′ (z, x)} ≤ q − 1 + |D′ | − 1 < q + |D|. If z = σ, then we are
done. Thus let z = u, where u is the vertex incident to both σ and τ in △q . We know that △q − D
is connected, and thus there exists an u-τ path in the right subfractal △′′q−1 − D′′ . By Lemma 4,
it follows that dist△′′q−1 −D′′ (u, τ ) ≤ |D′′ | + 1. Recall that {σ, τ } 6∈ D. In total, we get
dist△q −D (x, σ) ≤ dist△′q−1 −D′ (u, x) + dist△′′q−1 −D′′ (u, τ ) + 1
≤ q − 1 + |D′ | − 1 + |D′′ | + 1 + 1 = q + |D|.
In the cases, we obtain that dist△q −D (x, σ) ≤ q + |D| and hence, dist△q −D (x, τ ) ≤ q + |D| + 1. In
case that x is in the right subfractal △′′q−1 , it follows by symmetry that dist△q −D (x, τ ) ≤ q + |D|
and hence, dist△q −D (x, σ) ≤ q + |D| + 1.
Case 2: {σ, τ } ∈ D. First, we consider the step for statement (A). Let x be in the left
subfractal △′q−1 . Observe that D′ does not form an edge cut in △′q−1 , since otherwise the graph is
not connected. Thus, △′q−1 − D′ is connected, and by IH.(A) it follows that dist△′q−1 −D′ (σ, x) ≤
q − 1 + |D′ | + 1 < q + |D|.
Now, let x be in the right subfractal △′′q−1 . Again, D′′ does not form an edge cut in △′′q−1 . By
IH.(A), dist△′′q−1 −D′′ (u, x) ≤ q − 1 + |D′′ | + 1. Since u and σ are connected in △′q−1 − D′ , we can
apply Lemma 4 on u and σ. In total, with D = D′ ∪ D′′ ∪ {σ, τ } we get:
dist△q −D (x, σ) ≤ dist△′q−1 −D′ (u, σ) + dist△′′q−1 −D′′ (u, x)
≤ q − 1 + |D′ | + 1 + |D′′ | + 1 ≤ q + |D|.
Next, we consider the step for statement (B). Observe that the edge cut formed by edges in D
cannot form edge cuts in △′q−1 and in △′′q−1 at the same time since otherwise there are more than
two connected components. Let x be in the left subfractal and let edges in D′ do not form an
edge cut in △′q−1 − D′ . Then, by IH.(A), it follows that dist△′q−1 −D′ (σ, x) ≤ q − 1 + |D′ | + 1 ≤
q + |D| − 1. Thus, let the edges in D′ form an edge cut in △′q−1 − D′ . By IH.(B), either
dist△′q−1 −D′ (σ, x) ≤ q − 1 + |D′ | − 1 < q + |D| − 1, or dist△′q−1 −D′ (u, x) ≤ q − 1 + |D′ | − 1. For the
latter case, recall that the edges in D′′ do not form a cut in △′′q−1 , that is, △′′q−1 − D′′ is connected.

9

σ

τ

~ 3.
Figure 4: The directed T-fractal △
By Lemma 4, it follows that dist△′′q−1 −D′′ (u, τ ) ≤ |D′′ | + 1. In total, we get:
dist△q −D (x, τ ) ≤ dist△′q−1 −D′ (x, u) + dist△′′q−1 −D′′ (u, τ )
≤ q − 1 + |D′ | − 1 + |D′′ | + 1 < q + |D| − 1.
The case where x is in the right subfractal follows by symmetry.

3.2

Directed Variants of T-Fractals

By deﬁnition, a T-fractal is an undirected graph. We now discuss how to turn it into a directed
~ q.
graph, more precisely, into a directed acyclic graph. We denote the directed variant of △q by △
~
We obtain △q from △q as follows: Recall that each boundary forms a σ-τ path. For each boundary,
we direct the edges in the boundary from σ to τ . By this, the obtained boundary forms a directed
σ-τ path. Observe that σ has no incoming arcs, and the out-degree of σ equals q + 1. Further
~ q is acyclic,
observe that τ has no outgoing arcs, and the in-degree of τ equals q + 1. Moreover, △
see Figure 4 for an illustration.
~ q . Lemma 1 and Corollary 1
Except for Lemma 5, all results from Section 3.1 can be transferred to △
hold since we still have the same degree on σ an τ and the boundaries still form disjoint (directed)
σ-τ paths. Furthermore, we still have the equivalent recursive deﬁnition with the adjustment that
~ q as the
the edge between σ and τ becomes an arc from σ to τ . We deﬁne the dual structure of △
dual structure of the underlying undirected variant △q . By this, it is not hard to adapt Lemmas 2
and 3. For the latter result, and additionally for Lemma 4, we make use of the fact that in the
undirected case, we traverse the edges of the undirected △q in the same direction as they are
~ q.
directed in △
Regarding an equivalent of Lemma 5 for the directed variant, with small eﬀort one can modify
the proof of Lemma 5 to show the following.
~ q ) be a subset of arcs of △
~ q and let x be an arbitrary vertex in V (△
~ q ).
Lemma 6. Let D ⊆ E(△
~
~
If x ∈ V (△q ) is reachable from σ in △q − D, then dist△
~ q −D (σ, x) ≤ q + |D| + 1.
Proof. We prove the statement with an induction on depth q of the T-fractal.
The base case is q = 0. If x = σ, the statement immediately holds. If x = τ , observe that
D = ∅, since x is reachable from σ. Thus, since τ has distance one to σ, the statement follows.
As our induction hypothesis, we assume that the statement holds for 1, . . . , q − 1. We introduce
~ q , q > 0, be the directed T-fractal with special
some notation used for the induction step. Let △
~ q that is adjacent to σ and τ , that is, u is on
vertices σ and τ and let u be the (unique) vertex in △
′
′′
~
~
~
~ q with special
the boundary B1 of △q . Denote with △q−1 (△q−1 ) the left (right) subfractal of △
′
′′
~′
vertices σ and u (u and τ ). Furthermore, let D (D ) be the subset of arcs of D deleted in △
q−1
~ ′′ ).
(△
q−1
~ be an arbitrary vertex reachable from σ in △
~ q − D. For the inductive step, we
Let x ∈ V (△)
~
consider the two cases of the position of x in △q .

10

~ ′ . By induction hypothesis, it follows that
Case 1: x appears in △
q−1
dist△
~ q −D (σ, x) = dist△
~′

q−1 −D

′

(σ, x) ≤ q − 1 + |D′ | + 1 ≤ q + |D|.

~ ′′ . Since x is reachable from σ and τ has no outgoing arcs, it
Case 2: x appears in △
q−1
follows that u is reachable from σ as well. By the version of Lemma 4 for directed T-fractals, it
′
follows that dist△
~′
−D′ (σ, u) ≤ |D | + 1. Together with the induction hypothesis, it follows that
q−1

dist△
~ q −D (σ, x) ≤ dist△
~′

q−1 −D

′

(σ, u) + dist△
~′

q−1 −D

′

(u, τ )

≤ |D′ | + 1 + q − 1 + |D′′ | + 1 ≤ q + |D| + 1.

Observe that the case that x reaches τ is symmetric.

3.3

Application Manual for T-Fractals

The aim of this subsection is to provide two general guidelines on how to use T-fractals in crosscompositions. To this end, we introduce two general constructions–one for undirected graphs and
one for directed graphs. We start with the undirected case.
Construction 1. Given p = 2q instances I1 , . . . , Ip of an NP-hard graph problem, where each
instance Ii has a unique source vertex si and a unique sink vertex ti .
(i) Equip △cq with some “appropriate” edge cost c ∈ N.
(ii) Let v0 , . . . , vp be the vertices of the boundary Bq , labeled by their distances to σ in the σ-τ path
corresponding to Bq (observe that v0 = σ and vp = τ ).
(iii) Incorporate each of the p graphs of the input instances into △cq as follows: for each i ∈ [p],
merge si with vertex vi−1 in △cq and merge ti with vi in △cq .
Refer to Figure 5 for an illustrative example of Construction 1. In Construction 1, the T-fractal
works as an instance selector by deleting edges corresponding to a minimum edge cut, which, by
Lemma 1, is of size q+1. Hence, each minimum edge cut costs c·(q+1). The idea is that if we choose
an appropriate value for c (larger than the budget in the instances I1 , . . . , Ip ) and an appropriate
budget in the composed instance (e. g. c · (q + 1) plus the budget in the instances I1 , . . . , Ip ), then
we can only aﬀord to delete at most q + 1 edges in △cq . Furthermore, if the at most q + 1 edges
chosen to be deleted do not form a minimum σ-τ edge cut in △cq , then, by Lemma 4, the shortest
σ-τ path has length at most q + 2. Thus, by requiring in the composed instance that σ and τ
have distance more than q + 2, we enforce that any solution for the composed instance contains
a minimum σ-τ edge cut in △cq . By Lemma 2, each such minimum edge cut corresponds to one
root-leaf path in the dual structure Tq of △cq . Observe that each leaf in the dual structure of △cq
one-to-one corresponds to an attached source instance. Hence, with an appropriate choice of c, the
budget in the composed instance, and the required distance between σ and τ , the T-fractal ensures
that one instance is “selected”. We say that a minimum σ-τ edge cut in △cq selects an instance I
if the edge cut corresponds to the root-leaf path with the leaf corresponding to instance I.
Observation 3. Every minimum edge cut C in △cq selects exactly one instance I. Conversely,
every instance I can be selected by exactly one minimum edge cut.
Moreover, the graph obtained from Construction 1 has treewidth bounded in the maximum
input instance size.
Observation 4. Let nmax := |V (Gi )|, where Gi is the graph in instance Ii , i ∈ [p], from
Construction 1 and let G be the obtained graph. Then the treewidth of G is ω(G) ≤ 2 + nmax .

11

s1

t1 s 2

t2 s 3

t3 s 4

t4 s 5

t5 s 6

σ

τ

σ

τ

t6 s 7

t7 s 8

t8

Figure 5: Illustration of Construction 1 with p = 23 = 8. The vertices s1 , . . . , s8 indicate the
source vertices in the eight input instances, and t1 , . . . , t8 indicate the sink vertices in the eight
input instances. We use dashed lines to sketch the input graphs. Below the curved brace, the
resulting graph of the target instance is sketched.
Proof. By Observation 1, we know that the treewidth of T-fractal is at most two. Moreover,
we know that the treewidth of the modiﬁed T-fractal is at most two (cf. paragraph preceding
Section 3.1). Considering a tree decomposition of the modiﬁed T-fractal, we replace each bag
corresponding to an edge e of the outer boundary by the set containing all vertices of the instance
appended on e. Hence, we obtain a tree decomposition of G of width at most nmax + 2.
Proposition 1. Unless NP ⊆ coNP / poly, any parameterized problem P that admits an OR-crosscomposition for some NP-hard problem L by using Construction 1 does not admit a polynomial
kernel with respect to the parameter treewidth ω.
Using the same ideas as above and transferring them to the directed case yields the following
construction with analogous properties.
Construction 2. Given p = 2q instances I1 , . . . , Ip of an NP-hard problem on directed acyclic
graphs, where each instance Ii has a unique source vertex si and a unique sink vertex ti .
~ c with some “appropriate” edge cost c ∈ N, where σ is the vertex with no incoming
(i) Equip △
q
arc.
(ii) Let v0 , . . . , vp be the vertices of the boundary Bq , labeled by their distances to σ in the σ-τ path
corresponding to Bq (observe that v0 = σ and vp = τ ).
~ c as follows:
(iii) Incorporate each of the p directed acyclic graphs of the input instances into △
q
~ c and merge ti with vertex vi in △
~ c.
for each i ∈ [p], merge si with vertex vi−1 in △
q
q
In the rest of the paper, we use Constructions 1 and 2 in OR-cross-compositions to rule out the
existence of polynomial kernels. We baptize this approach fractalism. In particular, we provide
the source and the target problem, appropriate values for the edge cost c and the budget in the
composed instance, and the required distance between the special vertices σ and τ . Observe that
the directed graph obtained from Construction 2 is acyclic. Hence, by Construction 2 we can
apply OR-cross-compositions for problems on directed acyclic graphs. We remark that there is
a third construction where we drop the “acyclicity” requirement in Construction 2. This yields a
12

construction of a directed, possibly cyclic graph. In this sense, Construction 2 is a special case of
the third construction.

4

Applications to Length-Bounded Cut Problems

In this section, we rule out the existence of polynomial kernels for several problems (and their
variants) under the assumption that NP 6⊆ coNP / poly. To this end, we combine the framework
of OR-cross-compositions with our fractalism technique as described in Section 3.3.

4.1

Length-Bounded Edge-Cut

Our ﬁrst application of fractalism is the Length-Bounded Edge-Cut problem [2], also known
as the problem of ﬁnding bounded edge undirected cuts [27], or the Shortest Path Most Vital
Edges problem [4, 36].
Length-Bounded Edge-Cut (LBEC)
Input:
An undirected graph G = (V, E), with s, t ∈ V , and two integers k, ℓ.
Question: Is there a subset F ⊆ E of cardinality at most k such that distG−F (s, t) ≥ ℓ?
The problem is NP-complete [32] and ﬁxed-parameter tractable with respect to (k, ℓ) [27]. If
k is at least the size of any s-t edge cut, then the problem becomes polynomial-time solvable by
simply computing a minimum s-t edge cut. Thus, throughout this section, we assume that k is
smaller than the size of any minimum s-t edge cut. The generalized problem where each edge is
equipped with positive length remains NP-hard even on series-parallel and outerplanar graphs [2].
The directed variant with positive edge lengths remains NP-hard on planar graphs where the
source and the sink vertex are incident to the same face [41]. Recently, Dvořák and Knop [21]
showed that the problem can be solved in polynomial time on graphs of bounded treewidth. Here,
we answer an open question [27] concerning the existence of a polynomial kernel with respect to
the combined parameter (k, ℓ).1
Theorem 1. Unless NP ⊆ coNP / poly, Length-Bounded Edge-Cut parameterized by (k, ℓ, ω)
does not admit a polynomial kernel, where ω denotes the treewidth.
Proof. We OR-cross-compose p = 2q instances of LBEC into one instance of LBEC(k ′ , ℓ′ ). An
instance (Gi , si , ti , ki , ℓi ) of LBEC is called bad if max{ki , ℓi } > |E(Gi )| or min{ki , ℓi } < 0. We
deﬁne the polynomial equivalence relation R on the instances of LBEC as follows: two instances
(Gi , si , ti , ki , ℓi ) and (Gj , sj , tj , kj , ℓj ) of LBEC are R-equivalent if and only if kj = ki and ℓj = ℓi ,
or both are bad instances. Clearly, the relation R fulﬁlls condition (i) of an equivalence relation
(see Section 2). Observe that the number of equivalence classes of a ﬁnite set of instances is
upper-bounded by the maximal size of a graph over the instances, hence condition (ii) holds.
Thus, we consider p R-equivalent instances Ii := (Gi , si , ti , k, ℓ), i = 1, . . . , p. We remark that
we can assume that ℓ ≥ 3, since otherwise LBEC is solvable in polynomial time by counting
all edges connecting the source with the sink vertex. We OR-cross-compose into one instance
I := (G, s, t, k ′ , ℓ′ ) of LBEC(k ′ , ℓ′ ) with k ′ = k 2 · (log(p) + 1) + k and ℓ′ = ℓ + log(p) as follows.
Construction: Apply Construction 1 with edge cost c = k 2 . In addition, set s := σ and
t := τ . Let G denote the obtained graph. By Observation 4, the treewidth ω(G) of G is at most
2 + maxi∈[p] |V (Gi )|.
Correctness: We show that I is a yes-instance if and only if there exists an i ∈ [p] such that
Ii is a yes-instance.
“⇐”: Let i ∈ [p] be such that Ii is yes. Following Observation 3 in Section 3.3, let C be the
minimum s-t cut in △cq that selects instance Ii . Recall that C is of size q +1 and that the edge cost
equals k 2 . Thus, the minimum s-t cut C has cost (q + 1) · k 2 = (log(p) + 1) · k 2 .
1 The question also appeared in the list of open problems of the FPT School 2014, 17-22 August 2014, Będlewo,
Poland, http://fptschool.mimuw.edu.pl/opl.pdf.

13

Note that after deleting the edges in C, the vertices s and t are only connected via paths through
the incorporated graph Gi . Since Ii is yes, we can delete k edges (equal to the remaining budget)
such that the distance of si and ti in Gi is at least ℓ. Together with Lemma 3 in Section 3.1,
such an additional edge deletion increases the length of any shortest s-t path in G to at least
ℓ + log(p) = ℓ′ . Hence, I is a yes-instance.
“⇒”: Suppose that one can delete at most k ′ edges in G such that each s-t path is of length
at least ℓ′ . Since the budget allows log(p) + 1 edge-deletions in △cq , by Lemma 4 in Section 3.1, if
we do not cut s and t in △cq , then there is an s-t path of length log(p) + 2. Since ℓ ≥ 3, such an
edge deletion does not yield a solution. Thus, in every solution of I, a subset of the deleted edges
forms a minimum s-t edge cut in △cq and thus, by Observation 3, selects an input instance.
Consider an arbitrary solution to I, that is, an edge subset of E(G) of cardinality at most k ′
whose deletion increases the shortest s-t path to at least ℓ′ . Let Ii , i ∈ [p], be the selected instance.
Note that any shortest s-t path contains edges in the selected instance Ii . By Lemma 3, we know
that the length of the shortest s-si path and the length of the shortest ti -t path sum up to exactly
log(p). It follows that the remaining budget of k edge deletions is spent in Gi in such a way that
there is no path from si to ti of length smaller than ℓ in Gi . Hence, Ii is a yes-instance.
Golovach and Thilikos [27] showed that LBEC on directed acyclic graphs is NP-complete.
Using Construction 2 instead of Construction 1 with LBEC on directed acyclic graphs as source
and target problem, the same argument as in the proof of Theorem 1 yields the following.
Theorem 2. Unless NP ⊆ coNP / poly, Length-Bounded Edge-Cut on directed acyclic graphs
parameterized by (k, ℓ) does not admit a polynomial kernel.
In the following, we consider LBEC on planar graphs. To the best of our knowledge, it was
not shown before whether LBEC remains NP-hard on planar graphs. This is what we state next.
Theorem 3. Length-Bounded Edge-Cut is NP-hard even on planar undirected graphs as well
as on planar directed acyclic graphs, where for both problems s and t are incident to the outer face.
To prove the theorem, we need the following deﬁnitions of plane embeddings of graphs.
Definition 3. A page embedding of a graph G is a plane embedding of G where all vertices lie
on the real line and every edge lies in the upper half R × R+ .
Definition 4. A graph G = (V, E) is k-page book embeddable if there is a partition E1 , . . . , Ek
of the edge set E such that Gi := (V, Ei ) is page embeddable for all i ∈ [k].
Intuitively, a book embedding of a graph is a drawing of graph where all vertices are drawn
along the spine of the book, and the edges are draw crossing-free on each page of the book.
Proof of Theorem 3. Our proof follows the same strategy as the proof due to Schieber et al. [42] for
LBEC on general graphs, where Schieber et al. [42] reduce Vertex Cover to LBEC. We reduce
from 3-Planar Vertex Cover, that is, Vertex Cover on planar graphs with maximum degree
three, which remains NP-complete [39]. Heath [31] proved that any planar graph of maximum
vertex degree three allows a two-page embedding (cf. Deﬁnition 4). Moreover, Heath [31] showed
that such an embedding can be computed in linear time in the number of vertices of the input
graph. Recently, Bekos et al. [5] proved that any planar graph of maximum degree four allows
a two-page embedding. We mainly copy the proof due to Schieber et al. [42] and, on the way,
perform small changes on the gadgets and target parameters. We describe this in the following.
Let I = (G, k) be an instance of 3-Planar Vertex Cover. Since we can assume to have
a two-page embedding, the vertices are drawn along the real line and connected by non-crossing
edges lying in the lower and upper half. Further, we assume that the vertices are labeled from 1
to n, in the order along the real line. We replace each vertex i by a gadget i as follows. The
gadget i consists of two P2k s, where P2k denotes a simple path with 2k vertices, and one P2k+1 ,
all three merged together at their endpoints. We denote the left and right (merged) endpoint of
gadget i by si and ti , respectively. One P2k belongs to the upper half, the other to the lower half.
14

...

si

k−

1

xu
i

yiu

k−

1

2k

k−

...
ti

1

xℓi

yiℓ

k−

sj

k−

xu
j

yju

k−

1

2k

k−

1

1

...
tj

1

xℓj

yjℓ

k−

1

(2k − 1) · (j − i) − 2
Figure 6: Illustration of the gadgets in the proof of Theorem 3. Here, exempliﬁed for two vertices
i, j ∈ V with {i, j} ∈ E, and the edge is embedded on the second (lower) page in the two-page
embedding of the input graph G = (V, E).
The P2k+1 lies along the real line. The two middle vertices of each of the two P2k we denote by
xui , xℓi , yiu , yiℓ , where x is left of y, and u and ℓ stand for “upper” and “lower”. We merge ti with
si+1 for all i ∈ [n − 1]. We set s := s1 and t := tn . Moreover, if two vertices i < j are connected
by an edge lying in the upper half, then we connect the vertex yiu with xuj via a path of length
(2k − 1)(j − i) − 2 (analogously for edges in the lower half). Refer to Figure 6 for an illustration of
the construction. We denote by G′ the obtained graph. Observe that G′ remains planar. Except
for the edges {xui , yiu }, {xℓi , yiℓ }, i ∈ [n], there are no edges that are allowed to be deleted (see
Schieber et al. [42]).
We set k ′ := 2k and ℓ′ = k · (2k) + (n − k) · (2k − 1). Let I ′ := (G′ , s, t, k ′ , ℓ′ ) be the resulting
instance of Planar-LBEC(k ′ , ℓ′ ), that is LBEC(k ′ , ℓ′ ) on planar graphs. We show that I is a
yes-instance if and only if I ′ is a yes-instance.
“⇒”: Suppose that G admits a vertex cover of size at most k. Let C ⊆ V (G) be such a vertex
cover of size k. We claim that deleting the edges in the edge set X := {{xui , yiu }, {xℓi , yiℓ } | i ∈ C}
forms a solution to I ′ .
We observe that any s-t path in G′ − X using only edges in the gadgets is of length at
least ℓ′ . To see this, consider a gadget i with i ∈ C. Then the edges {xui , yiu }, {xℓi , yiℓ } ∈ X,
and hence the only si -ti path using only edges in the gadget i is of length 2k (that is the P2k+1
used in the construction). If no edge in a gadget j is deleted, then any shortest sj -tj path
using only edges in the gadget j is of length 2k − 1 (those correspond to the P2k s used in the
construction). Since |C| = k, any s-t path in G′ − X using only edges in the gadgets is of length
at least k · (2k) + (n − k) · (2k − 1) = ℓ′ .
We have to show that there is no shorter s-t path in G′ − X than any path using only edges
in the gadgets. To this end, let i, j ∈ V (G), i < j, be two adjacent vertices in G, that is, with
{i, j} ∈ E(G). Since C is a vertex cover, it follows that either i ∈ C or j ∈ C. Let i ∈ C and j 6∈ C
(the case with j ∈ C and i 6∈ C is symmetric). We consider the shortest path from si to tj not
going backwards, that is, not appearing in any gadget z with z < i or z > j, and using the path
connecting the gadgets of i and j. Let the path connecting the gadgets of i and j be a lower path,
that is, the vertices yiℓ and xℓj are connected by the path. Since the edges {xℓi , yiℓ } and {xui , yiu } are
deleted, the shortest path from si to yiℓ is of length 2k + (k − 1). Then we take the path of length
(2k − 1)(j − i) − 2 to get to the gadget of j. Finally, we take the path from xℓj via edge {xℓj , yjℓ }
to ti of length (k − 1) + 1 = k. In total, the path is of length 4k + (2k − 1)(j − i) − 3, and it is the
shortest of its kind.
We compare this to the shortest path from si to tj using only edges in the gadgets. The length
of such a path is at most 2k(k) + (2k − 1)(j − i − k) + (2k − 1) = 2k(j − i) − (j − i − k) + (2k − 1)
if j − i ≥ k, and at most 2k(j − i) + (2k − 1) otherwise. Comparing the two lengths, we obtain

15

for j − i ≥ k
4k + (2k − 1)(j − i) − 3 − (2k(j − i) − (j − i − k) + (2k − 1)) = k − 2,
and for j − i < k
4k + (2k − 1)(j − i) − 3 − (2k(j − i) + (2k − 1)) = 2k − (j − i) − 2 > k − 2.
It follows that there is a path using only edges in the gadgets that is shorter than the shortest
paths using at least one edge not appearing in the gadgets. Finally note that if both i, j ∈ C, then
the diﬀerence of the path lengths is even bigger. Observe that using a path connecting gadget i
with j + 1 (or i − 1 with j) to get from si to tj is longer by at least k − 1 (or at least k − 3),
following from an analogous argumentation as above. Hence, the shortest path connecting s with
t passes through the gadgets and is of length at least ℓ′ .
“⇐”: Suppose that G′ allows k ′ = 2k edge deletions such that any shortest s-t path is of length
at least ℓ′ . Our ﬁrst observation is that in any solution to I, either none or exactly two edges are
deleted in any gadget. Suppose that there is an gadget with only one edge deleted. Then a shortest
path through this gadget is of length 2k − 1. Since 2k is the maximum increase of the passing
length through a gadget, we get (2k)(k − 2) + (2k − 1)(n − k + 2) < (2k) · k + (2k − 1)(n − k) = ℓ′ .
Hence, in any gadget, either exactly two or no edge is deleted. Let C ⊆ V (G) be the set of vertices
such that both edges are deleted in the corresponding gadgets. We claim that C is a vertex cover
of size k in G.
Suppose that there are two gadgets i and j not containing any deleted edge, that is, {i, j}∩C =
∅, but {i, j} ∈ E(G). Then the shortest si -tj path using the path corresponding to edge {i, j} ∈
E(G) is of length 2k + (2k − 1)(i − j) − 2. The shortest si -tj path through the gadgets only is of
length at least 2k − 1 + (2k − 1)(i − j). Thus, the path using the path connecting the gadgets i
and j is too short by exactly one, and hence, the shortest s-t path is of length smaller than ℓ′ .
This contradicts the fact that {{xui , yiu }, {xℓi , yiℓ } | i ∈ C} forms a solution to I ′ . It follows that for
each edge {i, j} ∈ E(G) we have |C ∩ {i, j}| > 0. This is exactly the property of a vertex cover,
and thus, C is a vertex cover in G of size k.
We have shown that the problem is NP-hard on planar, undirected graphs. Observe that we
can direct all edges from “left to right”. The planarity still holds, and we obtain a directed acyclic
graph. Since we have shown in the proof that “going backwards” is never optimal, the proof can
be easily adapted. Thus, the problem remains NP-hard on planar directed acyclic graphs.
Due to Theorem 3, we can use LBEC on planar undirected graphs as well as on planar directed
acyclic graphs, where in both cases the source and sink vertices are incident to the outer face, as
source problem for OR-cross-compositions. The property that the source and the sink vertices
are allowed to be incident with the same face in the input graph allows us to use Constructions 1
and 2 with a target problem on planar graphs. Hence, together with the same argumentation as
in the proof of Theorem 1, we obtain the following.
Theorem 4. Unless NP ⊆ coNP / poly, Length-Bounded Edge-Cut on planar undirected
graphs parameterized by (k, ℓ, ω) as well as on planar directed acyclic graphs parameterized by
(k, ℓ) do not admit a polynomial kernel, where ω denotes the treewidth.

4.2

Minimum Diameter Edge Deletion

Our second fractalism application concerns a problem introduced by Schoone et al. [43].
Minimum Diameter Edge Deletion (MDED)
Input:
A connected, undirected graph G = (V, E), two integers k, ℓ.
Question: Is there a subset F ⊆ E of cardinality at most k such that G − F is connected
and diam(G − F ) ≥ ℓ?
The problem was shown to be NP-complete, also on directed graphs [43]. A simple search tree
algorithm yields ﬁxed-parameter tractability with respect to (k, ℓ):
16

σ

τ
L

σ′

τ′

Figure 7: Cross-composition for Minimum Diameter Edge Deletion(k, ℓ) with p = 8 = 23 ,
and L = 9 · nmax + 1. Dashed lines sketch the boundaries of the graphs in the p input instances.
Theorem 5. Minimum Diameter Edge Deletion can be solved in O((ℓ − 1)k n2 (n + m)) time.
Proof. We give a search tree algorithm branching over the possible edge deletions to prove that
MDED(k, ℓ) is ﬁxed-parameter tractable. The underlying crucial observation is that if some
instance (G, k, ℓ) of MDED(k, ℓ) is a yes-instance, then there exists at least one pair of vertices v, w ∈ V in the graph G − X such that distG−X (v, w) ≥ ℓ, where X is a solution to (G, k, ℓ).
Hence, we want to check whether we can increase by at most k edge deletions the length of any
shortest path between the chosen pair up to at least ℓ, where we delete an edge only if its deletion
leaves the graph connected.
To this end, for each pair, we apply the branching algorithm provided by Golovach and Thilikos [27]: Find a shortest path and if its length is at most ℓ − 1, then branch in all cases of deleting
an edge on this path and decrease k by one. In each branch, we need to check whether the graph
is still connected. This can be done in O(n + m) time with a simple depth/breadth ﬁrst search.
Hence, in total we obtain a branching algorithm running in O(n2 · (ℓ − 1)k (n + m)) time. Thus,
MDED(k, ℓ) is ﬁxed-parameter tractable.
Complementing the ﬁxed-parameter tractability of MDED(k, ℓ), we show the following.
Theorem 6. Unless NP ⊆ coNP / poly, Minimum Diameter Edge Deletion parameterized
by (k, ℓ, ω) does not admit a polynomial kernel, where ω denotes the treewidth.
Proof. We OR-cross-compose p = 2q instances of Length-Bounded Edge-Cut (LBEC) on
connected graphs into one instance of MDED(k, ℓ) as follows. Apply Construction 1 with p = 2q
instances Ii := (Gi , si , ti , k, ℓ), i = 1, . . . , p, of the input problem LBEC on connected graphs,
target problem MDED(k, ℓ), and edge cost c = k 2 . The equivalence relation on the input instances
is deﬁned as in the proof of Theorem 1. Let nmax := maxi∈[p] |V (Gi )|. In addition, attach to σ as
well as on τ a path of length L := nmax · (2 log(p) + 3) + 1 each. Denote the endpoint of the path
attached to σ by σ ′ (where σ ′ 6= σ), and let τ ′ be deﬁned analogously. Let G denote the obtained
graph. Note that the appended paths to the T-fractal do not increase the treewidth ω(G) of G,
and hence by Observation 4, it holds that ω(G) ≤ 2 + nmax .
Refer to Figure 7 for an exempliﬁed illustration of the described construction. Let I :=
(G, k ′ , ℓ′ ) be the target instance of MDED(k ′ , ℓ′ ) with k ′ = k 2 · (log(p) + 1) + k and ℓ′ =
2 · L + log(p) + ℓ.
Correctness: We show that I is a yes-instance for MDED(k ′ , ℓ′ ) if and only if there exists
an i ∈ [p] such that Ii is a yes-instance for LBEC on connected graphs.
“⇐”: Let Ii , i ∈ [p], be a yes-instance for LBEC on connected graphs. Following Observation 3,
we delete all edges in the minimum cut in △cq that selects instance Ii . Then, we delete edges corresponding to a solution for Ii without disconnecting the graph G (observe that we can always
ﬁnd such a solution). Let X ⊆ E(G) be the set of deleted edges. The distance of σ and τ in G − X
17

is at least log(p) + ℓ, and thus, the distance of σ ′ and τ ′ is at least 2 · L + log(p) + ℓ = ℓ′ . Hence,
the diameter is at least ℓ′ after k ′ edge deletions that leave the graph connected. It follows that
I is a yes-instance.
“⇒”: Conversely, suppose that I allows k ′ edge deletions such that the remaining graph is
connected and has diameter at least ℓ′ . Let X ⊆ E(G) be a solution. First observe that G − X is
connected. Consider the instances appended to the T-fractal as the artiﬁcial q + 1st boundary of a
(q+1)-T-fractal, where an edge in this boundary has length nmax . Thus, we can apply Lemma 5(A)
to this artiﬁcial (q + 1)-T-fractal. Recall that our budget only allows log(p) + 1 edge deletions
(of cost k 2 ) in △cq . Hence we get that the distance to σ (and by symmetry to τ ) of every vertex
contained either in △cq or in any appended instance is at most nmax ·(log(p)+log(p)+3) = L−1. It
follows that distG−X (x, σ) ≤ distG−X (σ, σ ′ ) and distG−X (x, τ ) ≤ distG−X (τ, τ ′ ) for all x ∈ V (G).
Moreover, for all x, y ∈ V (G) we have:
distG−X (x, y) ≤ distG−X (x, σ) + distG−X (σ, τ ) + distG−X (τ, y)
≤ distG−X (σ ′ , σ) + distG−X (σ, τ ) + distG−X (τ, τ ′ )
= distG−X (σ ′ , τ ′ ).
Hence, σ ′ , τ ′ is the pair of vertices with the largest distance in G−X and, thus, distG−X (σ ′ , τ ′ ) ≥
ℓ . Observe that distG−X (σ ′ , τ ′ ) ≥ ℓ′ if and only if distG−X (σ, τ ) ≥ log(p) + ℓ since every shortest σ ′ -τ ′ path contains both σ and τ . Following the argumentation in the correctness proof
of Theorem 1, it follows that there is an instance Ii , i ∈ [p], that is a yes-instance for LBEC on
connected graphs.
′

In their NP-hardness-proof for MDED, Schoone et al. [43] reduce from Hamiltonian Path
(HP) to MDED. The reduction does not modify the graph, that is, the input graph for HP remains
the same for the MDED instance. Since HP remains NP-hard on planar graphs [26], the reduction
of Schoone et al. implies that MDED is NP-hard even on planar graphs. Due to Theorem 3, using
Construction 1 with LBEC on planar graphs as source problem, and MDED(k, ℓ) on planar
graphs as target problem, we obtain the following.
Theorem 7. Unless NP ⊆ coNP / poly, Minimum Diameter Edge Deletion on planar graphs
parameterized by (k, ℓ, ω) does not admit a polynomial kernel, where ω denotes the treewidth.
The diameter of a directed graph is deﬁned as the maximum length of a shortest directed
path over any two vertices in any order. The diameter of a directed graph that is not stronglyconnected equals inﬁnity. Thus, Minimum Diameter Edge Deletion on directed graphs is
deﬁned as follows: given a strongly-connected directed graph G = (V, E), and two integers k and
ℓ, the question is whether there is a subset F ⊆ E of cardinality at most k such that G − F
is strongly-connected and diam(G − F ) ≥ ℓ? Observe that Minimum Diameter Edge Deletion on directed planar graphs parameterized by (k, ℓ) is FPT, as a consequence of the proof
of Theorem 5.
Theorem 8. Unless NP ⊆ coNP / poly, Minimum Diameter Edge Deletion on directed
planar graphs parameterized by (k, ℓ) does not admit a polynomial kernel.
Proof (Sketch). The following proof adapts the ideas of the proof of Theorem 6. Thus, we highlight
the diﬀerences to the proof instead of providing a full proof here.
We OR-cross-compose p = 2q instances of the Length-Bounded Edge-Cut (LBEC) problem on planar, directed acyclic graphs into one instance of MDED(k, ℓ) on directed planar graphs.
We assume without loss of generality that in each graph of the input instances, the source reaches
every vertex, and every vertex reaches the sink.
We apply Construction 2 with the following additions. Let nmax and k ′ be deﬁned as in
the proof of Theorem 6, that is, nmax := maxi∈[p] |V (Gi )| and k ′ := k 2 · (log(p) + 1) + k. Let
L := ℓ · nmax · (2 log(p) + 3) + 1 and ℓ′ = 2 · L + log(p) + ℓ. Attach to σ as well as to τ a path
of length L each. Denote the endpoint of the path attached to σ by σ ′ (where σ ′ 6= σ), and
let τ ′ be deﬁned analogously. Direct all edges in the paths towards from σ ′ to σ and from τ to
18

τ ′ respectively. Moreover, add to the graph the arc (τ ′ , σ ′ ), and the arc (τ, σ), the latter with
cost k ′ + 1.
Next, we adjust the instances we compose in order to ensure that we can delete all the arcs
we want without destroying the property that the source reaches every vertex and every vertex
reaches the sink. Let Gi be the graph in instance Ii for each i ∈ [p]. For each arc (v, w) ∈ E(Gi ),
connect v and w by an additional path of length ℓ directed towards w. Apply this for each Gi ,
i ∈ [p], and let G′i the graph obtained from graph Gi . Note that the directed graph G′i remains
planar and acyclic. Observe that none of the introduced arcs will be in a minimal solution for
the LBEC instance since they only occur in paths of length ℓ. Hence, Ii is a yes-instance of
LBEC on planar, directed acyclic graphs if and only if (G′i , si , ti , k, ℓ) is a yes-instance of LBEC
on planar, directed acyclic graphs. Furthermore, in the composed Minimum Diameter Edge
Deletion-instance, none of the introduced arcs will be deleted as this would introduce a vertex
without in-going or without out-going arcs and this is not allowed in the problem setting.
Let G denote the obtained graph. Observe that G is planar, directed and strongly-connected.
Suppose (G, k ′ , ℓ′ ) is a yes-instance of Minimum Diameter Edge Deletion. Consider
a solution X ⊆ E(G) for the instance (G, k ′ , ℓ′ ) of Minimum Diameter Edge Deletion on
directed planar graphs. The crucial observation is that for any two vertices x, y not contained in
the attached paths with endpoints σ ′ on the one, and τ ′ on the other hand, the following holds:
max{distG−X (x, y), distG−X (y, x)} ≤ distG−X (σ ′ , τ ′ ). To see this, note that the arc (τ, σ) has
cost k ′ + 1 and thus (τ, σ) 6∈ X. Since G is strongly-connected, both x and y are reachable and
reach σ and τ . Moreover, σ is reachable from τ via the arc (τ, σ). Without loss of generality, let
distG−X (x, y) = max{distG−X (x, y), distG−X (y, x)}. It holds that
distG−X (x, y) ≤ distG−X (x, τ ) + distG−X (τ, σ) + distG−X (σ, y)
≤ ℓ · nmax · (2 log(p) + 2) + 1 + ℓ · nmax · (2 log(p) + 2)
= 2 · ℓ · nmax · (2 log(p) + 2) + 1 < ℓ′ .
~ q . The second inequality follows from Lemma 6
Herein, recall that we allow log(p)+1 arc deletions in △
and the fact that in each graph Gi − X the vertex si has distance at most ℓ · nmax to ti .
As a consequence, the vertices at distance ℓ′ appear in the paths appended on σ and τ . Among
them, note that distG−X (σ ′ , τ ′ ) is maximal. Following the discussion in the proof of Theorem 6,
~ q , and
the budget has to be spend in such a way that the arc-deletions form an σ-τ arc-cut in △
the remaining budget must be spend in such a way that the instance Ii chosen by the cut allows
no si -ti path of length smaller than ℓ. Hence, the Ii is a yes-instance.
Conversely, let Ii be a yes-instance of LBEC on planar, directed acyclic graphs and let X ′ ⊆
E(Gi ) a minimum size solution. We added to each arc of Gi a directed path of length ℓ and, as
discussed above, none of the arcs in these paths is in X ′ . Hence, in Gi − X ′ every vertex is still
reachable from si and reaches ti . Deleting in G the arcs in X ′ and the arcs corresponding to the
cut choosing Ii preserves the strongly-connectivity of G. Let X ⊆ E(G) be the set of deleted arcs.
Following the discussion in the proof of Theorem 6, distG−X (σ ′ , τ ′ ) ≥ ℓ′ . It follows that I is a
yes-instance of Minimum Diameter Edge Deletion on directed planar graphs.

4.3

Directed Small Cycle Transversal

Our third fractalism application concerns the following problem.
Directed Small Cycle Transversal (DSCT)
Input:
A directed graph G = (V, E), two integers k, ℓ.
Question: Is there a subset F ⊆ E of cardinality at most k such that there is no induced
directed cycle of length at most ℓ in G − F ?
The problem is NP-hard [30], also on undirected graphs [49]. The NP-completeness of DSCT
follows by a simple reduction from k-Feedback Arc Set with an n-vertex graph, where we
set ℓ = n and leave the graph unchanged in the reduction. We remark that the problem is also
19

σ

τ

Figure 8: Cross-composition for DSCT(k, ℓ) with p = 8 = 23 . Dashed lines sketch the boundaries
of the graphs in the p input instances.
known as Cycle Transversal [9], or ℓ-(Directed)-Cycle Transversal [30]. The undirected
variant is also known as Small Cycle Transversal [47, 48].
As for the Minimum Diameter Edge Deletion problem, there is a simple search tree
algorithm showing ﬁxed-parameter tractability with respect to (k, ℓ).
Theorem 9. Directed Small Cycle Transversal can be solved in O(ℓk · n · (n + m)) time.
Proof. We give a search tree algorithm branching over all possible edge deletions to prove that
DSCT(k, ℓ) is ﬁxed-parameter tractable. Let (G, k, ℓ) be an instance of DSCT(k, ℓ). To detect
short cycles in G containing a vertex v ∈ V (G), we construct a helping graph Gv as follows.
Delete v (and all edges incident to v), and add vin and vout , and the arcs {(x, vin ) | (x, v) ∈ E(G)},
{(vout , x) | (v, x) ∈ E(G)} as well as the arc (vin , vout ). Now to detect the shortest cycle in G
containing v, compute a shortest vout -vin path in Gv . If a cycle is too short, then we branch into
all possible, at most ℓ diﬀerent deletions of an arc of the cycle (beside arc (vin , vout )).
The depth of the search tree is at most k, and thus we obtain an O(ℓk · n · (n + m))-time
algorithm since constructing for each v ∈ V the helping graph Gv and then ﬁnding a shortest path
in unweighted graphs can be done in O(n · (n + m)) time.
Theorem 10. Unless NP ⊆ coNP / poly, Directed Small Cycle Transversal parameterized
by (k, ℓ) does not admit a polynomial kernel.
Proof. We OR-cross-compose p = 2q R-equivalent instances of LBEC on directed acyclic graphs
into one instance of DSCT(k, ℓ) as follows, where R is deﬁned as in the proof of Theorem 1.
Recall that Length-Bounded Edge-Cut (LBEC) on directed acyclic graphs is NP-complete.
Construction: We apply Construction 2 with edge cost k 2 . In addition, we add the edge (τ, σ)
with edge cost k ′ + 1, where k ′ = k 2 · (log(p) + 1) + k. We denote by G the obtained graph. We
refer to Figure 8 for an exempliﬁed illustration of the construction. Observe that G is not acyclic,
and the edge (τ, σ) participates in every cycle in G, that is, G without edge (τ, σ) is acyclic. Let
(G, k ′ , ℓ′ ) be the target instance of DSCT(k, ℓ) with ℓ′ = ℓ + log(p) + 1.
Correctness: Note that every cycle in G uses the edge (τ, σ). Since its edge cost equals k ′ + 1,
the budget does not allow its deletion. Thus, the crucial observation is that the length of any
shortest path from σ to τ must be increased to at least ℓ + log(p) = ℓ′ − 1. Hence, the correctness
proof follows from the proof of Theorem 2.
Due to Theorem 3, using LBEC on planar directed acyclic graphs as source problem in the
proof of Theorem 10, we obtain the following.
Theorem 11. Unless NP ⊆ coNP / poly, Directed Small Cycle Transversal on planar
directed graphs parameterized by (k, ℓ) does not admit a polynomial kernel.
Remarkably, DSCT(k, ℓ) on planar undirected graphs admits a polynomial kernel [47].

20

Figure 9: The vertex deletion variant △2;5
2 of T-fractals. Vertex types: empty diamonds
to the boundary B0 , empty triangles belong to the boundary B1 , empty circles belong
boundary B2 . The squares and dashed lines indicate the dual structure, where the ﬁlled
corresponds to the root. We highlighted vertices in gray-ﬁlled circles that correspond
vertices in the edge-deletion variant △2 .

5

belong
to the
square
to the

Conclusion

We start with brieﬂy sketching how our technique can be adapted such that it also applies to
the vertex deletion (instead of edge deletion) versions of the considered problems. Afterwards, we
discuss future challenges and open problems.
Vertex-Deletion Variants. We give another modiﬁcation of the T-fractal such that vertexdeletion variants can be tackled. We obtain the vertex-deletion variant △c;d
of the T-fractal
q
from △cq as follows, where d denotes an additional vertex cost. Recall that △cq can be reduced
ˆ c . We ﬁrst obtain △
ˆ c = (V ′ ∪ V ′′ , E ′ ) from △c , where V ′
to an unweighted, simple graph △
q
q
q
ˆ c . Next, we
denote the vertices not being the product of a subdivision in the step from △cq to △
q
ˆ c . To this end, we introduce the following notation: given
describe how to obtain △qc;d from △
q
a graph G = (V, E) and v ∈ V , we say we clone vertex v if we add a new vertex v ′ to V and
′
ˆc
the edge set {{v ′ , w} | {v, w} ∈ E} to E. We obtain △c;d
q from △q by cloning every vertex in V
c;d
d − 1 times (we refer to them as the clones in the following). We denote by Cx ⊆ V (△q ) the
ˆ c ). We refer to Figure 9 for an illustration of the vertex-deletion variant
clones of vertex x ∈ V (△
q
of T-fractal △2 with edge cost 2 and vertex cost 5.
The vertex cost can be interpreted as a tool to avoid deletion of clones. Herein, we can set
the vertex cost larger than the budget for vertex-deletions in a given problem instance to avoid
any deletion of clones. To this end, note that to essentially change the structure of the graph by
deleting a vertex having clones, it is required the delete all clones of the vertex as well.
We remark that the vertex-deletion variant of the T-fractal can be directed in the same way
as the edge-deletion variant of the T-fractal such that the obtained graph is acyclic. Moreover,
we can transfer the notion of boundaries, now being a set of vertices instead, as well as the dual
structure for the vertex-deletion variant of T-fractal (cf. Figure 9). Note that in general △c;d
is
q
not planar, for example for c, d ≥ 3.
One can show that all properties of the edge-deletion variant also hold on the vertex-deletion
variant, replacing edge cuts by vertex cuts (modulo some constants), while forbidding to delete
clones. Again, the latter is reasonable since in any application we can set the vertex cost larger
than the budget for vertex-deletions. For example, considering any minimum Cσ -Cτ vertex cut
in △c;d
q , where every vertex in every Cx , x ∈ V (△q ), is not allowed to be deleted. One can show
that it is of size (q + 1) · c, using a simple bijection of the edges in △cq and the corresponding
vertices in △c;d
q .
In addition, one can modify Constructions 1 and 2 slightly to use the vertex-deletion variants

21

for vertex-deletion problems. Herein, it is worth to mention how the merging of the source and
sink vertices of the input instances works. Consider si and vi−1 as deﬁned in Construction 1, and
let d ∈ N be the vertex cost. Note that vi−1 is replaced by C := Cvi−1 with |C| = d. We remove
si and all incident edges of si , and add d copies s1i , . . . , sdi of si . In addition, if {si , x} was an edge
we deleted in the previous step, we add the edges {sji , x} for all j ∈ [d]. Finally, we merge each
sji with one vertex in C in such a way that each vertex in C is merged exactly once. We apply an
analogue procedure to the sink vertex ti and Cvi .
We remark that recently, Zschoche [50] used the fractalism technique to exclude the existence
of polynomial kernels for the problem of ﬁnding s-t separators in temporal graphs under NP 6⊆
coNP / poly. Moreover, a gadget relying on grids that could ensure planarity for the vertex-deletion
variant of the T-fractal is proposed.
Outlook. We provided several case studies where our fractalism technique applies. It remains
open to further explore the limitations and possibilities of our technique in more contexts. Note
that the fractal structure also applies for refuting the existence of polynomial kernels for problems
not dealing with cuts [28]. Table 1 in Section 1 presents an open question which should be clariﬁed.
Moreover, we could not settle the cases for vertex deletion problems when the underlying graphs
are planar.

Acknowledgement
We thank Manuel Sorge (TU Berlin) for his help with the proof of Theorem 3.

References
[1] Giorgio Ausiello, Pierluigi Crescenzi, Giorgio Gambosi, Viggo Kann, Alberto MarchettiSpaccamela, and Marco Protasi. Complexity and Approximation: Combinatorial Optimization
Problems and Their Approximability Properties. Springer, 1999. 2
[2] Georg Baier, Thomas Erlebach, Alexander Hall, Ekkehard Köhler, Petr Kolman, Ondrej
Pangrác, Heiko Schilling, and Martin Skutella. Length-bounded cuts and ﬂows. ACM Transactions on Algorithms, 7(1):4, 2010. 13
[3] Cristina Bazgan, Morgan Chopin, Marek Cygan, Michael R. Fellows, Fedor V. Fomin, and
Erik Jan van Leeuwen. Parameterized complexity of ﬁreﬁghting. Journal of Computer and
System Sciences, 80(7):1285–1297, 2014. 3
[4] Cristina Bazgan, André Nichterlein, and Rolf Niedermeier. A reﬁned complexity analysis of
ﬁnding the most vital edges for undirected shortest paths. In Proc. of the 9th International
Conference on Algorithms and Complexity (CIAC 2015), volume 9079 of LNCS, pages 47–60.
Springer, 2015. 2, 13
[5] Michael A. Bekos, Martin Gronemann, and Chrysanthi N. Raftopoulou. Two-page book
embeddings of 4-planar graphs. In Proc. of the 31st International Symposium on Theoretical
Aspects of Computer Science (STACS 2014), volume 25 of LIPIcs, pages 137–148. Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2014. 14
[6] René van Bevern, Robert Bredereck, Morgan Chopin, Sepp Hartung, Falk Hüﬀner, André
Nichterlein, and Ondřej Suchý. Fixed-parameter algorithms for DAG partitioning. Discrete
Applied Mathematics, 220:134–160, 2017. 3
[7] Hans L. Bodlaender. A partial k-arboretum of graphs with bounded treewidth. Theoretical
Computer Science, 209(1-2):1–45, 1998. 6
[8] Hans L. Bodlaender, Rodney G. Downey, Michael R. Fellows, and Danny Hermelin. On
problems without polynomial kernels. Journal of Computer and System Sciences, 75(8):423–
434, 2009. 2
[9] Hans L. Bodlaender, Fedor V. Fomin, Daniel Lokshtanov, Eelko Penninkx, Saket Saurabh,

22

[10]
[11]
[12]
[13]
[14]
[15]
[16]
[17]
[18]
[19]
[20]
[21]
[22]

[23]
[24]

[25]
[26]
[27]
[28]
[29]
[30]

and Dimitrios M. Thilikos. (Meta) Kernelization. Journal of the ACM, 63(5):44:1–44:69,
2016. 20
Hans L. Bodlaender, Bart M. P. Jansen, and Stefan Kratsch. Kernelization lower bounds by
cross-composition. SIAM Journal on Discrete Mathematics, 28(1):277–305, 2014. 2, 4, 5
Hans L. Bodlaender, Stéphan Thomassé, and Anders Yeo. Kernel bounds for disjoint cycles
and disjoint paths. Theoretical Computer Science, 412(35):4570–4578, 2011. 2
Liming Cai, Jianer Chen, Rodney G. Downey, and Michael R. Fellows. Advice classes of
parameterized tractability. Annals of Pure and Applied Logic, 84(1):119–138, 1997. 4
Jianer Chen, Henning Fernau, Iyad A. Kanj, and Ge Xia. Parametric duality and kernelization: Lower bounds and upper bounds on kernel size. SIAM Journal on Computing,
37(4):1077–1106, 2007. 2
Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin
Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015.
1, 4
Marek Cygan, Stefan Kratsch, Marcin Pilipczuk, Michal Pilipczuk, and Magnus Wahlström.
Clique cover and graph separation: New incompressibility results. ACM Transactions on
Computation Theory (TOCT), 6(2):6, 2014. 2
Holger Dell and Dieter van Melkebeek. Satisﬁability allows no nontrivial sparsiﬁcation unless
the polynomial-time hierarchy collapses. Journal of the ACM (JACM), 61(4):23:1–23:27,
2014. 2
Reinhard Diestel. Graph Theory, volume 173 of Graduate Texts in Mathematics. Springer,
4th edition, 2010. 4, 7
Michael Dom, Daniel Lokshtanov, and Saket Saurabh. Kernelization lower bounds through
colors and IDs. ACM Transactions on Algorithms, 11(2):13, 2014. 2
Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity.
Texts in Computer Science. Springer, 2013. 1, 4
Andrew Drucker. New limits to classical and quantum instance compression. SIAM Journal
on Computing, 44(5):1443–1479, 2015. 2
Pavel Dvořák and Dušan Knop. Parametrized complexity of length-bounded cuts and multicuts. In Proc. of the 12th Annual Conference on Theory and Applications of Models of
Computation (TAMC 2015), volume 9076 of LNCS, pages 441–452. Springer, 2015. 13
Michael R. Fellows, Ariel Kulik, Frances A. Rosamond, and Hadas Shachnai. Parameterized
approximation via ﬁdelity preserving transformations. In Proc. of the 39th International Colloquium on Automata, Languages, and Programming (ICALP 2012), volume 7391 of Lecture
Notes in Computer Science, pages 351–362. Springer, 2012. 2
Jörg Flum and Martin Grohe. Parameterized Complexity Theory. Springer, 2006. 1, 4
Till Fluschnik, Stefan Kratsch, Rolf Niedermeier, and Manuel Sorge. The parameterized complexity of the minimum shared edges problem. In Proc. of the 35th IARCS Annual Conference
on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2015),
volume 45 of LIPIcs, pages 448–462. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik,
2015. 2
Lance Fortnow and Rahul Santhanam. Infeasibility of instance compression and succinct
PCPs for NP. Journal of Computer and System Sciences, 77(1):91–106, 2011. 2
Michael R. Garey, David S. Johnson, and Larry J. Stockmeyer. Some simpliﬁed NP-complete
graph problems. Theoretical Computer Science, 1(3):237–267, 1976. 18
Petr A. Golovach and Dimitrios M. Thilikos. Paths of bounded length and their cuts: Parameterized complexity and algorithms. Discrete Optimization, 8(1):72–86, 2011. 2, 13, 14,
17
Sylvain Guillemot, Frédéric Havet, Christophe Paul, and Anthony Perez. On the (non)existence of polynomial kernels for Pl -free edge modiﬁcation problems. Algorithmica,
65(4):900–926, 2013. 3, 22
Jiong Guo and Rolf Niedermeier. Invitation to data reduction and problem kernelization.
ACM SIGACT News, 38(1):31–45, 2007. 2
Venkatesan Guruswami and Euiwoong Lee. Inapproximability of feedback vertex set for
23

[31]
[32]
[33]
[34]
[35]
[36]
[37]
[38]
[39]
[40]
[41]
[42]
[43]
[44]
[45]
[46]
[47]
[48]
[49]
[50]

bounded length cycles. Electronic Colloquium on Computational Complexity (ECCC), 21:6,
2014. 19, 20
Lenwood Scott Heath. Algorithms for Embedding Graphs in Books. PhD thesis, University
of North Carolina at Chapel Hill, USA, 1985. 14
Alon Itai, Yehoshua Perl, and Yossi Shiloach. The complexity of ﬁnding maximum disjoint
paths with length constraints. Networks, 12(3):277–286, 1982. 13
Stefan Kratsch. Recent developments in kernelization: A survey. Bulletin of the EATCS,
113:58–97, 2014. 1, 2, 5
Daniel Lokshtanov, Dániel Marx, and Saket Saurabh. Lower bounds based on the exponential
time hypothesis. Bulletin of the EATCS, 105:41–72, 2011. 1
Daniel Lokshtanov, Fahad Panolan, M. S. Ramanujan, and Saket Saurabh. Lossy kernelization. In Proc. of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC
2017), pages 224–237. ACM, 2017. 2
Kavindra Malik, Ashok K. Mittal, and Santosh K. Gupta. The k most vital arcs in the
shortest path problem. Operations Research Letters, 8(4):223–227, 1989. 13
Dániel Marx. Parameterized complexity and approximation algorithms. The Computer Journal, 51(1):60–78, 2008. 2
Karl Menger. Über reguläre Baumkurven. Mathematische Annalen, 96(1):572–582, 1927. 7
Bojan Mohar. Face covers and the genus problem for apex graphs. Journal of Combinatorial
Theory, Series B, 82(1):102–117, 2001. 14
Rolf Niedermeier. Invitation to Fixed-Parameter Algorithms. Oxford University Press, 2006.
1, 4
Feng Pan and Aaron Schild. Interdiction problems on planar graphs. Discrete Applied Mathematics, 198:215–231, 2016. 13
Baruch Schieber, Amotz Bar-Noy, and Samir Khuller. The complexity of ﬁnding most vital
arcs and nodes. Technical report, College Park, MD, USA, 1995. 14, 15
Anneke A. Schoone, Hans L. Bodlaender, and Jan van Leeuwen. Diameter increase caused
by edge deletion. Journal of Graph Theory, 11(3):409–427, 1987. 16, 18
Vijay V. Vazirani. Approximation Algorithms. Springer, 2001. 2
Douglas B. West. Introduction to Graph Theory. Prentice Hall, 2 edition, 2000. 4
David P. Williamson and David B. Shmoys. The Design of Approximation Algorithms. Cambridge University Press, 2011. 2
Ge Xia and Yong Zhang. On the small cycle transversal of planar graphs. Theoretical
Computer Science, 412(29):3501–3509, 2011. 3, 20
Ge Xia and Yong Zhang. Kernelization for cycle transversal problems. Discrete Applied
Mathematics, 160(7-8):1224–1231, 2012. 20
Mihalis Yannakakis. Node- and edge-deletion NP-complete problems. In Proc. of the 10th
Annual ACM Symposium on Theory of Computing (STOC 1978), pages 253–264. ACM, 1978.
19
Philipp Zschoche. On ﬁnding separators in temporal graphs. Master’s thesis, Institut für
Softwaretechnik und Theoretische Informatik, TU Berlin, 2017. 22

24

