arXiv:1704.07284v1 [] 24 Apr 2017

Optimal algorithms for hitting (topological) minors on
graphs of bounded treewidth∗
Julien Baste†

Ignasi Sau‡§

Dimitrios M. Thilikos‡ ¶

Abstract
For a fixed collection of graphs F , the F -M-Deletion problem consists in, given a
graph G and an integer k, decide whether there exists S ⊆ V (G) with |S| ≤ k such
that G \ S does not contain any of the graphs in F as a minor. We are interested
in the parameterized complexity of F -M-Deletion when the parameter is the
treewidth of G, denoted by tw. Our objective is to determine, for a fixed F , the
smallest function fF such that F -M-Deletion can be solved in time fF (tw) · nO(1)
on n-vertex graphs. Using and enhancing the machinery of boundaried graphs and
small sets of representatives introduced by Bodlaender et al. [J ACM, 2016], we
prove that when all the graphs in F are connected and at least one of them is
planar, then fF (w) = 2O(w·log w) . When F is a singleton containing a clique, a
cycle, or a path on i vertices, we prove the following asymptotically tight bounds:
• f{K4 } (w) = 2Θ(w·log w) .
• f{Ci } (w) = 2Θ(w) for every i ≤ 4, and f{Ci } (w) = 2Θ(w·log w) for every i ≥ 5.
• f{Pi } (w) = 2Θ(w) for every i ≤ 4, and f{Pi } (w) = 2Θ(w·log w) for every i ≥ 6.
The lower bounds hold unless the Exponential Time Hypothesis fails, and the superexponential ones are inspired by a reduction of Marcin Pilipczuk [Discrete Appl
Math, 2016]. The single-exponential algorithms use, in particular, the rank-based
approach introduced by Bodlaender et al. [Inform Comput, 2015]. We also consider the version of the problem where the graphs in F are forbidden as topological
minors, and prove that essentially the same set of results holds.

Keywords: parameterized complexity; graph minors; treewidth; hitting minors; topological minors; dynamic programming; Exponential Time Hypothesis.

∗

Emails of authors: baste@lirmm.fr, ignasi.sau@lirmm.fr, sedthilk@thilikos.info.
This work has been supported by project DEMOGRAPH (ANR-16-CE40-0028).
†
Université de Montpellier, LIRMM, Montpellier, France.
‡
AlGCo project-team, CNRS, LIRMM, France.
§
Departamento de Matemática, Universidade Federal do Ceará, Fortaleza, Brazil.
¶
Department of Mathematics, National and Kapodistrian University of Athens, Athens, Greece.

1

1

Introduction

Let F be a ﬁnite non-empty collection of non-empty graphs. In the F-M-Deletion
(resp. F-TM-Deletion) problem, we are given a graph G and an integer k, and the
objective is to decide whether there exists a set S ⊆ V (G) with |S| ≤ k such that G \ S
does not contain any of the graphs in F as a minor (resp. topological minor). These
problems have a big expressive power, as instantiations of them correspond to several
notorious problems. For instance, the cases F = {K2 }, F = {K3 }, and F = {K5 , K3,3 }
of F-M-Deletion (or F-TM-Deletion) correspond to Vertex Cover, Feedback
Vertex Set, and Vertex Planarization, respectively.
For the sake of readability, we use the notation F-Deletion in statements that
apply to both F-M-Deletion and F-TM-Deletion. Note that if F contains a graph
with at least one edge, then F-Deletion is NP-hard by the classical result of Lewis and
Yannakakis [26].
In this article we are interested in the parameterized complexity of F-Deletion
when the parameter is the treewidth of the input graph. Since the property of containing
a graph as a (topological) minor can be expressed in Monadic Second Order logic (see [22]
for explicit formulas), by Courcelle’s theorem [8], F-Deletion can be solved in time
O∗ (f (tw)) on graphs with treewidth at most tw, where f is some computable function1 .
Our objective is to determine, for a ﬁxed collection F, which is the smallest such function
f that one can (asymptotically) hope for, subject to reasonable complexity assumptions.
This line of research has attracted some interest during the last years in the parameterized complexity community. For instance, Vertex Cover is easily solvable
in time O∗ (2O(tw) ), called single-exponential, by standard dynamic-programming techniques, and no algorithm with running time O∗ (2o(tw) ) exists unless the Exponential
Time Hypothesis (ETH)2 fails [19].
For Feedback Vertex Set, standard dynamic programming techniques give a
running time of O∗ (2O(tw·log tw) ), while the lower bound under the ETH [19] is again
O∗ (2o(tw) ). This gap remained open for a while, until Cygan et al. [10] presented an optimal algorithm running in time O∗ (2O(tw) ), using the celebrated Cut&Count technique.
This article triggered several other techniques to obtain single-exponential algorithms for
so-called connectivity problems on graph of bounded treewidth, mostly based on algebraic
tools [2, 15].
Concerning Vertex Planarization, Jansen et al. [20] presented an algorithm of
time O∗ (2O(tw·log tw) ) as a crucial subroutine in an FPT algorithm parameterized by k.
Marcin Pilipczuk [30] proved that this running time is optimal under the ETH, by using
the framework introduced by Lokshtanov et al. [28] for proving superexponential lower
bounds.

1
2

The notation O∗ (·) suppresses polynomial factors depending on the size of the input graph.
The ETH states that 3-SAT on n variables cannot be solved in time 2o(n) ; see [19] for more details.

2

Our results. We present a number of upper and lower bounds for F-Deletion parameterized by treewidth, several of them being tight. Namely, we prove the following
results, all the lower bounds holding under the ETH:
 O(tw·log tw) 
.
1. For every F, F-Deletion can be solved in time O∗ 22
2. For every connected3 F containing at least one planar graph (resp. subcubic
planar graph), F-M-Deletion
(resp. F-TM-Deletion) can be solved in time

∗
O(tw·log
tw)
O 2
.
3. For any connected F, F-Deletion cannot be solved in time O∗ (2o(tw) ).

4. When F = {Ki }, the clique on i vertices, {Ki }-Deletion cannot be solved in
time O∗ (2o(tw·log tw) ) for i ≥ 4. Note that {Ki }-Deletion can be solved in time
O∗ (2O(tw) ) for i ≤ 3 [10], and that the case i = 4 is tight by item 2 above (as K4
is planar).
5. When F = {Ci }, the cycle on i vertices, {Ci }-Deletion can be solved in time
O∗ (2O(tw) ) for i ≤ 4, and cannot be solved in time O∗ (2o(tw·log tw) ) for i ≥ 5.
Note that, by items 2 and 3 above, this settles completely the complexity of {Ci }Deletion for every i ≥ 3.
6. When F = {Pi }, the path on i vertices, {Pi }-Deletion can be solved in time
O∗ (2O(tw) ) for i ≤ 4, and cannot be solved in time O∗ (2o(tw·log tw) ) for i ≥ 6.
Note that, by items 2 and 3 above, this settles completely the complexity of {Pi }Deletion for every i ≥ 2, except for i = 5, where there is still a gap.
The results discussed in the last three items are summarized in Table 1. Note that
the cases with i ≤ 3 were already known [10, 19], except when F = {P3 }.
❍
i
❍
F ❍❍❍

2

3

4

5

≥6

Ki
Ci
Pi

tw
tw
tw

tw
tw
tw

tw · log tw
tw
tw

tw · log tw ? 2O(tw·log tw)
tw · log tw
tw ? tw · log tw

tw · log tw ? 2O(tw·log tw)
tw · log tw
tw · log tw

Table 1: Summary of our results when F equals {Ki }, {Ci }, or {Pi }. If only one value
‘x’ is written in the table (like ‘tw’), it means that the corresponding problem can be
solved in time O∗ (2O(x) ) and that this bound is tight. An entry of the form ‘x ? y’
means that the corresponding problem cannot be solved in time O∗ (2o(x) ), and that it
can be solved in time O∗ (2O(y) ). We interpret {C2 }-Deletion as Feedback Vertex
Set. Grey cells correspond to known results.
3

A connected collection F is a collection containing only connected graphs.

3

 O(tw·log tw) 
uses and, a sense,
Our techniques. The algorithm running in time O∗ 22
enhances, the machinery of boundaried graphs, equivalence relations, and representatives
originating in the seminal work of Bodlaender et al. [5], and which has been subsequently
used in [16, 17, 22]. For technical reasons, we use branch decompositions instead of
tree decompositions, whose associated widths are equivalent from a parametric point of
view [32].

In order to obtain the faster algorithm running in time O∗ 2O(tw·log tw) when F
is a connected collection containing at least a (subcubic) planar graph, we combine the
above ingredients with additional arguments to bound the number and the size of the
representatives of the equivalence relation deﬁned by the encoding that we use to construct the partial solutions. Here, the connectivity of F guarantees that every connected
component of a minimum-sized representative intersects its boundary set (cf. Lemma 6).
The fact that F contains a (subcubic) planar graph is essential in order to bound the
treewidth of the resulting graph after deleting a partial solution (cf. Lemma 13).
We present these algorithms for the topological minor version and then it is easy to
adapt them to the minor version within the claimed running time (cf. Lemma 4).
The single-exponential algorithms when F ∈ {{P3 }, {P4 }, {C4 }} are ad hoc. Namely,
the algorithms for {P3 }-Deletion and {P4 }-Deletion use standard (but nontrivial)
dynamic programming techniques on graphs of bounded treewidth, exploiting the simple
structure of graphs that do not contain P3 or P4 as a minor (or as a subgraph, which
in the case of paths is equivalent). The algorithm for {C4 }-Deletion is more involved,
and uses the rank-based approach introduced by Bodlaender et al. [2], exploiting again
the structure of graphs that do not contain C4 as a minor (cf. Lemma 20). It might
seem counterintuitive that this technique works for C4 , and stops working for Ci with
i ≥ 5 (see Table 1). A possible reason for that is that the only cycles of a C4 -minor-free
graph are triangles and each triangle is contained in a bag of a tree decomposition. This
property, which is not true anymore for Ci -minor-free graphs with i ≥ 5, permits to keep
track of the structure of partial solutions with tables of small size.
As for the lower bounds, the general lower bound of O∗ (2o(tw) ) for connected collections is based on a simple reduction from Vertex Cover. The superexponential lower
bounds, namely O∗ (2o(tw·log tw) ), are strongly based on the ideas presented by Marcin
Pilipczuk [30] for Vertex Planarization. We present a general hardness result (cf.
Theorem 14) that applies to wide families of connected collections F. Then, our superexponential lower bounds, as well as the result of Marcin Pilipczuk [30] itself, are corollaries
of this general result. Combining Theorem 14 with item 2 above, it easily follows that
the running time O∗ (2O(tw·log tw) ) is tight for a wide family of F, for example, when all
graphs in F are planar and 3-connected.
Organization of the paper. In Section 2 we give some preliminaries. The algorithms
based on boundaried graphs and representatives are given in Section 3, and the singleexponential algorithms for hitting paths and cycles are given in Section 4. The general
lower bound for connected collections is presented in Section 5, and the superexponential
lower bounds are presented in Section 6. We conclude the article in Section 7.
4

2

Preliminaries

In this section we provide some preliminaries to be used in the following sections.
Sets, integers, and functions. We denote by N the set of every non-negative integer
and we set N+ = N \ {0}. Given two integers p and q, the set [p, q] refers to the set
of every integer r such that p ≤ r ≤ q. Moreover, for each integer p ≥ 1, we set
N≥p = N \ [0, p − 1]. In the set [1, k] × [1, k], a row is a set {i} × [1, k] and a column is a
set [1, k] × {i} for some i ∈ [1, k].
We use ∅ to denote the empty set and ∅ to denote the empty function, i.e., the unique
subset of ∅ × ∅. Given a function f : A → B and
S a set S, we deﬁne f |S = {(x, f (x)) |
x ∈ S ∩ A}. Moreover if S ⊆ A, we set f (S) = s∈S {f (s)}. Given a set S, we denote

by S2 the set containing every subset of S that has cardinality 2. We also denote by
2S the set of all the subsets ofSS. If S
S is a collection of objects where the operation ∪ is
deﬁned, then we then denote S = X∈S X.
Let p ∈ N with p ≥ 2, let f : Np → N, and let g : Np−1 → N. We say that
f (x1 , . . . , xp ) = Oxp (g(x1 , . . . , xp−1 )) if there is a function h : N → N such that
f (x1 , . . . , xp ) = O(h(xp ) · g(x1 , . . . , xp−1 )).
Graphs. All the graphs that we consider in this paper are undirected, ﬁnite, and
without loops or multiple edges. We use standard graph-theoretic notation, and we refer
the reader to [11] for any undeﬁned terminology. Given a graph G, we denote by V (G)
the set of vertices of G and by E(G) the set of the edges of G. We call |V (G)| the
size of G. A graph is the empty graph if its size is 0. We also denote by L(G) the
set of the vertices of G that have degree exactly 1. If G is a tree (i.e., a connected
acyclic graph) then L(G) is the set of the leaves of G. A vertex labeling of G is some
injection ρ : V (G) → N+ . Given a vertex v ∈ V (G), we deﬁne the neighborhood of
v as NG (v) = {u | u ∈ V (G), {u, v} ∈ E(G)} and the closedS neighborhood of v as
NG [v] = NG (v) ∪ {v}. If X ⊆ V (G), then we write NG (X) = ( v∈X NG (v)) \ X. The
degree of a vertex v in G is deﬁned as degG (v) = |NG (v)|. A graph is called subcubic if
all its vertices have degree at most 3.
A subgraph H = (VH, EH ) of a graph G = (V, E) is a graph such that VH ⊆ V (G)
and EH ⊆ E(G) ∩ V (H)
. If S ⊆ V (G), the subgraph of G induced by S, denoted G[S],
2
S
is the graph (S, E(G) ∩ 2 ). We also deﬁne G \ S to be the subgraph of G induced by
V (G) \ S. If S ⊆ E(G), we denote by G \ S the graph (V (G), E(G) \ S).
If s, t ∈ V (G), an (s, t)-path of G is any connected subgraph P of G with maximum
degree 2 and where s, t ∈ L(P ). We ﬁnally denote by P(G) the set of all paths of G.
Given P ∈ P(G), we say that v ∈ V (P ) is an internal vertex of P if degP (v) = 2. Given
an integer i and a graph G, we say that G is i-connected if for each {u, v} ∈ V (G)
, there
2
exists a set Q ⊆ P(G) of (u, v)-paths of G such that |Q| = i and for each P1 , P2 ∈ Q
such that P1 6= P2 , V (P1 ) ∩ V (P2 ) = {u, v}.
We denote by Kr the complete graph on r vertices, by Kr1 ,r2 the complete bipartite
+
graph where the one part has r1 vertices and the other r2 , and by K2,r
the graph obtained
5

if we take K2,r and add an edge between the two vertices of the part of size 2. Finally
we denote by Pk and Ck the path and cycles of k vertices respectively. We deﬁne the
+
diamond to be the graph K2,2
.
Block-cut trees. A connected graph G is biconnected if for any v ∈ V (G), G \ {v} is
connected (notice that K2 is the only biconnected graph that it is not 2-connected). A
block of a graph G is a maximal biconnected subgraph of G. We name block(G) the set
of all blocks of G and we name cut(G) the set of all cut vertices of G. If G is connected,
we deﬁne the block-cut tree of G to be the tree bct(G) = (V, E) such that
• V = block(G) ∪ cut(G) and
• E = {{B, v} | B ∈ block(G), v ∈ cut(G) ∩ V (B)}.
Note that L(bct(G)) ⊆ block(G). It is worth mentioning that the block-cut tree of a
graph can be computed in linear time using depth-ﬁrst search [18].
Let F be a set of connected graphs such that for each H ∈ F, |V (H)| ≥ 2. Given
H ∈ F and B ∈ L(bct(H)), we say that (H, B) is an essential pair if for each H ′ ∈ F
and each B ′ ∈ L(bct(H ′ )), |E(B)| ≤ |E(B ′ )|. Given an essential pair (H, B) of F, we
deﬁne the first vertex of (H, B) to be, if it exists, the only cut vertex of H contained in
V (B), or an arbitrarily chosen vertex of V (B) otherwise. We deﬁne the second vertex of
(H, B) to be an arbitrarily chosen vertex of V (B) that is a neighbor in H[B] of the ﬁrst
vertex of (H, B). Note that, given an essential pair (H, B) of F, the ﬁrst vertex and the
second vertex of (H, B) exist and, by deﬁnition, are ﬁxed.
Moreover, given an essential pair (H, B) of F, we deﬁne the core of (H, B) to be the
graph H \ (V (B) \ {a}) where a is the ﬁrst vertex of (H, B). Note that a is a vertex of
the core of (H, B).
For the statement of our results, we need to consider the class K containing every
+
| r ≥ 0} = ∅.
connected graph G such that L(bct(G)) ∩ {K2,r , K2,r
Minors and topological minors. Given two graphs H and G and two functions
φ : V (H) → V (G) and σ : E(H) → P(G), we say that (φ, σ) is a topological minor
model of H in G if
• for every {x, y} ∈ E(H), σ({x, y}) is an (φ(x), φ(y))-path in G and
• if P1 , P2 are two distinct paths in σ(E(H)), then none of the internal vertices of
P1 is a vertex of P2 .
The branch vertices of (φ, σ) are the vertices in φ(V (E)), while the subdivision vertices
of (φ, σ) are the internal vertices of the paths in σ(E(H)).
We say that G contains H as a topological minor, denoted by H tm G, if there is a
topological minor model (φ, σ) of H in G.
Given two graphs H and G and a function φ : V (H) → 2V (G) , we say that φ is a
minor model of H in G if
6

• for every x ∈ V (H), G[φ(x)] is a connected non-empty graph and
• for every {x, y} ∈ E(H), there exist x′ ∈ φ(x) and y ′ ∈ φ(y) such that {x′ , y ′ } ∈
E(G).
We say that G contains H as a minor, denoted by H m G, if there is a minor model
φ of H in G.
Let H be a graph. We deﬁne the set of graphs tpm(H) as follows: among all the
graphs containing H as a minor, we consider only those that are minimal with respect
to the topological minor relation. The following two observations follow easily from the
above deﬁnitions.
Observation 1. There is a function f1 : N → N such that for every h-vertex graph H,
every graph in tpm(H) has at most f1 (h) vertices.
Observation 2. Given two graphs H and G, H is a minor of G if and only if some of
the graphs in tpm(H) is a topological minor of G.
Graph separators and (topological) minors. Let G be a graph and S ⊆ V (G). Then
for each connected component C of G \ S, we deﬁne the cut-clique of the triple (C, G, S)

to be the graph whose vertex set is V (C)∪ S and whose edge set is E(G[V (C)∪ S])∪ S2 .

Lemma 1. Let i ≥ 2 be an integer, let H be an i-connected graph, let G be a graph, and
let S ⊆ V (G) such that |S| ≤ i − 1. If H is a topological minor (resp. a minor) of G,
then there exists a connected component G′ of G \ S such that H is a topological minor
(resp. a minor) of the cut-clique of (G′ , G, S).
Proof. We prove the lemma for the topological minor version, and the minor version can
be proved with the same kind of arguments. Let i, H, G, and S be deﬁned as in the
statement of the lemma. Assume that H tm G and let (φ, σ) be a topological minor
model of H in G. If S is not a separator of G, then the statement is trivial, as in that
case the cut-clique of (G \ S, G, S) is a supergraph of G. Suppose henceforth that S is a
separator of G, and assume for contradiction that there exist two connected components
G1 and G2 of G \ S and two distinct vertices x1 and x2 of H such that φ(x1 ) ∈ V (G1 )
and φ(x2 ) ∈ V (G2 ). Then, as H is i-connected, there should be i internally vertexdisjoint paths from φ(x1 ) to φ(x2 ) in G. As S is a separator of size at most i − 1, this is
not possible. Thus, there exists a connected component G′ of G \ S such that for each
x ∈ V (H), φ(x) ∈ V (G′ )∪S. This implies that H is a topological minor of the cut-clique
of (G′ , G, S).
Lemma 2. Let G be a connected graph, let v be a cut vertex of G, and let V be the vertex
set of a connected component of G \ {v}. If H is a connected graph such that H tm G
and for each leaf B of bct(H), B 6tm G[V ∪ {v}], then H tm G \ V .
Proof. Let G, v, V , and H be deﬁned as in the statement of the lemma. Let B ∈
L(bct(H)). If B is a single edge, then the condition B 6tm G[V ∪ {v}] implies that
7

V = ∅. But V is the vertex set of a connected component of G \ {v} and so V 6= ∅. This
implies that the case B is a single edge cannot occur. If B is not a simple edge, then
by deﬁnition B is 2-connected and then, by Lemma 1, B tm G \ V . This implies that
there is a topological minor model (φ, σ) of H in G such that for each B ∈ L(bct(H))
and for each b ∈ B, φ(b) 6∈ V .
S
We show now that for each x ∈ V (H), φ(x) 6∈ V . If V (H) \ ( B∈L(bct(H))
V (B)) = ∅
S
then the result is already proved. Otherwise, let x ∈ V (H)S\ ( B∈L(bct(H)) V (B)).
By deﬁnition of the block-cut tree, there exist b1 and b2 in B∈L(bct(H)) V (B) such
that x lies on a (b1 , b2 )-path P of P(H). Let Pi be the (bi , x)-subpath of P for each
i ∈ {1, 2}. By deﬁnition of P , we have that V (P1 ) ∩ V (P2 ) = {x}. This implies
that there exists a (φ(b1 ), φ(x))-path P1′ and a (φ(b2 ), φ(x))-path P2′ in P(G) such that
V (P1′ ) ∩ V (P2′ ) = {φ(x)}. Then, as v is a cut vertex of G, it follows that φ(x) 6∈ V .
Thus, for each x ∈ V (H), φ(x) 6∈ V . Let {x, y} be an edge of E(H). As σ({x, y}) is a
simple (φ(x), φ(y))-path, both φ(x) and φ(y) are not in V and v is a cut vertex of G, we
have, with the same argumentation that before that, for each z ∈ V (σ({x, y}), z 6∈ V .
This concludes the proof.
Using the same kind of argumentation with minors instead of topological minors, we
also obtain the following lemma.
Lemma 3. Let G be a connected graph, let v be a cut vertex of G, and let V be the
vertex set of a connected component of G \ {v}. If H is a graph such that H m G and
for each leaf B of bct(H), B 6m G[V ∪ {v}], then H m G \ V .
In the above two lemmas, we have required graph H to be connected so that bct(H)
is well-deﬁned, but we could relax this requirement, and replace in both statements “for
each leaf B of bct(H)” with “for each connected component H ′ of H and each leaf B of
bct(H ′ )”.
Graph collections. Let F be a collection of graphs. From now on instead of “collection
of graphs” we use the shortcut “collection”. If F is a collection that is ﬁnite, non-empty,
and all its graphs are non-empty, then we say that F is a regular collection. For any
regular collection F, we deﬁne size(F) = max{|V (H)| | H ∈ F} ∪ {|F|}. Note that
if the size of F is bounded, then the size of the graphs in F is also bounded. We say
that F is a planar collection (resp. planar subcubic collection) if it is regular and at
least one of the graphs in F is planar (resp. planar and subcubic). We say that F is a
connected collection if it is regular and all the graphs in F are connected. We say that
F is an (topological) minor antichain if no two of its elements are comparable via the
(topological) minor relation.
Let F be a regular collection. We extend the (topological) minor relation to F such
that, given a graph G, F tm G (resp. F m G) if and only if there exists a graph
H ∈ F such that H tm G (resp. H m G). We also denote extm (F) = {G | F tm G},
i.e., extm (F) is the class of graphs that do not contain any graph in F as a topological
minor. The set exm (F) is deﬁned analogously.
8

Tree decompositions. A tree decomposition of a graph G is a pair D = (T, X ), where
T is a tree and X = {Xt | t ∈ V (T )} is a collection of subsets of V (G) such that:
S
• t∈V (T ) Xt = V (G),
• for every edge {u, v} ∈ E, there is a t ∈ V (T ) such that {u, v} ⊆ Xt , and

• for each {x, y, z} ⊆ V (T ) such that z lies on the unique path between x and y in
T , Xx ∩ Xy ⊆ Xz .
We call the vertices of T nodes of D and the sets in X bags of D. The width of a tree
decomposition D = (T, X ) is maxt∈V (T ) |Xt | − 1. The treewidth of a graph G, denoted
by tw(G), is the smallest integer w such that there exists a tree decomposition of G of
width at most w. For each t ∈ V (T ), we denote by Et the set E(G[Xt ]).
Parameterized complexity. We refer the reader to [9, 12] for basic background on
parameterized complexity, and we recall here only some very basic deﬁnitions. A parameterized problem is a language L ⊆ Σ∗ × N. For an instance I = (x, k) ∈ Σ∗ × N, k
is called the parameter. A parameterized problem is fixed-parameter tractable (FPT) if
there exists an algorithm A, a computable function f , and a constant c such that given
an instance I = (x, k), A (called an FPT algorithm) correctly decides whether I ∈ L in
time bounded by f (k) · |I|c .
Definition of the problems. Let F be a regular collection. We deﬁne the parameter
tmF as the function that maps graphs to non-negative integers as follows:
tmF (G) = min{|S| | S ⊆ V (G) ∧ G \ S ∈ extm (F)}.

(1)

The parameter mF is deﬁned analogously. The main objective of this paper is to study
the problem of computing the parameters tmF and mF for graphs of bounded treewidth
under several instantiations of the collection F. The corresponding decision problems
are formally deﬁned as follows.
F-M-Deletion
Input: A graph G and an integer k ∈ N.
Parameter: The treewidth of G.
Output: Is mF (G) ≤ k?

F-TM-Deletion
Input: A graph G and an integer k ∈ N.
Parameter: The treewidth of G.
Output: Is tmF (G) ≤ k?

Note that in both above problems, we can always assume that F is an antichain with
respect to the considered relation. Indeed, this is the case because if F is contains two
graphs H1 and H2 where H1 tm H2 , then tmF (G) = tmF ′ (G) where F ′ = F \ {H2 }
(similarly for the minor relation).
Throughout the article, we let n and tw be the number of vertices and the treewidth
of the input graph of the considered problem, respectively. In some proofs, we will also
use w to denote the width of a (nice) tree decomposition that is given together with the
input graph (which will diﬀer from tw by at most a factor 5).
9

3

Dynamic programming algorithms for computing tmF

The purpose of this section is to prove the following results.
Theorem 1. If F is a regular collection, where d = size(F), then there exists an algoO (tw·log tw)
rithm that solves F-TM-Deletion in 22 d
· n steps.
Theorem 2. If F is a connected and planar subcubic collection, where d = size(F), then
there exists an algorithm that solves F-TM-Deletion in 2Od (tw·log tw) · n steps.
Theorem 3. If F is a regular collection, where d = size(F), then there exists an algoO (tw·log tw)
· n steps.
rithm that solves F-M-Deletion in 22 d
Theorem 4. If F is a connected and planar collection, where d = size(F), then there
exists an algorithm that solves F-M-Deletion in 2Od (tw·log tw) · n steps.
The following lemma is a direct consequence of Observation 2.
Lemma 4. Let F be aS
regular collection. Then, for every graph G, it holds that mF (G) =
tmF ′ (G) where F ′ = F ∈F tpm(F ).

It is easy to see that for every (planar) graph F , the set tpm(F ) contains a subcubic
(planar) graph. Combining this observation with Lemma 4 and Observation 1, Theorems 3 and 4 follow directly from Theorems 1 and 2, respectively. The rest of this section
is dedicated to the proofs of Theorems 1 and 2. We ﬁrst need to provide some preliminaries in Subsections 3.1 and 3.2. The proof of Theorem 3 presented in Subsection 3.3.
Before we present the proof of Theorem 2 in Subsection 3.5, we give in Subsection 3.4
bounds on the sets of representatives when F is a connected and planar collection.

3.1

Boundaried graphs and their equivalence classes

Many of the following deﬁnitions were introduced in [5, 16] (see also [17, 22].
Boundaried graphs. Let t ∈ N. A t-boundaried graph is a triple G = (G, R, λ) where
G is a graph, R ⊆ V (G), |R| = t, and λ : R → N+ is an injective function. We call R
the boundary of G and we call the vertices of R the boundary vertices of G. We also
call G the underlying graph of G. Moreover, we call t = |R| the boundary size of G
and we deﬁne the label set of G as Λ(G) = λ(R). We also say that G is a boundaried
graph if there exists an integer t such that G is an t-boundaried graph. We say that a
boundary graph G is consecutive if Λ(G) = [1, |R|]. We deﬁne the size of G = (G, R, λ),
as |V (G)| and we use the notation V (G) and E(G) for V (G) and E(G), respectively. If
S ⊆ V (G), we deﬁne G′ = G \ S such that G′ = (G′ , R′ , λ′ ), G′ = G \ S, R′ = R \ S, and
λ′ = λ|R′ . We deﬁne B (t) as the set of all t-boundaried graphs. We also use the notation
B∅ = ((∅, {∅}), ∅, ∅) to denote the (unique) 0-boundaried empty boundaried graph.
Given a t-boundaried graph G = (G, R, λ), we deﬁne ψG : R → [1, t] such that for
each v ∈ R, ψG (v) = |{u ∈ R | λ(u) ≤ λ(v)}|. Note that, as λ is an injective function,
ψG is a bijection and, given a boundary vertex v of G, we call ψG (v) the index of v.
10

Let t ∈ N. We say that two t-boundaried graphs G1 = (G1 , R1 , λ1 ) and G2 =
(G2 , R2 , λ2 ) are isomorphic if there is a bijection σ : V (G1 ) → V (G2 ) that is an isomor−1
◦ ψG2 ⊆ σ, i.e., σ sends
phism σ : V (G1 ) → V (G2 ) from G1 to G2 and additionally ψG
1
the boundary vertices of G1 to equally-indexed boundary vertices of G2 . We say that G1
−1
◦ ψG2 is an isomorphism from G1 [R1 ] to G2 [R2 ]
and G2 are boundary-isomorphic if ψG
1
and we denote this fact by G1 ∼ G2 . It is easy to make the following observation.
Observation 3. For every t ∈ N, if S is a collection of t-boundaried graphs where
t
|S| > 2(2) , then S contains at least two boundary-isomorphic graphs.
Topological minors of boundaried graphs. Let G1 = (G1 , R1 , λ1 ) and G2 =
(G2 , R2 , λ2 ) be two boundaried graphs. We say that G1 is a topological minor of G2 if
there is a topological minor model (φ, σ) of G1 in G2 such that
• ψG1 = ψG2 ◦ φ|R1 , i.e., the vertices of R1 are mapped via φ to equally indexed
vertices of R2 and
• none of the vertices in R2 \ φ(R1 ) is a subdivision vertex of (φ, σ).
Operations on boundaried graphs. Let G1 = (G1 , R1 , λ1 ) and G2 = (G2 , R2 , λ2 )
be two t-boundaried graphs. We deﬁne the gluing operation ⊕ such that (G1 , R1 , λ1 ) ⊕
(G2 , R2 , λ2 ) is the graph G obtained by taking the disjoint union of G1 and G2 and
−1
−1
then, for each i ∈ [1, t], identifying the vertex ψG
(i) and the vertex ψG
(i). Keep in
1
2
mind that G1 ⊕ G2 is a graph and not a boundaried graph. Moreover, the operation ⊕
requires both boundaried graphs to have boundaries of the same size.
Let G = (G, R, λ) be a t-boundaried graph and let I ⊆ N. We use the notation
G|I = (G, λ−1 (I), λ|λ−1 (I) ), i.e., we do not include in the boundary anymore the vertices
that are not indexed by numbers in I. Clearly, G|I is a t′ -boundaried graph where
t′ = |I ∩ Λ(G)|.
Let G1 = (G1 , R1 , λ1 ) and G2 = (G2 , R2 , λ2 ) be two boundaried graphs. Let also
I = λ1 (R1 ) ∩ λ2 (R2 ) and let t = |R1 | + |R2 | − |I|. We deﬁne the merging operation ⊙
such that (G1 , R1 , λ1 ) ⊙ (G2 , R2 , λ2 ) is the t-boundaried graph G = (G, R, λ) where G
is obtained by taking the disjoint union of G1 and G2 and then for each i ∈ I identify
−1
the vertex λ−1
1 (i) with the vertex λ2 (i). Similarly, R is the obtained by R1 ∪ R2 after
applying the same identiﬁcations to pairs of vertices in R1 and R2 . Finally, λ = λ′1 ∪ λ′2
where, for j ∈ [1, 2], λ′j is obtained from λj after replacing each (x, i) ∈ λj (for some
−1
i ∈ I) by (xnew , i), where xnew is the result of the identiﬁcation of λ−1
1 (i) and λ2 (i).
Observe that G1 ⊙ G2 is a boundaried graph and that the operation ⊙ does not require
input boundaried graphs to have boundaries of the same size.
Let G = (G, R, λ) be a consecutive t-boundaried graph and let I ⊆ N be such that
|I| = t. We deﬁne G = (G, R, λ) ⋄ I as the unique t-boundaried graph G′ = (G, R, λ′ )
where λ′ : R → I is a bijection and ψG′ = λ.

11

Equivalence relations. Let F be a regular collection and let t be a non-negative
integer. We deﬁne an equivalence relation ≡(F ,t) on t-boundaried graphs as follows:
Given two t-boundaried graphs G1 and G2 , we write G1 ≡(F ,t) G2 to denote that
∀G ∈ B (t) F tm G ⊕ G1 ⇐⇒ F tm G ⊕ G2 .
It is easy to verify that ≡(F ,t) is an equivalent relation. We set up a set of representatives
R(F ,t) as a set containing, for each equivalent class C of ≡(F ,t) , some consecutive tboundaried graph in C with minimum number of edges and no isolated vertices out of
its boundary (if there are more than one such graphs, pick one arbitrarily). Given a
t-boundaried graph G we denote by rep(F ) (G) the t-boundaried graph B ∈ R(F ,t) where
B ≡(F ,t) G and we call B the F-representative of G. Clearly, rep(F ) (B) = B.
Note that if B = (B, R, λ) is a t-boundaried graph and F tm B, then rep(F ) (B)
is, by deﬁnition, a consecutive t-boundaried graph whose underlying graph is a graph
H ∈ F with minimum number of edges, possibly completed with t − |V (H)| isolated
vertices in the case where |V (H)| < t. We denote this graph by F(F ,t) (if there are many
possible choices, just pick one arbitrarily). Note also that the underlying graph of every
boundaried graph in R(F ,t) \ {F(F ,t) } belongs in extm (F).
We need the following three lemmata. The ﬁrst one is a direct consequence of the
deﬁnitions of the equivalence relation ≡(F ,t) and the set of representatives R(F ,t) .
Lemma 5. Let F be a regular collection and let t ∈ N. Let also B1 and B2 be tboundaried graphs. Then B1 ≡(F ,t) B2 if an only if ∀G ∈ R(F ,t) F tm G ⊕ B1 ⇐⇒
F tm G ⊕ B2 .
Lemma 6. Let F be a connected collection and let t ∈ N. Let also B ∈ R(F ,t) . Then
every connected component of the underlying graph of B intersects its boundary set.
Proof. Let B = (B, R, λ) ∈ R(F ,t) . As the lemma follows directly in the case where
B = F(F ,t) , we may assume that F 6tm B. We assume, towards a contradiction, that
B has a component C whose vertex set does not contain any of the vertices of R. This
means that B can be seen as the disjoint union of C and B ′ = B \ V (C). As F 6tm B,
we also have that F 6tm C. Let now B′ = (B ′ , R, λ). Clearly |E(B′ )| < |E(B)|. We
will arrive to a contradiction by proving that B′ ≡(F ,t) B. Let G ∈ B (t) . Note that
G ⊕ B is the disjoint union of G ⊕ B′ and C. As all graphs in F are connected, it follows
that a (connected) graph H ∈ F is a topological minor of G ⊕ B if and only if H is a
topological minor of G ⊕ B′ . We conclude that B′ ≡(F ,t) B, a contradiction.
Lemma 7. Let F be a connected collection. Then, for every graph B, it holds that
rep(F ) ((B, ∅, ∅)) = B∅ if and only if F 6tm G.
Proof. Let B = (B, ∅, ∅) where B is a graph. Recall that if F tm B, then rep(F ) (B) =
F(F ,t) . As F does not contain the empty graph, we have that F(F ,t) 6= B∅ , therefore
rep(F ) (B) 6= B∅ .
Suppose now that F 6tm B. We have to prove that for every G ∈ B (0) , F tm
G ⊕ B ⇐⇒ F tm G ⊕ B∅ . Let G = (G, ∅, ∅) ∈ B (0) . Note that G ⊕ B is the disjoint
12

union of G and B and that G ⊕ B∅ = G. As F 6tm B and F is connected, it follows
that the disjoint union of B and G contains some (connected) graph in F if and only if
B does. This implies that F tm G ⊕ B ⇐⇒ F tm G ⊕ B∅ , as required.
(t)

Folios. Let F be a regular collection. Given t, r ∈ N, we deﬁne AF ,r as the set of
all pairwise non-isomorphic boundaried graphs that contain at most r non-boundary
vertices, whose label set is a subset of [1, t], and whose underlying graph belongs in
(t)
extm (F). Note that a graph in AF ,r is not necessarily a t-boundaried graph.
Given a t-boundaried graph B and an integer r ∈ N, we deﬁne the (F, r)-folio of
(t)
B, denoted by folio(B, F, r) the set containing all boundaried graphs in AF ,r that are
topological minors of B. Moreover, in case F tm B, we also include in folio(B, F, r)
the graph F(F ,t) .
(t)

(t)

(F ,t) }

We also deﬁne FF ,r = 2AF ,r ∪{F
(t)

and notice that {folio(B, F, r) | B ∈ B (t) } ⊆

(t)

FF ,r , i.e., FF ,r contains all diﬀerent (F, r)-folios of t-boundaried graphs.
Lemma 8. Let t ∈ N and let F be a regular collection. For every t-boundaried graph
B and every r ∈ N, it holds that |folio(B, F, r)| = 2Or+d (t log t) , where d = size(F).
Or+d (t log t)
(t)
.
Moreover, |FF ,r | = 22
Proof. Let t ∈ N, let F be a regular collection, let r ∈ N, and let n = t + r. We prove
(t)
(t)
a stronger result, namely that |AF ,r | = 2Or+d (t log t) . The claimed bound on |FF ,r | then
(t)

follows directly by deﬁnition of the set FF ,r . By [25], there exists a constant c such that
for each G ∈ extm (F), |E(G)| ≤ c · |V (G)|. By deﬁnition, every underlying graph of an
(t)
(t)
element of AF ,r is in extm (F). If we want to construct an element G = (G, R, λ) of AF ,r

n2
≤ c · n1+2·c·n
with at most n vertices, then there are asymptotically at most c · n · c·n

n
t
|R|
choices for the edge set E(G), at most t · t ≤ t · n choices for R, and t ≤ tt choices
(t)

for the function λ. We obtain that AF ,r is of size at most n · 2(1+2·c·n) log n · 2t log t =
2Or+d (t log t) , and the lemma follows.

The following lemma indicates that folios deﬁne a reﬁnement of the equivalence relation ≡(F ,t) .
Lemma 9. Let F be a regular collection and let d = size(F). Let also B1 and B2 be two
t-boundaried graphs. If folio(B1 , F, d) = folio(B2 , F, d), then B1 ≡(F ,t) B2 .
Proof. Let B1 and B2 be two t-boundaried graphs such that folio(B1 , F, d) = folio(B2 , F, d).
We ﬁx G ∈ B (t) , and we need to prove that F tm G ⊕ B1 if and only if F tm G ⊕ B2 .
Assume ﬁrst that F tm G ⊕ B1 . Then there exists a graph F ∈ F and a topological
minor model (φ, σ) of F in G⊕ B1 . This topological minor model (φ, σ) can be naturally
decomposed into two topological minor models (φ0 , σ0 ) and (φ1 , σ1 ) of two graphs F0
(t)
and F1 in AF ,d , respectively, with F0 ⊙ F1 = F , such that (φ0 , σ0 ) (resp. (φ1 , σ1 )) is
a topological minor model of F0 (resp. F1 ) in the (boundaried) graph G (resp. B1 ).
13

Since folio(B1 , F, d) = folio(B2 , F, d), there exists a topological minor model (φ2 , σ2 ) of
F1 in B2 . Combining the topological minor models (φ0 , σ0 ) and (φ2 , σ2 ) gives rise to a
topological minor model (φ′ , σ ′ ) of F in G ⊕ B2 , and therefore F tm G ⊕ B2 .
Conversely, assume that F 6tm G ⊕ B1 , and assume for contradiction that there
exists a graph F ∈ F and a topological minor model (φ, σ) of F in G ⊕ B2 . Using
the same arguments as above, (φ, σ) implies the existence of a topological minor model
(φ′ , σ ′ ) of F in G ⊕ B1 , contradicting the hypothesis that F 6tm G ⊕ B1 .
Lemmata 8 and 9 directly imply the following.
Lemma 10. There exists a function h1 : N × N → N such that if F is a regular collection
O (t·log t)
.
and t ∈ N, then |R(F ,t) | ≤ h1 (d, t) where d = size(F). Moreover h1 (d, t) = 22 d

3.2

Branch decompositions of boundaried graphs

Let G = (G, R, λ) be a boundaried graph and let ρ be a vertex labeling of G where
λ ⊆ ρ. A branch decomposition of G is a pair (T, σ) where T is a ternary tree and
σ : E(G) ∪ {R} → L(T ) is a bijection. Let r = σ(R) and let er be the unique edge in
T that is incident to r. We call r the root of T . Given an edge e ∈ E(T ), we deﬁne Te
as the one of the two connected components of T \{e} that does not contain the
S root r.
We then deﬁne Ge = (Ge , Re , λe ) where E(Ge ) = σ −1 (L(Te ) ∩ L(T )), V (Ge ) = E(Ge ),
Re is the set containing every vertex of G that is an endpoint of an edge in E(Ge ) and
also belongs in a set in {R} ∪ (E(G) \ E(Ge )) (here we treat edges in E(G) \ E(Ge )
as 2-element sets), and λe = ρ|Re . We also set te = |Re | and observe that Ge is a
te -boundaried graph. The width of (T, σ) is max{te | e ∈ E(T )}. The branchwidth of G,
denoted by bw(G), is the minimum width over all branch decompositions of G.
This is an extension of the deﬁnition of a branch decomposition on graphs, given
in [32], to boundaried graphs. Indeed, of G is a graph, then a branch decomposition
of G is a branch decomposition of (G, ∅, ∅). We also deﬁne the branchwidth of G as
bw(G) = bw(G, ∅, ∅).
Lemma 11. Let G = (G, R, λ) be a boundaried graph. Then bw(G) ≤ bw(G) + |R|.
Proof. Let (T ′ , σ ′ ) be a branch decomposition of G′ = (G, ∅, ∅) and let r be the root
of T ′ . Recall that G′e = (G′e , Re′ , λ′e ), e ∈ E(T ′ ). We construct a branch decomposition
(T, σ) of G = (G, R, λ) as follows: we set T = T ′ and σ = (σ ′ \ {(∅, r)}) ∪ {(R, r)}. Note
that Ge = (G′e , Re , λe ), e ∈ E(T ), where Re ⊆ Re′ ∪R. This means that |Re | ≤ |Re′ |+|R|,
therefore bw(G) ≤ bw(G) + |R|.
The following lemma is a combination of the single-exponential linear-time constantfactor approximation of treewidth by Bodlaender et al. [4], with the fact that any graph G
with |E(G)| ≥ 3 satisﬁes that bw(G) ≤ tw(G)+1 ≤ 32 bw(G) [32]; it is worth noting that
from the proofs of these inequalities, simple polynomial-time algorithms for transforming
a branch (resp. tree) decomposition into a tree (resp. branch) decompositions can be
derived.
14

Lemma 12. There exists an algorithm that receives as input a graph G and a w ∈ N
and either reports that bw(G) > w or outputs a branch decomposition (T, σ) of G of
width O(w). Moreover, this algorithm runs in 2O(w) · n steps.
Lemma 13. There exists a function µ : N → N such that for every planar subcubic
collection F, every graph in extm (F) has branchwidth at most y = µ(d) where d = size(F).
Proof. Let G ∈ extm (F) and let F ∈ F be a planar subcubic graph. Since F is subcubic
and F tm G, it follows (see [11]) that F m G, and since F is planar this implies by [31]
that tw(G), hence bw(G) as well, is bounded by a function depending only on F .

3.3

Proof of Theorem 1

We already have all the ingredients to prove Theorem 1.
Proof of Theorem 1. We provide a dynamic programming algorithm for the computation
of tmF (G) for the general case where F is a regular collection. We ﬁrst consider an,
arbitrarily chosen, vertex labeling ρ of G. From Lemma 12, we may assume that we have
a branch decomposition (T, σ) of (G, ∅, ∅) of width O(w), where w = tw(G). This gives
rise to the te -boundaried graphs Ge = (Ge , Re , λe ) for each e ∈ E(T ). Moreover, if r is
the root of T , σ −1 (r) = ∅ = Rer and Ger = (G, ∅, ∅). Keep also in mind that te = O(w)
for every e ∈ E(T ).
(t′ )
For each e ∈ E(T ), we say that (L, C) is an e-pair if L ⊆ Re and C ∈ FFe,d where t′e =
P
(t −i)
te − |L|. We also denote by Pe the set of all e-pairs. Clearly, |Pe | = i∈[0,te ] 2i · |FFe,d |,
O (w log w)

therefore, from Lemma 8, |Pe | = 22 d
.
(e)
We then deﬁne the function tmF : Pe → N such that if (L, C) ∈ Pe , then
(e)

tmF (L, C) = min{|S| | S ⊆ V (Ge ) ∧ L = Re ∩ S ∧ C = folio(Ge \ S, d)} ∪ {∞}.
(0)

(0)

Note that Per = ∅ × FF ,d . Note also that the set AF ,d contains only those that do not
contain some graph in F as a topological minor. Therefore
(0)

(e )

tmF (G) = min{tmF r (∅, C) | C ∈ 2AF ,d }.
(e)

Hence, our aim is to give a way to compute tmF for every e ∈ E(T ). Our dynamic
programming algorithm does this in a bottom-up fashion, starting from the edges that
contain as endpoints leaves of T that are diﬀerent from the root. Let ℓ ∈ L(T ) \ {r}
and let eℓ be the unique edge of T that contains it. Let also σ −1 (eℓ ) = {x, y}. Clearly,
Geℓ = ({x, y}, {{x, y}}) and


(2)
(1)
Peℓ = ({x, y}, A0F ,d ) ∪ ( {x}, {y} × AF ,d ) ∪ ({∅} × AF ,d ).

(e )

As the size of the elements in Peℓ depends only on d, it is possible to compute tmF l in
Od (1) steps.
15

Let e ∈ {er } ∪ E(T \ L(T )), and let e1 and e2 be the two other edges of T that share
an endpoint with e and where each path from them to r contains e. We also set

Fe = Re1 ∪ Re2 \ Re .
(e)

For the dynamic programming algorithm, it is enough to describe how to compute tmF
(e )
given tmF i , i ∈ [1, 2]. For this, given an e-pair (L, C) ∈ Pe it is possible to verify that
 (e )
(e )
(e)
tmF (L, C) = min tmF 1 (L1 , C1 ) + tmF 2 (L2 , C2 ) − |L1 ∩ L2 | |
(Li , Ci ) ∈ Pei , i ∈ [1, 2] ,

Li \ Fe = L ∩ Rei , i ∈ [1, 2] ,
L1 ∩ Fe = L2 ∩ Fe , and


[

folio (B1 ⋄ Z1 ) ⊙ (B2 ⋄ Z2 ) |Z , F, te − |L|
C=
(B1 ,B2 )∈C1 ×C2

where Z = ρ(Re \ L) and Zi = ρ(Rei \ Li ), i ∈ [1, 2] .
(e)

(e )

Note that given tmF i , i ∈ [1, 2] and a (L, B) ∈ Pe , the value of tmF (L, B) can
O (w log w)
be computed by the above formula in O(|Pe1 | · |Pe2 |) = 22 d
steps. As |Pe | =
Od (w log w)
Od (w log w)
(e)
2
2
steps. This
2
, the computation of the function tmF requires again 2
O (w log w)
Od (w·log w)
2
·
· |V (T )| = 22 d
means that the whole dynamic programming requires 2
|E(G)| steps. As |E(G)| = O(tw(G) · |V (G)|), the claimed running time follows.

3.4

Bounding the sets of representatives

We now prove the following result.
Lemma 14. Let t ∈ N and F be a connected and planar collection, where d = size(F),
and let R(F ,t) be a set of representatives. Then |R(F ,t) | = 2Od (t·log t) . Moreover, there
exists an algorithm that given F and t, constructs a set of representatives R(F ,t) in
2Od (t·log t) steps.
Before we proceed with the proof of Lemma 14, we need a series of results. The proof
of the following lemma uses ideas similar to the ones presented by Garnero et al. [17].
Lemma 15. There is a function h2 : N × N → N such that if F is a connected and
planar collection, where d = size(F), t ∈ N, B = (B, R, λ) ∈ R(F ,t) \ {F(F ,t) }, z ∈ N,
and X is a subset of V (B) such that X ∩ R = ∅ and |NB (X)| ≤ z, then |X| ≤ h2 (z, d).
Proof. We set h2 (z, d) = 2h1 (d,µ(d)+z)·(z+µ(d)+1)+ζ(µ(d)+z)−1 + z, where h1 is the function
x
of Lemma 10, µ is the function of Lemma 13, and ζ : N → N such that ζ(x) = 2(2) .
Let y = µ(d), q = h1 (d, y + z) · (x + y + 1) · ζ(y + z), s = h2 (z, d), and observe that
s = 2q−1 + z. Towards a contradiction, we assume that |X| > s.

16

Let B = (B, R, λ) ∈ R(F ,t) \ {F(F ,t) } and let ρ be a vertex-labeling of B where λ ⊆ ρ.
As B 6= F(F ,t) , it follows that
B ∈ extm (F).

(2)

We set G = B[X ∪ NB (X)] and observe that |V (G)| ≥ |X| > s. As G is a subgraph of
B, (2) implies that
G ∈ extm (F),

(3)

and therefore, from Lemma 13, bw(G) ≤ y. Let R′ = NB (X) and λ′ = ρ|R′ . We set
G = (G, R′ , λ′ ). From Lemma 11, bw(G) ≤ bw(G) + |R′ | ≤ y + |R′ | = y + z.
Note now that G has at most |R′ | connected components. Indeed, if it has more, then
one of them, say C, will not intersect |R′ |. This, together with the fact that R ∩ X = ∅,
implies that C is also a connected component of B whose vertex set is disjoint from R,
a contradiction to Lemma 6. We conclude that |E(G)| ≥ |V (G)| − |R′ | ≥ |V (G)| − z >
s − z = 2q−1 .
Let (T, σ) be a branch decomposition of G of width at most y + z. We also consider
the graph Ge = (Ge , Re , λe ), for each e ∈ E(T ) (recall that λe ⊆ ρ). Observe that
∀e ∈ E(T ), |Re | ≤ y + z.

(4)

S
We deﬁne H = {repF (Ge ) | e ∈ E(T )}. From (4), H ⊆ i∈[0,y+z] R(F ,i) . From
Lemma 10, |H| ≤ (y + z + 1) · h1 (d, y + z), therefore q ≥ |H| · ζ(y + z). Let r be
the root of T and let P be a longest path in T that has r as an endpoint. As B has
more than 2q−1 edges, T also has more than 2q−1 leaves diﬀerent from r. This means
that P has more than q edges. Recall that q ≥ |H| · ζ(y + z). As a consequence, there
is a set S ⊆ {Ge | e ∈ E(P )} where |S| > ζ(y + z) and repF (S) contains only one
boundaried graph (i.e., all the boundaried graphs in S have the same F-representative).
From Observation 3, there are two graphs Ge1 , Ge2 ∈ S, e1 6= e2 , such that
Ge1 ≡(F ,t) Ge2 and
Ge1

∼

Ge2 .

(5)
(6)

W.l.o.g., we assume that e1 is in the path in T between r and some endpoint of e2 . This
implies that the underlying graph of Ge1 is a proper subgraph of the underlying graph
of Ge2 , therefore
|E(Ge2 )| < |E(Ge1 )|.

(7)

Recall that Gei = (Gei , Rei , λei ), i ∈ [1, 2]. Let B − = B \ (V (Ge1 ) \ Re1 ) and we set
B− = (B − , Re1 , λe1 ). Clearly, B− ∼ Ge1 . This, combined with (6), implies that
B− ∼ Ge2 .
17

(8)

Let now B ∗ = B− ⊕ Ge2 . Combining (7) and (8), we may deduce that
|E(B ∗ )| < |E(B)|.

(9)

We now set B∗ = (B ∗ , R, λ) and recall that t = |R|. Clearly, both B and B∗ belong in
B (t) .
We now claim that B ≡(F ,t) B∗ . For this, we consider any D = (D, R, λ) ∈ B (t) . We
deﬁne B⋆ = (B − , R, λ), D + = D ⊕ B⋆ , and D+ = (D + , Re1 , λe1 ). Note that
D ⊕ B = D+ ⊕ Ge1

and

D ⊕ B∗ = D+ ⊕ Ge2 .

(10)
(11)

From (5), we have that F tm D+ ⊕Ge1 ⇐⇒ F tm D+ ⊕Ge2 . This, together with (10)
and (11), implies that F tm D ⊕ B ⇐⇒ F tm D ⊕ B∗ , therefore B ≡(F ,t) B∗ , and
the claim follows.
We just proved that B ≡(F ,t) B∗ . This, together with (9), contradict the fact that
B ∈ R(F ,t) . Therefore |X| ≤ s, as required.
Given a graph G and an integer y, we say that a vertex set S ⊆ V (G) is a branchwidthy-modulator if bw(G \ S) ≤ y. This notion is inspired from treewidth-modulators, which
have been recently used in a series of papers (cf., for instance, [5, 16, 17, 22].
The following proposition is a (weaker) restatement of [16, Lemma 3.10 of the full
version] (see also [22]).
Proposition 5. There exists a function f2 : N≥1 × N → N such that if d ∈ N≥1 , y ∈ N,
and G is a graph such that G ∈ extm (Kd ) and G contains a branchwidth-y-modulator
R, then there exists a partition X of V (G) and an element X0 ∈ X such that R ⊆ X0 ,
max{|X0 |, |X | − 1} ≤ 2 · |R|, and for every X ∈ X \ {X0 }, |NG (X)| ≤ f2 (d, y).
Lemma 16. There is a function h3 : N → N such that if t ∈ N and F is a connected
and planar collection, where d = size(F), then every graph in R(t,F ) has at most t · h3 (d)
vertices.
Proof. We deﬁne h3 : N → N so that h3 (d) = 2 + h2 (f2 (d, µ(d)), µ(d)) where h2 is
the function of Lemma 15, f2 is the function of Proposition 5, and µ is the function of
Lemma 13.
As F(F ,t) has at most d vertices, we may assume that G = (G, R, λ) ∈ R(t,F ) \
(F
{F ,t) }. Note that G ∈ extm (F), therefore, from Lemma 13, bw(G) ≤ µ(d). We set
y = µ(d) and we observe that R is a branchwidth-y-modulator of G. Therefore, we can
apply Proposition 5 on G and R and obtain a partition X of V (G) and an element
X0 ∈ X such that
R ⊆ X0 ,

(12)

max{|X0 |, a} ≤ 2 · |R|, and

(13)

∀X ∈ X \ {X0 } : |NG (X)| ≤ f2 (d, y)

(14)

18

From (12) and (14), each X ∈ X \ {X0 } is a subset of V (G) such that X ∩ R = ∅
and |NG (X)| ≤ f2 (d, y). Therefore, from Lemma 15, for each X ∈ X \ {X0 }, |X| ≤
h2 (f2 (d, y), d). We obtain that
X
|G|
=
|X0 | +
|X|
X∈X \{X0 }

≤(13) 2 · |R| + |R| · h2 (f2 (d, y), d)
=

t · (2 + h2 (f2 (d, y), d))

=

t · h3 (d),

as required.
The next proposition follows from the results of Baste et al. [1] on the number of
labeled graphs of bounded treewidth.
Proposition 6 (Baste et al. [1]). Let n, y ∈ N. The number of labeled graphs with at
most n vertices and branchwidth at most q is 2Oq (n·log n) .
Proof of Lemma 14. Before we proceed to the proof we need one more deﬁnition. Given
(t)
(F ,t)
n ∈ N, we set B≤n = AF ,n−t ∪ {F(F ,t) }.
(F ,t)

Note that, from Lemma 16, R(F ,t) ⊆ B≤n , where n = t·h3 (d). Also, from Lemma 13,
(F ,t)

(F ,t)

all graphs in B≤n have branchwidth at most y = max{µ(d), t}. The fact that |B≤n | =
2Od (t·log t) follows easily by applying Proposition 6 for n and y.
The algorithm claimed in the second statement of the lemma constructs a set of
(F ,t)
representatives R(F ,t) as follows: ﬁrst it ﬁnds a partition Q of B≤n into equivalence
classes with respect to ≡(F ,t) and then picks an element with minimum number of edges
from each set of this partition.
(F ,t)
The computation of the above partition of B≤n is based on the fact that, given
(F ,t)

two t-boundaried graphs B1 and B2 , B1 ≡(F ,t) B2 iﬀ for every G ∈ B≤n
F tm
G ⊕ B1 ⇐⇒ F tm G ⊕ B2 . This fact follows directly from Lemma 5 and taking into
(F ,t)
account that R(F ,t) ⊆ B≤n .
(F ,t)

(F ,t)

Note that it takes |B≤n |3 · Od (1) · tO(1) steps to construct Q. As |B≤n | = 2Od (t·log t)
, the construction of Q, and therefore of R(F ,t) as well, can be done in the claimed
number of steps.

3.5

Proof of Theorem 2

We are now ready to prove Theorem 2. The main diﬀerence with respect to the proof of
Theorem 1 is an improvement on the size of the tables of the dynamic programming algorithm, namely |Pe |, where the fact that F is a connected and planar subcubic collection
is exploited.

19

Proof of Theorem 2. We provide a dynamic programming algorithm for the computation
of tmF (G). We ﬁrst consider an, arbitrarily chosen, vertex labeling ρ of G. From
Lemma 12, we may assume that we have a branch decomposition (T, σ) of (G, ∅, ∅) of
width at most w = O(bw(G)) = O(tw(G)). This gives rise to the te -boundaried graphs
Ge = (Ge , Re , λe ) for each e ∈ E(T ). Moreover, if r is the root of T , σ −1 (r) = ∅ = Rer
and Ger = (G, ∅, ∅). Keep also in mind that te = O(w) for every e ∈ E(T ).
Our next step is to deﬁne the tables of the dynamic programming algorithm. Let
e ∈ E(T ). We call the pair (L, B) an e-pair if
1. L ⊆ Re
′

2. B = (B, R, λ) ∈ R(k ,F ) where k′ = |Re \ L| = te − |L|.
For each e ∈ E(T ), we denote by Pe the set of all e-pairs. Note that
X

|Pe | =

2i · |R

(F ,te −i)

|

i∈[0,te ]

= (te + 1) · 2te · 2Od (te ·log te )
Od (w·log w)

= 2

(from Lemma 14)

.

(e)

We then deﬁne the function tmF : Pe → N such that if (L, B) ∈ Pe , then
(e)

tmF (L, B) = min{|S| | S ⊆ V (Ge ) ∧ L = Re ∩ S ∧ B = repF (Ge \ S)} ∪ {∞}.
Note that Per = {(∅, B∅ ), (∅, F(F ,t) )} where B∅ = ((∅, ∅), ∅, ∅). We claim that tmF (G) =
(e )
tmF r (∅, B∅ ). Indeed,
tmF (G) = min{|S| | F 6tm G \ S}

(from Equation (1))

= min{|S| | B∅ = repF ((G \ S, ∅, ∅))}

(from Lemma 7)

= min{|S| | ∅ = ∅ ∩ S ∧ B∅ = repF (G \ S, ∅, ∅)}
= min{|S| | ∅ = Rre ∩ S ∧ B∅ = repF (Ger \ S)}
(e )

= tmF r (∅, B∅ ).
(e)

Therefore, our aim is to give a way to compute tmF for every e ∈ E(T ). Our dynamic
programming algorithm does this in a bottom-up fashion, starting from the edges that
contain as endpoints leaves of T that are diﬀerent to the root. Let l ∈ L(T ) \ {r} and
let eℓ be the edge of T that contains it. Let also σ −1 (eℓ ) = {x, y}. Clearly, Geℓ =
({x, y}, {{x, y}}) and



Peℓ = ( {x, y} × R(0,F ) ) ∪ ( {x}, {y} × R(1,F ) ) ∪ ( ∅ × R(2,F ) ).

(e )

As the size of the elements in Peℓ depends only on F, it is possible to compute tmF l in
Od (1) steps.
20

Let e ∈ {er } ∪ E(T \ L(T )), and let e1 and e2 be the two other edges of T that
share an endpoint
 with e and where each path from them to r contains e. We also set
Fe = Re1 ∪ Re2 \ Re . For the dynamic programming algorithm, it is enough to describe
(e )

(e)

how to compute tmF given tmF i , i ∈ [1, 2].
For this, given an e-pair (L, B) ∈ Pe where B = (B, R, λ), it is possible to verify that
 (e )
(e)
(e )
tmF (L, B) = min tmF 1 (L1 , B1 ) + tmF 2 (L2 , B2 ) − |L1 ∩ L2 | |
(Li , Bi ) ∈ Pei , i ∈ [1, 2],

Li \ Fe = L ∩ Rei , i ∈ [1, 2] ,
L1 ∩ Fe = L2 ∩ Fe , and



B = repF (B1 ⋄ Z1 ) ⊙ (B2 ⋄ Z2 ) |Z , te − |L| where
Z = ρ(Re \ L) and Zi = ρ(Rei \ Li ), i ∈ [1, 2] .
(e)

(e )

Note that given tmF i , i ∈ [1, 2] and a (L, B) ∈ Pe , the value of tmF (L, B) can
be computed by the above formula in O(|Pe1 | · |Pe2 |) = 2Od (w·log w) steps. As |Pe | =
(e)
2Od (w·log w) , the computation of the function tmF requires again 2Od (w·log w) steps. This
means that the whole dynamic programming requires 2Od (w·log w) · |E(T )| = 2Od (w·log w) ·
O(|E(G)|) steps. As |E(G)| = O(bw(G) · |V (G)|), the claimed running time follows.

4

Single-exponential algorithms for hitting paths and cycles

In this section we show that if F ∈ {{P3 }, {P4 }, {C4 }}, then F-TM-Deletion can
also be solved in single-exponential time. It is worth mentioning that the {Ci }-TMDeletion problem has been studied in digraphs from a non-parameterized point of
view [29].
The algorithms we present for {P3 }-TM-Deletion and {P4 }-TM-Deletion use
standard dynamic programming techniques and the algorithm we present for {C4 }-TMDeletion uses the rank-based approach introduced by Bodlaender et al. [2]. We ﬁrst
need a simple observation and to introduce nice tree decompositions, which will be very
helpful in the algorithms.
Observation 4. Let G be a graph and h be a positive integer. Then the following
assertions are equivalent.
• G contains Ph as a topological minor.
• G contains Ph as a minor.
• G contains Ph as a subgraph.
Moreover, the following assertions are also equivalent.
• G contains Ch as a topological minor.
21

• G contains Ch as a minor.
Nice tree decompositions. Let D = (T, X ) be a tree decomposition of G, r be a
vertex of T , and G = {Gt | t ∈ V (T )} be a collection of subgraphs of G, indexed by the
vertices of T . We say that the triple (D, r, G) is a nice tree decomposition of G if the
following conditions hold:
• Xr = ∅ and Gr = G,
• each node of D has at most two children in T ,
• for each leaf t ∈ V (T ), Xt = ∅ and Gt = (∅, ∅). Such t is called a leaf node,
• if t ∈ V (T ) has exactly one child t′ , then either
– Xt = Xt′ ∪ {vinsert } for some vinsert 6∈ Xt′ and Gt = G[V (Gt′ ) ∪ {vinsert }]. The
node t is called introduce vertex node and the vertex vinsert is the insertion
vertex of Xt ,
– Xt = Xt′ \ {vforget } for some vforget ∈ Xt′ and Gt = Gt′ . The node t is called
forget vertex node and vforget is the forget vertex of Xt .
• if t ∈ V (T ) has exactly two children t′ and t′′ , then Xt = Xt′ = Xt′′ , and E(Gt′ ) ∩
E(Gt′′ ) = ∅. The node t is called a join node.
As discussed in [24], given a tree decomposition, it is possible to transform it in
polynomial time to a nice new one of the same width. Moreover, by Bodlaender et al. [4]
we can ﬁnd in time 2O(tw) · n a tree decomposition of width O(tw) of any graph G.
Hence, since in this section we focus on single-exponential algorithms, we may assume
that a nice tree decomposition of width w = O(tw) is given with the input.

4.1

A single-exponential algorithm for {P3 }-TM-Deletion

We ﬁrst give a simple structural characterization of the graphs that exclude P3 as a
topological minor.
Lemma 17. Let G be a graph. P3 6tm G if and only if each vertex of G has degree at
most 1.
Proof. Let G be a graph. If G has a connected component of size at least 3, then clearly
it contains a P3 . This implies that, if P3 6tm G, then each connected component of G
has size at most 2 and so, each vertex of G has degree at most 1. Conversely, if each
vertex of G has degree at most 1, then, as P3 contains a vertex of degree 2, P3 6tm G.
We present an algorithm using classical dynamic programming techniques over a tree
decomposition of the input graph. Let G be an instance of {P3 }-TM-Deletion and let
((T, X ), r, G) be a nice tree decomposition of G.
22

We deﬁne, for each t ∈ V (T ), the set It = {(S, S0 ) | S, S0 ⊆ Xt , S ∩ S0 = ∅} and a
function rt : It → N such that for each (S, S0 ) ∈ It , r(S, S0 ) is the minimum ℓ such that
there exists a set Sb ⊆ V (Gt ), called the witness of (S, S0 ), that satisﬁes:
b ≤ ℓ,
• |S|

• Sb ∩ Xt = S,

b and
• P3 6tm Gt \ S,

• S0 is the set of each vertex of Xt of degree 0 in Gt \ S.
Note that with this deﬁnition, tmF (G) = rr (∅, ∅). For each t ∈ V (T ), we assume
that we have already computed rt′ for each children t′ of t, and we proceed to the
computation of rt . We distinguish several cases depending on the type of node t.
Leaf. It = {(∅, ∅)} and rt (∅, ∅) = 0.
Introduce vertex. If v is the insertion vertex of Xt and t′ is the child of t, then for
each (S, S0 ) ∈ It ,
rt (S, S0 ) = min

{rt′ (S ′ , S0 ) + 1 | (S ′ , S0 ) ∈ It′ , S = S ′ ∪ {v}}
∪ {rt′ (S, S0′ ) | (S, S0′ ) ∈ It′ , S0 = S0′ ∪ {v}, NGt [Xt ] (v) \ S = ∅}
∪ {rt′ (S, S0′ ) | (S, S0′ ) ∈ It′ , S0 = S0′ \ {u}, u ∈ S0′ ,


NGt [Xt ] (v) \ S = {u}} .

Forget vertex. If v is the forget vertex of Xt and t′ is the child of t, then for each
(S, S0 ) ∈ It ,
rt (S, S0 ) = min{rt′ (S ′ , S0′ ) | (S ′ , S0′ ) ∈ It′ , S = S ′ \ {v}, S0 = S0′ \ {v}}
Join. If t′ and t′′ are the children of t, then for each (S, S0 ) ∈ It ,
r(S, S0 ) = min{r(S ′ , S0′ ) + r(S ′′ , S0′′ ) − |S ′ ∩ S ′′ |
| (S ′ , S0′ ) ∈ It′ , (S ′′ , S0′′ ) ∈ It′′ ,
S = S ′ ∪ S ′′ , S0 = S0′ ∩ S0′′ , Xt \ S ⊆ S0′ ∪ S0′′ }.
Let us analize the running time of this algorithm. As, for each t ∈ V (T ), S and S0
are disjoint subsets of Xt , we have that |It | ≤ 3|Xt | . Note that if t is a leaf, then rt can
be computed in time O(1), if t is an introduce vertex or a forget vertex node, and t′ is
the child of t, then rt can be computed in time O(|It′ | · |Xt |), and if t is a join node, and
t′ and t′′ are the two children of t, then rt can be computed in time O(|It′ | · |It′′ | · |Xt |).
We now show that for each t ∈ V (T ), the function rt is correctly computed by the
algorithm.
23

Leaf. This follows directly from the deﬁnition of rt .
Introduce vertex. Let v be the insertion vertex of Xt . As v is the insertion vertex, we
have that NGt [Xt ] (v) = NGt (v), and so for each value we add to the set, we can
ﬁnd a witness of (S, S0 ) of size bounded by this value.
Conversely, let (S, S0 ) ∈ It and let Sb be a witness. If v ∈ S, then (S \ {v}, S0 ) ∈ It′
b
b
and r(S \{v}, S0 ) ≤ |S|−1,
if v ∈ S0 then (S, S0 \{v}) ∈ It′ and r(S, S0 \{v}) ≤ |S|,
b
and if v ∈ Xt \(S ∪ S0 ), then by deﬁnition v has a unique neighbor, say u, in Gt \ S,
b
moreover u ∈ Xt \(S ∪S0 ), v is the unique neighbor of u in Gt \ S, (S, S0 ∪{u}) ∈ It′ ,
b
and r(S, S0 ∪ {u}) ≤ |S|.

Forget vertex. This also follows directly from the deﬁnition of rt .

Join. Let (S ′ , S0′ ) ∈ Rt′ and let (S ′′ , S0′′ ) ∈ It′′ with witnesses Sb′ and Sb′′ , respectively.
If S = S ′ ∪ S ′′ and S0′ ∪ S0′′ = Xt \ S, then the condition Xt \ S ⊆ S0′ ∪ S0′′ ensures
that Gt \ (Sb′ ∪ Sb′′ ) has no vertex of degree at least 2 and so Sb′ ∪ Sb′′ is a witness of
(S, S0′ ∩ S0′′ ) ∈ It of size at most rt′ (S ′ , S0′ ) + rt′ (S ′′ , S0′′ ) − |S ′ ∩ S ′′ |.
b
b If Sb′ = Sb∩V (Gt′ ) and Sb′′ = S∩V
(Gt′′ ),
Conversely, let (S, S0 ) ∈ It with witness S.
′′
′
′
′
b
b
b
then by deﬁnition of S, S is a witness of some (S , S0 ) ∈ It′ , and S is a witness
of some (S ′′ , S0′′ ) ∈ It′′ such that S = S ′ = S ′′ , S0′ ∪ S0′′ = Xt \ S, and S0 = S0′ ∩ S0′′ ,
b
and we have rt′ (S ′ , S0′ ) + rt′ (S ′′ , S0′′ ) − |S| ≤ |S|.
The following theorem summarizes the above discussion.

Theorem 7. If a nice tree decomposition of G of width w is given, {P3 }-TM-Deletion
can be solved in time O(9w · w · n).

4.2

A single-exponential algorithm for {P4 }-TM-Deletion

Similarly to what we did for {P3 }-TM-Deletion, we start with a structural deﬁnition
of the graphs that exclude P4 as a topological minor.
Lemma 18. Let G be a graph. P4 6tm G if and only if each connected component of G
is either a C3 or a star.
Proof. First note that if each connected component of G is either a C3 or a star, then
P4 6tm G. Conversely, assume that P4 6tm G. Then each connected component of G of
size at least 4 should contain at most 1 vertex of degree at least 2, hence such component
is a star. On the other hand, the only graph on at most 3 vertices that is not a star is
C3 . The lemma follows.
As we did for {P3 }-TM-Deletion, we present an algorithm using classical dynamic
programming techniques over a tree decomposition of the input graph. Let G be an
instance of {P4 }-Deletion, and let ((T, X ), r, G) be a nice tree decomposition of G.

24

We deﬁne, for each t ∈ T , the set It to be the set of each tuple (S, S1+ , S1− , S∗ , S3+ , S3− )
such that {S, S1+ , S1− , S∗ , S3+ , S3− } is a partition of Xt and the function rt : It → N
such that, for each (S, S1+ , S1− , S∗ , S3+ , S3− ) ∈ It , rt (S, S1+ , S1− , S∗ , S3+ , S3− ) is the
b Sb∗ , Sb3− ) ⊆ V (Gt ) × V (Gt ) × V (Gt ), called
minimum ℓ such that there exists a triple (S,
the witness of (S, S1+ , S1− , S∗ , S3+ , S3− ), which satisﬁes the following properties:
b Sb∗ , and Sb3− are pairwise disjoint,
• S,

• Sb ∩ Xt = S, Sb∗ ∩ Xt = S∗ , and Sb3− ∩ Xt = S3− ,

b ≤ ℓ,
• |S|

b
• P4 6tm Gt \ S,

b
• S1+ is a set of vertices of degree 0 in Gt \ S,

• each vertex of S1− has a unique neighbor in Gt \ Sb and this neighbor is in Sb∗ ,

• each connected component of Gt [Sb3− ] is a C3 ,

• there is no edge in Gt \ Sb between a vertex of Sb3− and a vertex of V (Gt )\(Sb ∪ Sb3− ),

• there is no edge in Gt \ Sb between a vertex of S3+ and a vertex of V (Gt )\(Sb ∪ S3+ ),
and
• there is no edge in Gt \ Sb between two vertices of S∗ .

Intuitively, Sb corresponds to a partial solution in Gt . Note that, by Lemma 18, each
component of Gt \ Sb must be either a star or a C3 . With this in mind, Sb∗ is the set of
b S1+ is the set of leaves of a star that are
vertices that are centers of a star in Gt \ S,
b
not yet connected to a vertex of S∗ , S1− is the set of leaves of a star that are already
connected to a vertex of Sb∗ , Sb3− is the set of vertices that induce C3 ’s in Gt , and S3+ is
a set of vertices that will induce C3 ’s when further edges will appear.
Note that with this deﬁnition, tmF (G) = rr (∅, ∅, ∅, ∅, ∅, ∅). For each t ∈ V (T ), we
assume that we have already computed rt′ for each children t′ of t, and we proceed to
the computation of rt . We distinguish several cases depending on the type of node t.
Leaf. It = {(∅, ∅, ∅, ∅, ∅, ∅)} and rt (∅, ∅, ∅, ∅, ∅, ∅) = 0.
Introduce vertex. If v is the insertion vertex of Xt and t′ is the child of t, then, for

25

each (S, S1+ , S1− , S∗ , S3+ , S3− ) ∈ It ,
rt (S, S1+ , S1− , S∗ , S3+ , S3− ) = min

{rt′ (S ′ , S1+ , S1− , S∗ , S3+ , S3− ) + 1

| (S ′ , S1+ , S1− , S∗ , S3+ , S3− ) ∈ Rt′ , S = S ′ ∪ {v}}
′
, S1− , S∗ , S3+ , S3− )
∪ {rt′ (S, S1+
′
| (S, S1+
, S1− , S∗ , S3+ , S3− ) ∈ Rt′ ,
′
S1+ = S1+
∪ {v}, NGt [Xt \S] (v) = ∅}
′
, S∗ , S3+ , S3− )
∪ {rt′ (S, S1+ , S1−
′
| (S, S1+ , S1−
, S∗ , S3+ , S3− ) ∈ Rt′ ,
′
S1− = S1−
∪ {v}, z ∈ S∗ , NGt [Xt \S] (v) = {z}}
′
′
, S1−
, S∗′ , S3+ , S3− )
∪ {rt′ (S, S1+
′
′
, S∗′ , S3+ , S3− ) ∈ Rt′ ,
, S1−
| (S, S1+
′
,
S∗ = S∗′ ∪ {v}, NGt [Xt \S] (v) ⊆ S1+
′
′
\ NGt [Xt \S] (v), S1− = S1−
∪ NGt [Xt \S] (v)}
S1+ = S1+
′
, S3− )
∪ {rt′ (S, S1+ , S1− , S∗ , S3+
′
| (S, S1+ , S1− , S∗ , S3+
, S3− ) ∈ Rt′ ,
′
∪ {v},
S3+ = S3+

[NGt [Xt \S ′ ] (v) = ∅] or
′
[z ∈ S3+
, NGt [Xt \S] (v) = {z}, NGt [Xt \S] (z) = {v}]}
′
′
, S3−
)
∪ {rt′ (S, S1+ , S1− , S∗ , S3+
′
| (S, S1+ , S1− , S∗ , S3+
, S3− ) ∈ Rt′ ,
′
′
S3+ = S3+
\ {z, z ′ }, S3− = S3−
∪ {z, z ′ , v},
′
z, z ′ ∈ S3+
, NGt [Xt \S] (v) = {z, z ′ },

NGt [Xt \S] (z) = {v, z ′ }, NGt [Xt \S] (z ′ ) = {v, z}}

Forget vertex. If v is the forget vertex of Xt and t′ is the child of t, then,
for each (S, S1+ , S1− , S∗ , S3+ , S3− ) ∈ It ,
′
′
, S∗′ , S3+ , S3−
)
rt (S, S1+ , S1− , S∗ , S3+ , S3− ) = min{rt′ (S ′ , S1+ , S1−
′
′
| (S ′ , S1+ , S1−
, S∗′ , S3+ , S3−
) ∈ It′ ,
′
S = S ′ \ {v}, S1− = S1−
\ {v},
′
S∗ = S∗′ \ {v}, S3− = S3−
\ {v}}.

Join. If t′ and t′′ are the children of t, then for each (S, S1+ , S1− , S∗ , S3+ , S3− ) ∈ It ,

26



.

rt (S, S1+ , S1− , S∗ , S3+ , S3− ) is
′
′
′
′
′
′
′
′
, S1−
, S∗ , S3+
, S3−
) − |S|
, S1−
, S∗ , S3+
, S3−
) + rt′ (S, S1+
min{rt′ (S, S1+
′′
′′
′′
′′
′
′
′
′
, S1−
, S∗ , S3+
, S3−
) ∈ It′′ ,
| (S, S1+
, S1−
, S∗ , S3+
, S3−
) ∈ It′ , (S, S1+
′
′
′′
′′
′′
′′
′
′
(S1+
∪ S1−
) ∩ (S3+
∪ S3−
) = (S1+
∪ S1−
) ∩ (S3+
∪ S3−
) = ∅,
′
′′
∀v ∈ S1−
∩ S1−
, ∃z ∈ S∗ : NGt [Xt \S] (v) = {z},
′
′′
′
′′
∀v ∈ S3−
∩ S3−
, ∃z, z ′ ∈ S3−
∩ S3−
: v, z, z ′ induce a C3 in Gt [Xt \ S]}.

Let us analyze the running time of this algorithm. As, for each t ∈ V (T ), S, S1+ ,
S1− , S∗ , S3+ , and S3− form a partition of Xt , we have that |It | ≤ 6|Xt | . Note that if t
is a leaf, then rt can be computed in time O(1), if t is an introduce vertex or a forget
vertex node, and t′ is the child of t, then rt can be computed in time O(|It′ | · |Xt |), and
if t is a join node, and t′ and t′′ are the two children of t, then rt can be computed in
time O(|It′ | · |It′′ | · |Xt |).
We now show that for each t ∈ V (T ), rt is correctly computed by the algorithm.
For each (S, S1+ , S1− , S∗ , S3+ , S3− ) ∈ It , it can be easily checked that each value ℓ we
compute respects, rt (S, S1+ , S1− , S∗ , S3+ , S3− ) ≤ ℓ. Conversely, we now argue that for
each (S, S1+ , S1− , S∗ , S3+ , S3− ) ∈ It , the computed value ℓ is such that for any witness
b Sb∗ , Sb3− ) of (S, S1+ , S1− , S∗ , S3+ , S3− ) is such that ℓ ≤ |S|.
b We again distinguish the
(S,
type of node t.
Leaf. This follows directly from the deﬁnition of rt .
Introduce vertex. Let v be the insertion vertex of Xt , let (S, S1+ , S1− , S∗ , S3+ , S3− ) ∈
b Sb∗ , Sb3− ) be a witness.
Rt , and let (S,

• If v ∈ S, then (S \ {v}, S1+ , S1− , S∗ , S3+ , S3− ) ∈ It′ and
b − 1.
rt′ (S \ {v}, S1+ , S1− , S∗ , S3+ , S3− ) ≤ |S|
b hence (S, S1+ \{v}, S1− , S∗ , S3+ , S3− ) ∈
• If v ∈ S1+ , then v is of degree 0 in Gt \S,
b
It′ and rt′ (S, S1+ \ {v}, S1− , S∗ , S3+ , S3− ) ≤ |S|.
• If v ∈ S1− , then v has a unique neighbor that is in Sb∗ . As v is the insertion vertex of Xt , it implies that NGt (v) ⊆ S∗ , and so (S, S1+ , S1− \
b
{v}, S∗ , S3+ , S3− ) ∈ It′ and rt′ (S, S1+ , S1− \ {v}, S∗ , S3+ , S3− ) ≤ |S|.
b
• If v ∈ S∗ , then every neighbor of v is in S1− and has degree 1 in Gt \ S.
Thus, (S, S1+ ∪ NGt [Xt \S] (v), S1− \ NGt [Xt \S] (v), S∗ \ {v}, S3+ , S3− ) ∈ It′ and
b
rt′ (S, S1+ ∪ NG [X \S] (v), S1− \ NG [X \S] (v), S∗ \ {v}, S3+ , S3− ) ≤ |S|.
t

t

t

t

• If v ∈ S3+ , then (S, S1+ , S1− , S∗ , S3+ \ {v}, S3− ) ∈ It′ and
b
rt′ (S, S1+ , S1− , S∗ , S3+ \ {v}, S3− ) ≤ |S|.
• If v ∈ S3− , then there exist z and z ′ in S3− such that {v, z, z ′ } induce a C3 in
Gt \ Sb and there is no edge in Gt \ Sb between a vertex of {v, z, z ′ } and a vertex
b \ {x, z, z ′ }. So (S, S1+ , S1− , S∗ , S3+ ∪ {z, z ′ }, S3− \ {x, z, z ′ }) ∈ It′
of V (Gt \ S)
b
and rt′ (S, S1+ , S1− , S∗ , S3+ ∪ {z, z ′ }, S3− \ {x, z, z ′ }) ≤ |S|.
27

Forget vertex. Let v be the forget vertex of Xt , let (S, S1+ , S1− , S∗ , S3+ , S3− ) ∈ It ,
b Sb∗ , Sb3− ) be a witness. If v has degree 0 in Gt \ S,
b then (S, S1+ , S1− , S∗ ∪
and let (S,
b If v has degree
{v}, S3+ , S3− ) ∈ It′ and rt′ (S, S1+ , S1− , S∗ ∪ {v}, S3+ , S3− ) ≤ |S|.
b
at least 1 in Gt \ S, then NGt \Sb(v) ∩ S3+ = ∅, as otherwise there would be an edge
in Gt \ Sb between a vertex of S3+ and a vertex of V (Gt ) \ (Sb ∪ S3+ ). So, one of
the following case occurs:
b (S ∪ {v}, S1+ , S1− , S∗ , S3+ , S3− ) ∈ It′ , and
• v ∈ S,
b
′
rt (S ∪ {v}, S1+ , S1− , S∗ , S3+ , S3− ) ≤ |S|,
• v ∈ Sb∗ , (S, S1+ , S1− , S∗ ∪ {v}, S3+ , S3− ) ∈ It′ , and
b
rt′ (S, S1+ , S1− , S∗ ∪ {v}, S3+ , S3− ) ≤ |S|,

• NGt \Sb(v) ⊆ Sb∗ , (S, S1+ , S1− ∪ {v}, S∗ , S3+ , S3− ) ∈ It′ , and
b or
rt′ (S, S1+ , S1− ∪ {v}, S∗ , S3+ , S3− ) ≤ |S|,

• v ∈ Sb3− , (S, S1+ , S1− , S∗ , S3+ , S3− ∪ {v}) ∈ It′ , and
b
rt′ (S, S1+ , S1− , S∗ , S3+ , S3− ∪ {v}) ≤ |S|

b Sb∗ , Sb3− ) be a witness. Let t′ and
Join. Let (S, S1+ , S1− , S∗ , S3+ , S3− ) ∈ It , and let (S,
′′
′
b
b
t be the two children of t. We deﬁne S = S ∩ V (Gt′ ), Sb′′ = Sb ∩ V (Gt′′ ), Sb∗′ = Sb∗ ∩
′ ⊆S
b3− ∩V (Gt′ ), and Sb′′ ⊆ Sb3− ∩V (Gt′′ ), such that
V (Gt′ ), Sb∗′′ = Sb∗ ∩V (Gt′′ ), Sb3−
3−
′′ ]) is a C and G ′ \ (S
′ ] (resp. G [S
b′ ∪ Sb′ )
b
each connected component of Gt [Sb3−
3
t 3−
t
3−
′′ )) is a forest). Then we deﬁne
(resp. Gt′′ \ (Sb′′ ∪ Sb3−
• S ′ = Sb′ ∩ Xt ,

′ =S
b′
• S1+
1+ ∪ {v ∈ S1− | NGt \Sb(v) 6⊆ S∗ },

′ = {v ∈ S
b′
• S1−
1− | NGt \Sb(v) ⊆ S∗ },

• S∗′ = S∗ ∩ V (Gt′ ),
• S ′ = Sb′ ∩ Xt , and
•

3−
′
S3+

3−

′ ).
= S3+ ∪ (S3− \ S3−

′ , S ′ , S ′ , S ′ , S ′ ) ∈ I ′ . We deﬁne (S ′′ , S ′′ , S ′′ , S ′′ , S ′′ , S ′′ ) ∈
Note that (S ′ , S1+
∗
t
∗
3+
3−
1+
1−
3+
3−
1−
It′′ similarly. Moreover we can easily check that

• S = S ′ = S ′′ , S∗ = S∗′ = S∗′′ ,
′ ∪ S ′ ) ∩ (S ′′ ∪ S ′′ ) = (S ′′ ∪ S ′′ ) ∩ (S ′ ∪ S ′ ) = ∅,
• (S1+
3−
3+
1−
1+
3−
3+
1−
′ ∩ S ′′ , ∃z ∈ S : N
• ∀v ∈ S1−
∗
Gt [Xt \S] (v) = {z},
1−
′ ∩ S ′′ , ∃z, z ′ ∈ S ′ ∩ S ′′ : v, z, z ′ induce a C in G [X \ S],
• ∀v ∈ S3−
3
t
t
3−
3−
3−
′ ∩ S ′′ , S ′ ∪ S ′′ , S , S ′ ∩ S ′′ , S ′ ∪
• (S, S1+ , S1− , S∗ , S3+ , S3− ) = (S, S1+
∗
1+
1−
1−
3+
3+
3−
′′
S3− ), and
′ , S ′ , S ′ , S ′ , S ′ ) + r ′′ (S ′′ , S ′′ , S ′′ , S ′′ , S ′′ , S ′′ ) − |S| ≤ |S|.
b
• rt′ (S ′ , S1+
t
∗
∗
3−
3+
1−
1+
3−
3+
1−

28

This concludes the proof of correctness of the algorithm. The following theorem
summarizes the above discussion.
Theorem 8. If a nice tree decomposition of G of width w is given, {P4 }-Deletion can
be solved in time O(36w · w · n).

4.3

A single-exponential algorithm for {C4 }-TM-Deletion

As discussed before, in this subsection we use the dynamic programming techniques
introduced by Bodlaender et al. [2] to obtain a single-exponential algorithm for {C4 }TM-Deletion. The algorithm we present solves the decision version of {C4 }-TMDeletion: the input is a pair (G, k), where G is a graph and k is an integer, and the
output is the boolean value tmF (G) ≤ k.
We give some deﬁnitions that will be used in this section. Given a graph G, we
denote by n(G) = |V (G)|, m(G) = |E(G)|, c3 (G) the number of C3 ’s that are subgraphs
of G, and cc(G) the number of connected components of G. We say that G satisﬁes the
C4 -condition if the following conditions hold:
• G does not contain the diamond as a subgraph, and
• n(G) − m(G) + c3 (G) = cc(G).
As in the case of P3 and P4 , we state in Lemma 20 a structural characterization of
the graphs that exclude C4 as a (topological) minor. We ﬁrst need an auxiliary lemma.
Lemma 19. Let n0 be a positive integer. Assume that for each graph G′ such that
1 ≤ n(G′ ) ≤ n0 , C4 6tm G′ if and only if G satisfies the C4 -condition. If G is a
graph that does not contain a diamond as a subgraph and such that n(G) = n0 , then
n(G) − m(G) + c3 (G) ≤ cc(G).
Proof. Let n0 be a positive integer, and assume that for each graph G′ such that 1 ≤
n(G′ ) ≤ n0 , C4 6tm G′ if and only if G satisﬁes the C4 -condition. Let G be a graph that
does not contain a diamond as a subgraph and such that n(G) = n0 . Let S ⊆ E(G)
such that C4 6tm G \ S and cc(G \ S) = cc(G) (note that any minimal feedback edge set
satisﬁes these conditions). We have, by hypothesis, that G \ S satisﬁes the C4 -condition,
so n(G \ S) − m(G \ S) + c3 (G \ S) = cc(G \ S). Moreover, as G does not contain
a diamond as a subgraph, each edge of G participates in at most one C3 , and thus
c3 (G) − c3 (G \ S) ≤ |S|. As by deﬁnition n(G) = n(G \ S) and m(G) − m(G \ S) = |S|,
we obtain that n(G) − m(G) + c3 (G) ≤ cc(G \ S) = cc(G).
Lemma 20. Let G be a non-empty graph. C4 6tm G if and only if G satisfies the
C4 -condition.
Proof. Let G be a non-empty graph, and assume ﬁrst that C4 6tm G. This directly
implies that G does not contain the diamond as a subgraph. In particular, any two
cycles of G, which are necessarily C3 ’s, cannot share an edge. Let S be a set containing
29

an arbitrary edge of each C3 in G. By construction, G \ S is a forest. As in a forest
F , we have n(F ) − m(F ) = cc(F ), and S is deﬁned such that |S| = c3 (G) because each
edge of G participates in at most one C3 , we obtain that n(G) − m(G) + c3 (G) = cc(G).
Thus, G satisﬁes the C4 -condition.
Conversely, assume now that G satisﬁes the C4 -condition. We prove that C4 6tm G
by induction on n(G). If n(G) ≤ 3, then n(G) < n(C4 ) and so C4 6tm G. Assume now
that n(G) ≥ 4, and that for each graph G′ such that 1 ≤ n(G′ ) < n(G), if G′ satisﬁes
the C4 -condition, then C4 6tm G′ . We prove that this last implication is also true for G.
Note that, as two C3 cannot share an edge in G, we have that c3 (G) ≤ m(G)
3 . This implies
that the minimum degree of G is at most 3. Indeed, if each vertex of G had degree at least
4, then m(G) ≥ 2n(G), which together with the relations n(G) − m(G) + c3 (G) = cc(G)
and c3 (G) ≤ m(G)
would imply that cc(G) < 0, a contradiction. Let v ∈ V (G) be a
3
vertex with minimum degree. We distinguish two cases according to the degree of v.
If v has degree 0 or 1, then the graph G \ {v} satisﬁes the C4 -condition as well,
implying that C4 6tm G \ {v}. As v has degree at most 1, it cannot be inside a cycle,
hence C4 6tm G.
Assume that v has degree 2 and participates in a C3 . As G does not contain a diamond
as a subgraph, C4 tm G if and only if C4 tm G \ {v}. Moreover n(G \ {v}) = n(G) − 1,
m(G \ {v}) = m(G) − 2, c3 (G \ {v}) = c3 (G) − 1, and cc(G \ {v}) = cc(G). This implies
that G \ {v} satisﬁes the C4 -condition, hence C4 6tm G \ {v}, and therefore C4 6tm G.
Finally, assume that v has degree 2 and does not belong to any C3 . Using the
induction hypothesis and Lemma 19, we have that n(G\{v})−m(G\{v})+c3 (G\{v}) ≤
cc(G\{v}). As n(G\{v}) = n(G)−1, m(G\{v}) = m(G)−2, c3 (G\{v}) = c3 (G), v has
degree 2 in G, and G satisﬁes the C4 -condition, we obtain that cc(G \ {v}) = cc(G) − 1.
This implies that G \ {v} satisﬁes the C4 -condition, and thus C4 6tm G \ {v}. Since v
disconnects one of the connected components of G it cannot participate in a cycle of G,
hence C4 6tm G.
Lemma 21. If G is a non-empty graph such that C4 6tm G, then m(G) ≤ 32 (n(G) − 1).
Proof. As C4 6tm G, by Lemma 20 G satisﬁes the C4 -condition. It follows that c3 (G) ≤
1
3 m(G). Moreover, as G is non-empty, we have that 1 ≤ cc(G). The lemma follows by
using these inequalities in the equality n(G) − m(G) + c3 (G) = cc(G).
We are now going to restate the tools introduced by Bodlaender et al. [2] that we
need for our purposes.
Let U be a set. We deﬁne Π(U ) to be the set of all partitions of U . Given two
partitions p and q of U , we deﬁne the coarsening relation ⊑ such that p ⊑ q if for each
S ∈ q, there exists S ′ ∈ p such that S ⊆ S ′ . (Π(U ), ⊑) deﬁnes a lattice with minimum
element {{U }} and maximum element {{x} | x ∈ U }. On this lattice, we denote by ⊓
the meet operation and by ⊔ the join operation.
Let p ∈ Π(U ). For X ⊆ U we denote by p↓X = {S ∩ X | S ∈ p, S ∩ X 6= ∅} ∈ Π(X)
the partition obtained by removing all elements not in X from p, and analogously for
U ⊆ X we denote p↑X = p ∪ {{x} | x ∈ X \ U } ∈ Π(X) the partition obtained by adding
30

to p a singleton for each element in X \ U . Given a subset S of U , we deﬁne the partition
U [S] = {{x} | x ∈ U \ S} ∪ {S}.
A set of weighted partitions is a set A ⊆ Π(U )×N. We also deﬁne rmc(A) = {(p, w) ∈
A | ∀(p′ , w′ ) ∈ A : p′ = p ⇒ w ≤ w′ }.
We now deﬁne some operations on weighted partitions. Let U be a set and A ⊆
Π(U ) × N.
↓ B = rmc(A ∪ B).
Union. Given B ⊆ Π(U ) × N, we deﬁne A ∪

Insert. Given a set X such that X ∩U = ∅, we deﬁne ins(X, A) = {(p↑U ∪X , w) | (p, w) ∈
A}.
Shift. Given w′ ∈ N, we deﬁne shft(w′ , A) = {(p, w + w′ ) | (p, w) ∈ A}.
Glue. Given a set S, we deﬁne Û = U ∪ S and glue(S, A) ⊆ Π(Û ) × N as
glue(S, A) = rmc({(Û [S] ⊓ p↑Û , w | (p, w) ∈ A}).
Given w : Û × Û → N , we deﬁne gluew ({u, v}, A) = shft(w(u, v), glue({u, v}, A)).
Project. Given X ⊆ U , we deﬁne X = U \ X and proj(X, A) ⊆ Π(X) × N as
proj(X, A) = rmc({(p↓X , w) | (p, w) ∈ A, ∀e ∈ X : ∀e′ ∈ X : p ⊑ U [ee′ ]}).
Join. Given a set U ′ , B ⊆ Π(U ) × N, and Û = U ∪ U ′ , we deﬁne join(A, B) ⊆ Π(Û ) × N
as
join(A, B) = rmc({(p↑Û ⊓ q↑Û , w1 + w2 ) | (p, w1 ) ∈ A, (q, w2 ) ∈ B}).
Proposition 9 (Bodlaender et al. [2]). Each of the operations union, insert, shift, glue,
and project can be carried out in time s · |U |O(1) , where s is the size of the input of the
operation. Given two weighted partitions A and B, join(A, B) can be computed in time
|A| · |B| · |U |O(1) .
Given a weighted partition A ⊆ Π(U ) × N and a partition q ∈ Π(U ), we deﬁne
opt(q, A) = min{w | (p, w) ∈ A, p ⊓ q = {U }}. Given two weighted partitions A, A′ ⊆
Π(U ) × N, we say that A represents A′ if for each q ∈ Π(U ), opt(q, A) = opt(q, A′ ).
Given a set Z and a function f : 2Π(U )×N × Z → 2Π(U )×N , we say that f preserves
representation if for each two weighted partitions A, A′ ⊆ Π(U ) × N and each z ∈ Z, it
holds that if A′ represents A then f (A′ , z) represents f (A, z).
Proposition 10 (Bodlaender et al. [2]). The union, insert, shift, glue, project, and join
operations preserve representation.
Theorem 11 (Bodlaender et al. [2]). There exists an algorithm reduce that, given a set
of weighted partitions A ⊆ Π(U ) × N, outputs in time |A| · 2(ω−1)|U | · |U |O(1) a set of
weighted partitions A′ ⊆ A such that A′ represents A and |A′ | ≤ 2|U | , where ω denotes
the matrix multiplication exponent.

31

We now have all the tools needed to describe our algorithm. Let G be a graph and
k be an integer. We recall that the algorithm we describe solves the decision version of
{C4 }-TM-Deletion. This algorithm is based on the one given in [2, Section 3.5] for
Feedback Vertex Set.
We deﬁne a new graph G0 = (V (G) ∪ {v0 }, E(G) ∪ E0 ), where v0 is a new vertex and
E0 = {{v0 , v} | v ∈ V (G)}. The role of v0 is to artiﬁcially guarantee the connectivity of
the solution graph, so that the machinery of Bodlaender et al. [2] can be applied. In the
following, for each subgraph H of G, for each Z ⊆ V (H), and
for each Z0 ⊆ E0 ∩ E(H),
Z\{v0 }
we denote by HhZ, Z0 i the graph Z, Z0 ∪ E(H) ∩
.
2
Given a nice tree decomposition of G of width w, we deﬁne a nice tree decomposition
((T, X ), r, G) of G0 of width w + 1 such that the only empty bags are the root and the
leaves and for each t ∈ T , if Xt 6= ∅ then v0 ∈ Xt . Note that this can be done in linear
time. For each bag t, each integers i, j, and ℓ, each function s : Xt → {0, 1}, each function
s0 : {v0 } × s−1 (1) → {0, 1}, and each function r : E(Gt s−1 (1), s−1
0 (1) ) → {0, 1}, if
C4 6tm Gt s−1 (1), s−1
(1)
,
we
deﬁne:
0
Et (p, s, s0 , r, i, j, ℓ) = {(Z, Z0 ) | (Z, Z0 ) ∈ 2Vt × 2E0 ∩E(Gt )
|Z| = i, |E(Gt hZ, Z0 i)| = j, c3 (Gt hZ, Z0 i) = ℓ,
Gt hZ, Z0 i does not contain the diamond as a subgraph,
Z ∩ Xt = s−1 (1), Z0 ∩ (Xt × Xt ) = s−1
0 (1),
v0 ∈ Xt ⇒ s(v0 ) = 1,
∀u ∈ Z \ Xt : either t is the root or
∃u′ ∈ s−1 (1) : u and u′ are connected in Gt hZ, Z0 i,
∀v1 , v2 ∈ s−1 (1) : p ⊑ Vt [{v1 , v2 }] ⇔ v1 and v2 are con-

∀e ∈ E(Gt hZ, Z0 i) ∩



s−1 (1)
2



nected in Gt hZ, Z0 i,
: r(e) = 1 ⇔ e is an edge
of a C3 in Gt hZ, Z0 i}

At (s, s0 , r, i, j, ℓ) = {p | p ∈ Π(s−1 (1)), Et (p, s, s0 , r, i, j, ℓ) 6= ∅}.
Otherwise, i.e., if C4 tm Gt s−1 (1), s−1
0 (1) , we deﬁne
At (s, s0 , r, i, j, ℓ) = ∅.
Note that we do not need to keep track of partial solutions if C4 tm Gt s−1 (1), s−1
0 (1) ,
as we already know they will not lead to a global solution. Moreover, if C4 6tm
−1
−1
3
−1
−1
Gt s−1 (1), s−1
0 (1) , then by Lemma 21 m(Gt s (1), s0 (1) ) ≤ 2 (n(Gt s (1), s0 (1) )−
1).
32

Using the deﬁnition of Ar , Lemma 20, and Lemma 21 we have that tm{C4 } (G) ≤
k if and only if for some i ≥ |V (G) ∪ {v0 }| − k and some j ≤ 23 (i − 1), we have
Ar (∅, ∅, ∅, i, j, 1 + j − i) 6= ∅. For each t ∈ V (T ), we assume that we have already
computed At′ for each children t′ of t, and we proceed to the computation of At . As
usual, we distinguish several cases depending on the type of node t.
Leaf. By deﬁnition of At we have At (∅, ∅, ∅, 0, 0, 0) = {∅}.
Introduce vertex. Let v be the insertion vertex of Xt , let t′ be the child of t, let s, s0 ,
and r the functions deﬁned as before, let H = Gt s−1 (1), s−1
0 (1) , and let d3 be
the number of C3 ’s of H that contain the vertex v.
• If C4 tm H or if v = v0 and s(v0 ) = 0, then by deﬁnition of At we have that
At (s, s0 , r, i, j, ℓ) = ∅.
• Otherwise, if s(v) = 0, then, by deﬁnition of At , it holds that At (s, s0 , r, i, j, ℓ) =
At′ (s|Xt′ , s0 |Et′ , r|Et′ , i, j, ℓ).
• Otherwise, if v = v0 , then by construction of the nice tree decomposition, we
know that t′ is a leaf of T and so s = {(v0 , 1)}, s0 = r = ∅, j = ℓ = i − 1 = 0
and At (s, s0 , r, i, j, ℓ) = ins({v0 }, At′ (∅, ∅, ∅, 0, 0, 0)).
• Otherwise, we know that v 6= v0 , s(v) = 1, and C4 6tm H. As s(v) = 1, we
have to insert v and we have to make sure that all vertices of NH [v] are in the
same connected component of H. Moreover, by adding v we add one vertex,
|N (v)| edges, and d3 C3 ’s. Therefore, we have that
At (s, s0 , r, i, j, ℓ) =
glue(NH [v], ins({v}, At′ (s|Xt′ , s0 |Et′ , r|Et′ , i − 1, j − |NH (v)|, ℓ − d3 ))).
Forget vertex. Let v be the forget vertex of Xt , let t′ be the child of t, and let s, s0 ,
and r the functions deﬁned as before. For each function, we have a choice on how
it can be extended in t′ , and we potentially need to consider every possible such
extension. Note the number of vertices, edges, or C3 ’s is not aﬀected. We obtain
that
At (s, s0 , r, i, j, ℓ) = At′ (s ∪ {(v, 0)}, s0 , r, i, j, ℓ)
S
↓

proj({v}, At′ (s′ , s′0 , r′ , i, j, ℓ)).

s′ :Xt′ →{0,1}, s′ |Xt =s, s′ (v)=1

s′0 :{v0 }×s′−1 (1)→{0,1}, s′0 |Xt =s0
′
r′ :E(Gths′−1 (1),s′−1
0 (1)i )→{0,1}, r |Xt =r

Join. Let t′ and t′′ be the two children of t, let s, s0 , and r be the functions deﬁned
as before, let H = Gt s−1 (1), s−1
0 (1) , and let S ⊆ E(H) be the set of edges that
participate in a C3 of H.
33

We join every compatible entries At′ (s′ , s′0 , r′ , i′ , j ′ , ℓ′ ) and At′′ (s′′ , s′′0 , r′′ , i′′ , j ′′ , ℓ′′ ).
For two such entries being compatible, we need s′ = s′′ = s and s′0 = s′′0 = s0 .
Moreover, we do not want the solution graph to contain a diamond as a subgraph,
and for this we need r′−1 (1) ∩ r′′−1 (1) = S. Indeed, either H contains the diamond
as a subgraph, and then At′ (s′ , s′0 , r′ , i′ , j ′ , ℓ′ ) = At′′ (s′′ , s′′0 , r′′ , i′′ , j ′′ , ℓ′′ ) = {∅}, or
the diamond is created by joining two C3 ’s, one from t′ and the other one from t′′ ,
sharing a common edge. This is possible only if (r′−1 (1) ∩ r′′−1 (1)) \ S 6= ∅. For
the counters, we have to be careful in order not to count some element twice. We
obtain that
S
↓
join(At′ (s, s0 , r′ , i′ , j ′ , ℓ′ ), At′′ (s, s0 , r′′ , i′′ , j ′′ , ℓ′′ )).
At (s, s0 , r, i, j, ℓ) =
r′ ,r′′ :E(H)→{0,1},
r′−1 (1)∩r′′−1 (1)=S
i′ +i′′ =i+|V (H)|
j ′ +j ′′ =j+|E(H)|
ℓ′ +ℓ′′ =ℓ+c3 (H)

Theorem 12. {C4 }-TM-Deletion can be solved in time 2O(tw) · n7 .
Proof. The algorithm works in the following way. For each node t ∈ V (T ) and for
each entry M of its table, instead of storing At (M ), we store A′t (M ) = reduce(At (M ))
by using Theorem 11. As each of the operation we use preserves representation by
Proposition 10, we obtain that for each node t ∈ V (T ) and for each possible entry M ,
A′t (M ) represents At (M ). In particular, we have that A′r (M ) = reduce(Ar (M )) for each
possible entry M . Using the deﬁnition of Ar , Lemma 20, and Lemma 21, we have that
tm{C4 } (G) ≤ k if and only if for some i ≥ |V (G) ∪ {v0 }| − k and some j ≤ 32 (i − 1), we
have A′r (∅, ∅, ∅, i, j, 1 + j − i) 6= ∅.
We now focus on the running time of the algorithm. The size of the intermediate
sets of weighted partitions, for a leaf node and for an introduce vertex node are upper−1
bounded by 2|s (1)| . For a forget vertex node, as in the big union operation we take
into consideration a unique extension of s, at most 2 possible extensions of s0 , and at
−1
most 2|s (1)| possible extenstions for r, we obtain that the intermediate sets of weighted
−1
−1
−1
−1
partitions have size at most 2|s (1)| + 2 · 2|s (1)| · 2|s (1)| ≤ 22|s (1)|+2 . For a join
node, as in the big union operation we take into consideration at most 2|E(H)| possible
functions r′ and as many functions r′′ , at most n + |s−1 | choices for i′ and i′′ , at most
3
1
1
′
′′
2 (n − 1) + |E(H)| choices for j and j , and at most 2 (n − 1) + 3 |E(H)| choices for
′
′′
ℓ and ℓ , we obtain that the intermediate sets of weighted partitions have size at most
−1
2|E(H)| · 2|E(H)| · (n + |s−1 |) · ( 23 (n − 1) + |E(H)|) · ( 21 (n − 1) + 13 |E(H)|) · 4|s (1)| . As each
time we can check the condition C4 6tm H, by Lemma 21 m(H) ≤ 23 (n(H) − 1), so we
−1
obtain that the intermediate sets of weighted partitions have size at most 6 · n3 · 25|s (1)| .
Moreover, for each node t ∈ V (T ), the function reduce will be called as many times as
the number of possible entries, i.e., at most 2O(w) · n3 times. Thus, using Theorem 11,
A′t can be computed in time 2O(w) · n6 . The theorem follows by taking into account the
linear number of nodes in a nice tree decomposition.
34

5

Single-exponential lower bound for any connected F

Theorem 13. Let F be a connected collection. Neither F-TM-Deletion nor F-MDeletion can be solved in time 2o(tw) · nO(1) unless the ETH fails.
Proof. Let F be a connected collection and recall that w = tw(G). Without loss of
generality, we can assume that F is a topological minor antichain. We present a reduction
from Vertex Cover to F-TM-Deletion, both parameterized by the treewidth of the
input graph, and then we explain the changes to be made to prove the lower bound for
F-M-Deletion. It is known that Vertex Cover cannot be solved in time 2o(w) · nO(1)
unless the ETH fails [19] (in fact, it cannot be solved even in time 2o(n) ).
First we select an essential pair (H, B) of F. Let a be the ﬁrst vertex of (H, B), b be
the second vertex of (H, B), and A be the core of (H, B).
Let G be the input graph of the Vertex Cover problem and let < be an arbitrary
total order on V (G). We build a graph G′ starting from G. For each vertex v of G,
we add a copy of A, which we call Av , and we identify the vertices v and a. For each
edge e = {v, v ′ } ∈ E(G) with v < v ′ , we remove e, we add a copy of B, which we call
B e , and we identify the vertices v and a and the vertices v ′ and b. This concludes the
construction of G′ . Note that |V (G′ )| = |V (G)| · |V (A)| + |E(G)| · |V (B) \ {a, b}| and
that tw(G′ ) = max{tw(G), tw(H)}.
We claim that there exists a solution of size at most k of Vertex Cover in G if
and only if there is a solution of size at most k of F-TM-Deletion in G′ .
In one direction, assume that S is a solution of F-TM-Deletion in G′ with |S| ≤ k.
By deﬁnition of the problem, for each e = {v, v ′ } ∈ E(G) with v < v ′ , either B e contains
an element of S or Av contains an element of S. Let S ′ = {v ∈ V (G) | ∃v ′ ∈ V (G) : v <
v ′ , e = {v, v ′ } ∈ E(G), (V (B e ) \ {v, v ′ }) ∩ S 6= ∅} ∪ {v ∈ V (G) | V (Av ) ∩ S 6= ∅}. Then
S ′ is a solution of Vertex Cover in G and |S ′ | ≤ |S| ≤ k.
In the other direction, assume that we have a solution S of size at most k of Vertex
Cover in G. We want to prove that S is also a solution of F-TM-Deletion in G′ . For
this, we ﬁx an arbitrary H ′ ∈ F and we show that H ′ is not a topological minor of G′ \S.
First note that the connected components of G′ \ S are either of the shape Av \ {v} if
′
v ∈ S, B e \ e if e ⊆ S, or the union of Av with zero, one, or more graphs B {v,v } \ {v ′ }
such that {v, v ′ } ∈ E(G) if v ∈ V (G) \ S. As F is a topological minor antichain, for
any v ∈ V (G), H ′ 6tm Av \ {v} and for any e ∈ E(G), H ′ 6tm B e \ e. Moreover, let
v ∈ V (G) \ S and let K be the connected component of G \ S containing v. K is the
′
union of Av and of every B {v,v } \ {v ′ } such that {v, v ′ } ∈ E(G). As, for each v ′ ∈ V (G)
′
such that {v, v ′ } ∈ E(G), v ′ is not an isolated vertex in B {v,v } , by deﬁnition of B, for
′
any B ′ ∈ L(bct(H ′ )), |E(B {v,v } \ {v ′ })| < |E(B ′ )|. This implies that for each leaf B ′
′
of bct(H ′ ) and for each {v, v ′ } ∈ E(G), B ′ 6tm B {v,v } \ {v ′ }. Moreover, it follows by
deﬁnition of F that H ′ 6tm Av . This implies by Lemma 2 that H ′ is not a topological
minor of K. Moreover, as H ′ is connected by hypothesis, it follows that that H ′ is not
a topological minor of G′ \ S either. This concludes the proof for the topological minor
version.
Finally, note that the same proof applies to F-M-Deletion as well, just by replacing
35

• F-TM-Deletion with F-M-Deletion,
• topological minor with minor,
• tm with m , and
• Lemma 2 with Lemma 3.

6

Superexponential lower bound for specific cases

In this section, we focus on the graph classes P = {Pi | i ≥ 6} and K, and we show the
following theorem. Let us recall that K is the set containing every connected graph G
+
such that L(bct(G)) ∩ {K2,r , K2,r
| r ≥ 0} = ∅. Note that K can be equivalently deﬁned
as the set containing every connected graph G such that for each B ∈ L(bct(G)) and for
each r ∈ N, B 6tm K2,r (or B 6m K2,r , which is equivalent).
Theorem 14. Let F be a regular collection such that F ⊆ P or F ⊆ K. Unless
the ETH fails, neither F-TM-Deletion nor F-M-Deletion can be solved in time
2o(tw log tw) · nO(1) .
In particular, this theorem implies the result of Pilipczuk [30] as a corollary. Indeed,
Vertex Planarization corresponds to F-Deletion where F = {K5 , K3,3 }, and note
that {K5 , K3,3 } ⊆ K.
Corollary 1. Unless the ETH fails, Vertex Planarization cannot be solved in time
2o(tw log tw) · nO(1) .
Note also that Theorem 14 also implies the results stated in items 4 and 5 of the
introduction, as all these graphs are easily seen to belong in K.
Corollary 2. Unless the ETH fails, for each F ∈ {{Ci } | i ≥ 5} ∪ {{Ki } | i ≥ 4},
neither F-TM-Deletion nor F-M-Deletion can be solved in time 2o(tw log tw) · nO(1) .
In the following we focus on the proof of Theorem 14 for F-TM-Deletion. Namely,
we describe in Subsection 6.1 the general construction used to prove Theorem 14, and
in Subsection 6.2 (resp. Subsection 6.3) we explain how to complete this construction to
prove the hardness results for collections F such that F ⊆ P (resp. F ⊆ K). We explain
in Subsection 6.4 end how to modify the proof to obtain the result for F-M-Deletion.

6.1

The general construction

In order to prove Theorem 14, we will reduce from the following problem, deﬁned by
Lokshtanov et al. [28].

36

k × k Permutation Clique
Input: An integer k and a graph G with vertex set [1, k] × [1, k].
Parameter: k.
Output: Is there a k-clique in G with exactly one element from each row and exactly
one element from each column?
Theorem 15 (Lokshtanov et al. [28]). The k×k Permutation Clique problem cannot
be solved in time 2o(k log k) unless the ETH fails.
We now present the common part of the construction for both P and K. Let F be a
regular collection such that F ⊆ P or F ⊆ K. In the following, we assume without loss
of generality that F is a topological minor antichain. Note that if F ⊆ P, then |F| = 1.
Let us ﬁx (H, B) to be an essential pair of F.
We ﬁrst deﬁne some gadgets that generalize the K5 -edge gadget and the s-choice
gadget introduced in [30]. Given a graph G and two vertices x and y of G, by introducing
an H-edge gadget between x and y we mean that we add a copy of H where we identify
the ﬁrst vertex of (H, B) with y and the second vertex of (H, B) with x. Note that {x, y}
is a cut set that separates the H-edge gadget and the remaining of the graph. Note also
that the role of x and y is not symmetric. Using the fact that an H-edge gadget between
two vertices x and y is a copy of H and that {x, y} is a cut set, we have that the H-edge
gadgets clearly satisfy the following proposition.
Proposition 16. If F-TM-Deletion has a solution on (G, k) then
• this solution intersects every H-edge gadget, and
• there exists a solution S such that for each H-edge gadget A between two vertices
x and y, V (A) ∩ S ⊆ {x, y} and {x, y} ∩ S 6= ∅.
In the following, we will always assume that the solution that we take into consideration is a solution satisfying the properties given by Proposition 16. Moreover, we will
restrict the solution to contain only vertices of H-edge gadgets by setting an appropriate
budget to the number of vertices we can remove from the input graph G.
Given a graph G and two vertices x and y of G, by introducing a B-edge gadget
between x and y we mean that we add a copy of B where we identify the ﬁrst vertex of
(H, B) with y and the second vertex of (H, B) with x.
Given a graph G and three vertices x, y, and z of G, by introducing a double H-edge
gadget between x and z through y we mean that we introduce an H-edge gadget between
z and y and we introduce a B-edge gadget between x and y. Note that this implies that
there is an H-edge gadget between x and y and an H-edge gadget between z and y.
Given a set of s vertices {xi | i ∈ [1, s]}, by introducing an H-choice gadget connecting
{xi | i ∈ [1, s]}, we mean that we add 2s + 2 vertices zi , i ∈ [0, 2s + 1], for each i ∈ [0, 2s],
we introduce an H-edge gadget between zi and zi+1 , and for each i ∈ [1, s], we introduce
two B-edge gadgets, one between xi and z2i−1 and another between xi and z2i . We see
37

the H-choice gadget as a graph induced by the vertices {xi | i ∈ [1, s]} ∪ {zi | i ∈ [0, 2s]},
the B-edge gadgets, and the H-edge gadgets.
The following proposition is very similar to [30, Lemma 5].
Proposition 17. For every H-choice gadget connecting a set of s vertices {xi | i ∈
[1, s]},
• the smallest size of the restriction of a solution of F-TM-Deletion to this Hchoice gadget is 2s,
• for every i ∈ [1, s], there exists a solution S such that xi 6∈ S, and
• every solution S of size 2s is such that there exists i ∈ [1, s] such that xi 6∈ S.
Proof. In any solution we need, for each i ∈ [1, s], to take two vertices among xi , z2i−1 ,
and z2i . This implies that any solution is of size at least 2s. Moreover, for every i ∈ [1, s],
the set {xj | j 6= i}∪{z2j−1 | j ∈ [1, i]}∪{z2j | j ∈ [i, s]} is a solution of F-TM-Deletion
in the H-choice gadget of size 2s. This can be seen using Lemma 2 and the fact that
F is a topological minor antichain, as we did in the proof of Theorem 13. Finally, note
that any solution need to contain at least s + 1 vertices from {zi | i ∈ [0, 2s + 1]}. This
implies that in any solution S of size at most 2s, at least one vertex from {xi | i ∈ [1, s]}
is not in S.
We now start the description of the general construction. Given an instance (G, k)
of k × k Permutation Clique, we construct an instance (G′ , ℓ) of F-TM-Deletion,
which we call the general H-construction of (G, k).
We ﬁrst introduce k2 + 2k vertices, namely {ci | i ∈ [1, k]}, {ri | i ∈ [1, k]}, and
{ti,j | i, j ∈ [1, k]}. For each i, j ∈ [1, k], we add the edges {rj , ti,j } and {ti,j , ci }. For
each j ∈ [1, k], we introduce an H-choice gadget connecting {ti,j | i ∈ [1, k]}. This part
of the construction is depicted in Figure 1.
We now describe how we encode the edges of G in G′ . For each edge e ∈ E(G),
we deﬁne the integers p(e), γ(e), q(e), and δ(e), elements of [1, k], such that e =
{(p(e), γ(e)), (q(e), δ(e))} with p(e) ≤ q(e). Note that the edges e such that p(e) = q(e)
are not relevant to our construction and hence we safely forget them. For each edge
ℓ
r
e ∈ E(G), we add to G′ three new vertices, dℓe , dm
e , and de , and four edges {de , cp(e) },
{dℓe , rγ(e) }, {dre , cq(e) }, and {dre , rδ(e) }. Then we introduce a double H-edge gadget between dℓe and dre through dm
e . The encoding of an edge e ∈ E(G) is depicted in Figure 2.
For each 1 ≤ p < q ≤ k, we deﬁne E(p, q) = {e ∈ E(G) | (p(e), q(e)) = (p, q)} and
we introduce an H-choice gadget connecting {dℓe | e ∈ E(p, q)}. Note that even if the
construction seems to give a privilege to vertices of type dℓe over the vertices of type dre ,
the roles of vertices of type dℓe and dre are symmetric.
For each e ∈ E(G), we increase the size of the requested solution in G′ by one, the
initial budget being the sum of the budget given by Proposition 17 over all the H-choice
gadgets introduced in the construction. Because of the double H-edge gadget, we need
r
ℓ
to take in the solution either dm
e or both de and de . The extra budget given for each
38

r3

r2

r1

c1

t1,3

t2,3

t3,3

t1,2

t2,2

t3,2

t1,1

t2,1

t3,1

c2

c3

Figure 1: The general H-construction, where the dotted parts correspond to H-edge
gadgets, without the encoding of the edges of E(G).
cp(e)

cq(e)
dℓe

dm
e

rγ(e)

dre

rδ(e)

Figure 2: The encoding of an edge e = {(p(e), γ(e)), (q(e), δ(e))} of G, where the dotted
lines correspond to a double H-edge gadget.
ℓ
edge permits to include dm
e in the solution. If the H-choice gadget connected to de
already chooses dℓe to be in the solution, then we can safely use the extra budget given
m
for the edge e to add dre in the solution instead of dm
e . In the case de is chosen, then
in the resulting graph cp(e) remains connected to rγ(e) and cq(e) remains connected to
rδ(e) . In the following, we take into consideration only a solution S such that either
r
ℓ r
ℓ m r
m
{dℓe , dm
e , de } ∩ S = {de , de } or {de , de , de } ∩ S = {de } for each e ∈ E(G).
We set ℓ = 3|E(G)| + 2k2 . By construction, this budget is tight and permits to take
only a minimum-size solution in every H-choice gadget and one endpoint of each H-edge
′
gadget between dre and dm
e , e ∈ E(G). This concludes the general H-construction (G , ℓ)
of (G, k).
Let us now discuss about the treewidth of G′ . By deleting 2k vertices, namely the
vertices {ci | i ∈ [1, k]} and the vertices {rj | j ∈ [1, k]}, we obtain a graph where
each connected component is an H-choice gadget, with eventually some pendant Hedge gadgets or double H-edge gadgets. As the treewidth of the H-choice gadget, the
H-edge gadget, and the double H-choice gadget is linear in |V (H)|, we obtain that
tw(G) = Od (k) (recall that d = size(F)).

39

Let σ : [1, k] → [1, k] be a permutation. If {(σ(i), i) | i ∈ [1, k]} induces a k-clique in
G, then we say that σ is a solution of k × k Permutation Clique on (G, k). We denote
by eσp,q the edge {(σ(p), p), (σ(q), q)}. With such σ, we associate a σ-general H-solution
S such that
• S ⊆ V (G′ ),
• |S| = 3|E(G)| + 2k2 ,
• for each j ∈ [1, k], S restricted to the H-choice gadget connecting {ti,j | i ∈ [1, k]} is
a solution of F-TM-Deletion of size 2k such that {ti,j | i ∈ [1, k]} \ {tσ(j),j } ⊆ S
and tσ(j),j 6∈ S,
• for each p, q ∈ [1, k], p < q, such that eσp,q ∈ E(G), S restricted to the H-choice
gadget connecting {dℓe | e ∈ E(p, q)} is a solution of F-TM-Deletion of size
2|E(p, q)| such that {dℓe | e ∈ E(p, q) \ {eσp,q }} ⊆ S and dℓeσp,q 6∈ S,
• for each p, q ∈ [1, k], {dre | e ∈ E(p, q) \ {eσp,q }} ⊆ S and dreσp,q 6∈ S, and
∈ S.
• for each p, q ∈ [1, k], dm
eσ
p,q
Note that, with this construction of S, we already impose 3|E(G)| + 2k2 vertices to
be in S, and therefore no other vertex of G′ can be in S.
Given S ⊆ V (G′ ), we say that S satisﬁes the permutation property if
• for each e ∈ E(G) such that dℓe 6∈ S and for each j ∈ [1, k] \ {γ(e)}, tp(e),j ∈ S, and
• for each e ∈ E(G) such that dre 6∈ S and for each j ∈ [1, k] \ {δ(e)}, tq(e),j ∈ S.
Lemma 22. If S is a subset of V (G′ ) such that
• |S| ≤ 3|E(G)| + 2k2 ,
• for each H-choice gadget, S restricted to this H-choice gadget is a solution of
F-TM-Deletion of minimum size,
r
ℓ r
• for each edge e ∈ E(G), S is such that either {dℓe , dm
e , de } ∩ S = {de , de } or
ℓ
m
r
m
{de , de , de } ∩ S = {de }, and

• S satisfies the permutation property,
then
• there is a unique permutation σ : [1, k] → [1, k] such that S ∩ {ti,j | i, j ∈ [1, k]} =
{ti,j | i, j ∈ [1, k]} \ {tσ(j),j | j ∈ [1, k]} and
• {(σ(j), j) | j ∈ [1, k]} induces a clique in G.
40

Proof. By hypothesis, for each 1 ≤ p < q ≤ k, we know that there is an edge e ∈ E(p, q)
such that dℓe 6∈ S and dre 6∈ S. As S satisﬁes the permutation property, this implies
that for each set {ti,j | i ∈ [1, k]}, j ∈ [1, k], at most one vertex is not in S. As we
have supposed that for each set {ti,j | j ∈ [1, k]}, i ∈ [1, k], at least one vertex is
not in S, this implies that there is a unique permutation σ : [1, k] → [1, k] such that
S ∩ {ti,j | i, j ∈ [1, k]} = {ti,j | i, j ∈ [1, k]} \ {tσ(j),j | j ∈ [1, k]}. Moreover, for each
1 ≤ p < q ≤ k, eσp,q ∈ E(G). Indeed, if eσp,q 6∈ E(G), then there exists e ∈ E(p, q) such
that σ(γ(e)) 6= p or σ(δ(e)) 6= q and such that dℓe 6∈ S and dre 6∈ S. Assume without loss
of generality, that σ(γ(e)) 6= p. As tp,σ−1 (p) 6∈ S, this contradicts the fact that S satisﬁes
the permutation property.
We call the permutation given by Lemma 22 the associated permutation of S.
To conclude the reduction, we deal separately with the cases F ⊆ P and F ⊆ K.
For each such F, we will assume without loss of generality that F is a topological minor
antichain, we will ﬁx (H, B) to be an essential pair of F, and given an instance (G, k) of
k × k Permutation Clique we will start from the general H-construction (G′ , ℓ) and
add some edges and vertices in order to build an instance (G′′ , ℓ) of F-TM-Deletion.
We will show that if k × k Permutation Clique on (G, k) has a solution σ, then the
σ-general H-solution is a solution of F-TM-Deletion on (G′′ , ℓ). Conversely, we will
show that if F-TM-Deletion on (G′′ , ℓ) has a solution S, then this solution satisﬁes the
permutation property. This automatically gives, using Lemma 22, that the associated
permutation σ of S is a solution of k × k Permutation Clique on (G, k).

6.2

The reduction for paths

Theorem 18. Given an integer h ≥ 6, the {Ph }-TM-Deletion problem cannot be
solved in time 2o(tw log tw) · nO(1) , unless the ETH fails.
Proof. Let h ≥ 6 be an integer and let F = {Ph }. Let (G, k) be an instance of k × k
Permutation Clique and let (G′ , ℓ) be the general Ph -construction of (G, k) described
in Subsection 6.1. We build G′′ starting from G′ by adding, for each i, j ∈ [1, k], a pendant
path of size h − 6 to ti,j . This completes the construction of G′′ . Note that if h = 6,
then G′′ = G′ .
Let σ be a solution of k × k Permutation Clique on (G, k) and let S be the
σ-general Ph -solution. To show that G′′ \ S does not contain Ph as a topological minor,
we show that each connected component of G′′ \ S does not contain Ph as a topological
minor. Note that, by deﬁnition of S, the only connected components of G′′ \ S that can
contain Ph are the connected components that contain a vertex in {ci | i ∈ [1, k]} ∪ {rj |
j ∈ [1, k]}. Moreover, each of these connected components is a subgraph of G′′ induced
by {rj , cσ(j) , tσ(j),j } ∪ {dℓe | e ∈ E(G), σ(γ(e)) = p(e), σ(δ(e)) = q(e), p(e) = j} ∪ {dre |
e ∈ E(G), σ(γ(e)) = p(e), σ(δ(e)) = q(e), q(e) = j} and the vertices of the path of size
h − 6 pendant to tσ(j),j , for some j ∈ [1, k]. These connected components, depicted in
Figure 3 for the case h = 8, do not contain Ph as a topological minor, as it can be easily

41

checked that a longest path in them has h − 1 vertices. Therefore, S is a solution of
F-TM-Deletion on (G′′ , ℓ).
cσ(i)

ti,σ(i)

···

pendant path of size 2

ri

Figure 3: The connected component of G′′ \S that contains the vertex ri , i ∈ [1, k] where
h = 8.
Conversely, let S be a solution of F-TM-Deletion on (G′′ , ℓ). We ﬁrst show that
S satisﬁes the permutation property. Let e ∈ E(G) be such that dℓe 6∈ S and assume
that tp(e),j 6∈ S for some j ∈ [1, k] \ {γ(e)}. By construction of the Ph -choice gadget,
we know that there exists i0 ∈ [1, k] such that ti0 ,γ(e) 6∈ S. This implies that the path
rj tp(e),j cp(e) dℓe rγ(e) ti0 ,γ(e) together with the pendant path with h − 6 vertices attached to
ti0 ,γ(e) form a path with h vertices. As the same argument also works if dre 6∈ S, it follows
that S satisﬁes the permutation property, concluding the proof.

6.3

The reduction for subsets of K

Theorem 19. Given a regular collection F ⊆ K, the F-TM-Deletion problem cannot
be solved in time 2o(tw log tw) · nO(1) , unless the ETH fails.
Proof. Let F ⊆ K be a regular collection. We assume without loss of generality that F
is a topological minor antichain. Let (H, B) be an essential pair of F, let a be the ﬁrst
vertex of (H, B), let b be the second vertex of (H, B), let B = (V (B), E(B) \ {a, b}), and
let C be the core of (H, B). Let (G, k) be an instance of k × k Permutation Clique
and let (G′ , ℓ) be the general H-construction of (G, k). We build G′′ starting from G′
by adding a new vertex r0 , adding a copy of the core of (H, B) and identifying a and r0 ,
and adding for each j ∈ [1, k] a copy of B in which we identify a and r0 , and b and rj .
This completes the construction of G′′ .
Let σ be a solution of k × k Permutation Clique on (G, k) and let S be the σgeneral H-solution. We show that F 6tm G′′ \ S. For this, let us ﬁx H ′ ∈ F. Note that,
by deﬁnition of S, the only connected component of G′′ \ S that can contain H ′ is the
one containing {ci | i ∈ [1, k]} ∪ {rj | j ∈ [1, k]}. Let K be this connected component,
depicted in Figure 4. Note that for each j ∈ [0, k], rj is a cut vertex of K. Moreover,
42

we know that H ′ 6tm C and for each B ′ ∈ L(bct(H ′ )), B ′ 6tm B and B ′ 6tm K2,k .
This implies, using Lemma 2, that H ′ is not a topological minor of K. Therefore, S is
a solution of F-TM-Deletion on (G′′ , ℓ).
r3

cσ(3)

r2

cσ(2)

r1

cσ(1)

B
C

r0

B
B

Figure 4: The main connected component of G′′ \ S.
Conversely, let S be a solution of F-TM-Deletion on (G′′ , ℓ). We show that S
satisﬁes the permutation property. Let e ∈ E(G) be such that dℓe 6∈ S and assume that
tp(e),j 6∈ S for some j ∈ [1, k]\{γ(e)}. This implies that there exists in G′′ \S a (r0 , rγ(e) )path that uses the vertices r0 , rj , tp(e),j , cp(e) , dℓe , and rγ(e) and that does not use any
edge of the graph B = (V (B), E(B) \ {a, b}) between r0 and rγ(e) . By construction, this
implies that H is a topological minor of G′′ \ S. As the same argument also works if
dre 6∈ S, it follows that S satisﬁes the permutation property, concluding the proof.

6.4

The minor version

Theorems 18 and 19 allow to prove the statement of Theorem 14 for topological minors.
The equivalent statement of Theorem 14 for minors follows from the same proof as for
the topological minor version by applying the following local modiﬁcations:
• we replace F-TM-Deletion with F-M-Deletion,
• we replace topological minor with minor,
• we replace tm with m , and
• we replace Lemma 2 with Lemma 3.

7

Conclusions and further research

We analyzed the parameterized complexity of F-M-Deletion and F-TM-Deletion
taking as the parameter the treewidth of the input graph. We obtained a number of
lower and upper bounds for general and speciﬁc collections F, several of them being
tight (in particular, for all cycles). In order to complete the dichotomy for cliques and
43

paths (see Table 1), it remains to settle the complexity when F = {Ki } with i ≥ 5 and
when F = {P5 }.
An ultimate goal is to establish the tight complexity of F-Deletion for all collections
F, but we are still very far from it. In particular, we do not know whether there exists
some F for which a double-exponential lower bound can be proved, or for which the
complexities of F-M-Deletion and F-TM-Deletion diﬀer.
In the last years, the F-M-Deletion problem has been extensively studied in the
literature taking as the parameter the size of the solution [14,20–23]. In all these papers,
FPT algorithms parameterized by treewidth play a fundamental role. We hope that
our results will be helpful in this direction. Note that the connectivity of F was also
relevant in previous work [14, 22], as it is the case of the current article. Getting rid of
connectivity in both the lower and upper bounds we presented is an interesting avenue.
Our algorithms for {Ci }-Deletion may also be used to devise approximation algorithms for hitting or packing long cycles in a graph (in the spirit of [7] for other patterns),
possibly by using the fact that cycles of length at least i satisfy the Erdős-Pósa property [13].
We did not focus on optimizing either the degree of the polynomials or the constants
involved in our algorithms. Concerning the latter, one could use the framework presented
by Lokshtanov et al. [27] to prove lower bounds based on the Strong Exponential Time
Hypothesis.
It is easy to check that the lower bounds presented in Sections 5 and 6 also hold
for treedepth (as it is the case in [30]) which is a parameter more restrictive than
treewidth [6]. Also, it is worth mentioning that F-Deletion is unlikely to admit polynomial kernels parameterized by treewidth for essentially any collection F, by using
the framework introduced by Bodlaender et al. [3] (see [6] for an explicit proof for any
problem satisfying a generic condition).

References
[1] J. Baste, M. Noy, and I. Sau. The number of labeled graphs of bounded treewidth.
CoRR, abs/1604.07273, 2016.
[2] H. L. Bodlaender, M. Cygan, S. Kratsch, and J. Nederlof. Deterministic single
exponential time algorithms for connectivity problems parameterized by treewidth.
Information and Computation, 243:86–111, 2015.
[3] H. L. Bodlaender, R. G. Downey, M. R. Fellows, and D. Hermelin. On problems
without polynomial kernels. Journal of Computer and System Sciences, 75(8):423–
434, 2009.
[4] 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(2):317–378, 2016.

44

[5] H. L. Bodlaender, F. V. Fomin, D. Lokshtanov, E. Penninkx, S. Saurabh, and D. M.
Thilikos. (meta) kernelization. Journal of the ACM, 63(5):44:1–44:69, 2016.
[6] M. Bougeret and I. Sau. How much does a treedepth modulator help to obtain
polynomial kernels beyond sparse graphs? CoRR, abs/1609.08095, 2016.
[7] D. Chatzidimitriou, J. Raymond, I. Sau, and D. M. Thilikos. An O(log OP T )Approximation for Covering/Packing Minor Models of Θr . In Proc. of the 13th
International Workshop on Approximation and Online Algorithms (WAOA), volume
9499 of LNCS, pages 122–132, 2015.
[8] B. Courcelle. The Monadic Second-Order Logic of Graphs. I. Recognizable Sets of
Finite Graphs. Information and Computation, 85(1):12–75, 1990.
[9] M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk,
M. Pilipczuk, and S. Saurabh. Parameterized Algorithms. Springer, 2015.
[10] M. Cygan, J. Nederlof, M. Pilipczuk, M. Pilipczuk, J. M. M. van Rooij, and J. O.
Wojtaszczyk. Solving Connectivity Problems Parameterized by Treewidth in Single
Exponential Time. In Proc. of the 52nd Annual IEEE Symposium on Foundations
of Computer Science (FOCS), pages 150–159, 2011.
[11] R. Diestel. Graph Theory. Springer-Verlag, 3rd edition, 2005.
[12] R. G. Downey and M. R. Fellows. Fundamentals of Parameterized Complexity. Texts
in Computer Science. Springer, 2013.
[13] S. Fiorini and A. Herinckx. A tighter Erdős-Pósa function for long cycles. Journal
of Graph Theory, 77(2):111–116, 2014.
[14] F. V. Fomin, D. Lokshtanov, N. Misra, and S. Saurabh. Planar F-Deletion: Approximation, Kernelization and Optimal FPT Algorithms. In Proc. of the 53rd Annual
IEEE Symposium on Foundations of Computer Science (FOCS), pages 470–479,
2012.
[15] F. V. Fomin, D. Lokshtanov, F. Panolan, and S. Saurabh. Eﬃcient computation
of representative families with applications in parameterized and exact algorithms.
Journal of the ACM, 63(4):29:1–29:60, 2016.
[16] F. V. Fomin, D. Lokshtanov, S. Saurabh, and D. M. Thilikos. Bidimensionality and
kernels. In Proc. of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms
(SODA), pages 503–510, 2010. Full version available at CoRR, abs/1606.05689,
2016.
[17] V. Garnero, C. Paul, I. Sau, and D. M. Thilikos. Explicit linear kernels via dynamic
programming. SIAM Journal on Discrete Mathematics, 29(4):1864–1894, 2015.

45

[18] J. E. Hopcroft and R. E. Tarjan. Eﬃcient algorithms for graph manipulation.
Communations of ACM, 16(6):372–378, 1973.
[19] R. Impagliazzo, R. Paturi, and F. Zane. Which problems have strongly exponential
complexity? Journal of Computer and System Sciences, 63(4):512–530, 2001.
[20] B. M. P. Jansen, D. Lokshtanov, and S. Saurabh. A near-optimal planarization algorithm. In Proc. of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms
(SODA), pages 1802–1811, 2014.
[21] G. Joret, C. Paul, I. Sau, S. Saurabh, and S. Thomassé. Hitting and harvesting
pumpkins. SIAM Journal on Discrete Mathematics, 28(3):1363–1390, 2014.
[22] E. J. Kim, A. Langer, C. Paul, F. Reidl, P. Rossmanith, I. Sau, and S. Sikdar. Linear kernels and single-exponential algorithms via protrusion decompositions. ACM
Transactions on Algorithms, 12(2):21:1–21:41, 2016.
[23] E. J. Kim, C. Paul, and G. Philip. A single-exponential FPT algorithm for the K4 minor cover problem. Journal of Computer and System Sciences, 81(1):186–207,
2015.
[24] T. Kloks. Treewidth. Computations and Approximations. Springer-Verlag LNCS,
1994.
[25] J. Komlós and E. Szemerédi. Topological cliques in graphs II. Combinatorics,
Probability & Computing, 5:79–90, 1996.
[26] J. M. 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.
[27] D. Lokshtanov, D. Marx, and S. Saurabh. Lower bounds based on the exponential
time hypothesis. Bulletin of the EATCS, 105:41–72, 2011.
[28] D. Lokshtanov, D. Marx, and S. Saurabh. Slightly superexponential parameterized problems. In Proc. of the 22nd Annual ACM-SIAM Symposium on Discrete
Algorithms (SODA), pages 760–776, 2011.
[29] D. Paik, S. M. Reddy, and S. Sahni. Deleting vertices to bound path length. IEEE
Transactions on Computers, 43(9):1091–1096, 1994.
[30] M. Pilipczuk.
A tight lower bound for Vertex Planarization on
graphs of bounded treewidth.
Discrete Applied Mathematics, DOI:
http://dx.doi.org/10.1016/j.dam.2016.05.019, 2016, to appear.
[31] N. Robertson and P. D. Seymour. Graph minors. V. Excluding a planar graph.
Journal of Combinatorial Theory, Series B, 41(1):92–114, 1986.
[32] N. Robertson and P. D. Seymour. Graph minors. X. Obstructions to tree decomposition. Journal of Combinatorial Theory, Series B, 52(2):153–190, 1991.

46

