arXiv:1510.03945v2 [] 19 Jan 2017

An O(log OPT)-approximation for covering and packing
minor models of θr ∗
Dimitris Chatzidimitriou†

Jean-Florent Raymond‡§

Ignasi Sau§

Dimitrios M. Thilikos† §

Abstract
Given two graphs G and H, we define v-coverH (G) (resp. e-coverH (G)) as the minimum
number of vertices (resp. edges) whose removal from G produces a graph without any
minor isomorphic to H. Also v-packH (G) (resp. e-packH (G)) is the maximum number
of vertex- (resp. edge-) disjoint subgraphs of G that contain a minor isomorphic to
H. We denote by θr the graph with two vertices and r parallel edges between them.
When H = θr , the parameters v-coverH , e-coverH , v-packH , and e-packH are NP-hard to
compute (for sufficiently big values of r). Drawing upon combinatorial results in [7], we
give an algorithmic proof that if v-packθr (G) ≤ k, then v-cover θr (G) = O(k log k), and
similarly for e-packθr and e-cover θr . In other words, the class of graphs containing θr as
a minor has the vertex/edge Erdős-Pósa property, for every positive integer r. Using the
algorithmic machinery of our proofs we introduce a unified approach for the design of
an O(log OPT)-approximation algorithm for v-packθr , v-cover θr , e-packθr , and e-coverθr
that runs in O(n · log(n) · m) steps. Also, we derive several new Erdős-Pósa-type results
from the techniques that we introduce.
Keywords: Erdős-Pósa property, packings in graphs, coverings in graphs, minormodels of θr , approximation algorithms, protrusion decomposition.
MSC 2010: 05C70.

1

Introduction

All graphs in this paper are undirected, do not have loops but they may contain multiple
edges. We denote by θr the graph containing two vertices x and y connected by r parallel
edges between x and y. Given a graph class C and a graph G, we call C-subgraph of G any
subgraph of G that is isomorphic to some graph in C. All along this paper, when giving
the running time of an algorithm with input some graph G, we agree that n = |V (G)| and
m = |E(G)|.
∗ This research have been supported by the Warsaw Centre of Mathematics and Computer Science (JeanFlorent Raymond), by the (Polish) National Science Centre grant PRELUDIUM 2013/11/N/ST6/02706
(Jean-Florent Raymond), and by the E.U. (European Social Fund - ESF) and Greek national funds through
the Operational Program “Education and Lifelong Learning” of the National Strategic Reference Framework
(NSRF) - Research Funding Program: “Thales. Investing in knowledge society through the European Social
Fund” (Dimitris Chatzidimitriou and Dimitrios M. Thilikos). Email addresses: hatzisdimitris@gmail.com ,
jean-florent.raymond@mimuw.edu.pl, ignasi.sau@lirmm.fr, and sedthilk@thilikos.info.
† Department of Mathematics, National and Kapodistrian University of Athens, Greece.
‡ Faculty of Mathematics, Informatics and Mechanics, University of Warsaw, Poland.
§ AlGCo project team, CNRS, LIRMM, France.

1

Packings and coverings. Paul Erdős and Lajos Pósa, proved in 1965 [12] that there is
a function f : N → N such that for each positive integer k, every graph either contains k
vertex-disjoint cycles or it contains f (k) vertices that intersect every cycle in G. Moreover,
they proved that the “gap” of this min-max relation is f (k) = O(k · log k) and that this
gap is optimal. This result initiated an interesting line of research on the duality between
coverings and packings of combinatorial objects. To formulate this duality, given a class C
of connected graphs, we define v-coverC (G) (resp. e-coverC (G)) as the minimum cardinality
of a set S of vertices (resp. edges) such that each C-subgraph of G contains some element of
S. Also, we define v-packC (G) (resp. e-packC (G)) as the maximum number of vertex- (resp.
edge-) disjoint C-subgraphs of G.
We say that C has the vertex Erdős–Pósa property (resp. the edge Erdős–Pósa property) if there is a function f : N → N, called gap function, such that, for every graph G,
v-coverC (G) ≤ f (v-packC (G)) (resp. e-coverC (G) ≤ f (e-packC (G))). Using this terminology,
the original result of Erdős and Pósa says that the set of all cycles has the vertex Erdős–Pósa
property with gap O(k · log k). The general question in this branch of Graph Theory is to
detect instantiations of C which have the vertex/edge Erdős–Pósa property (in short, v/eEP-property) and when this is the case, minimize the gap function f . Several theorems of
this type have been proved concerning different instantiations of C such as odd cycles [24,30],
long cycles [3], and graphs containing cliques as minors [10] (see also [18, 22, 34] for results
on more general combinatorial structures and [31, 33] for surveys).
A general class that is known to have the v-EP-property is the class CH of the graphs
that contain some fixed planar graph H as a minor1 . This fact was proven by Robertson and
Seymour in [35] and the best known general gap is f (k) = O(k · logO(1) k) due to the results
of [8] — see also [14–16] for better gaps for particular instantiations of H. Moreover, the
planarity of H appears to be the right dichotomy, as for non-planar H’s, CH does not satisfy
the v-EP-property. Besides the near-optimality of the general upper bound of [8], it is open
whether the lower bound Ω(k · log k) can be matched for the general gap function, while this
is indeed the case when H = θr [14].
The question about classes that have the e-EP-property has also attracted some attention
(see [3]). According to [9, Exercise 23 of Chapter 7], the original proof of Erdős and Pósa
implies that cycles have the e-EP-property with gap O(k · log k). Moreover, as proved in [32],
the class Cθr has the e-EP-property with the (non-optimal) gap f (k) = O(k 2 · logO(1) k).
Interestingly, not much more is known on the graphs H for which CH has the e-EP-property
and is tempting to conjecture that the planarity of H provides again the right dichotomy.
Other graph classes that are known to have the e-EP-property are rooted cycles [29] (here the
cycles to be covered and packed are required to intersect some particular set of terminals of
G) and odd cycles for the case where G is a 4-edge connected graph [23], a planar graph [26],
or a graph embeddable in an orientable surface [24].
Approximation algorithms. The above defined four graph parameters are already quite
general when C := CH . From the algorithmic point of view, the computation of x-packCH
(for x ∈ {v, e}) corresponds to the general family of graph packing problems, while the
computation of x-coverCH belongs to the general family of graph modification problems where
the modification operation is the removal of vertices/edges (depending on whether x = v or
x = e). Interestingly, particular instantiations of H = θr generate known, well studied, NPhard problems. For instance, asking whether v-coverCθr ≤ k generates Vertex Cover for
r = 1, Feedback Vertex Set for r = 2, and Diamond Hitting Set for r = 3 [13, 17].
Moreover, asking whether x-packCθ2 (G) ≥ k corresponds to Vertex Cycle Packing [6, 25]
and Edge Cycle Packing [1, 27] when x = v and x = e, respectively. Finally, asking
1A

graph H is a minor of a graph G if it can be obtained from some subgraph of G by contracting edges.

2

whether |E(G)| − e-coverCθ3 (G) ≤ k corresponds to the Maximum Cactus Subgraph2 . All
parameters keep being NP-complete to compute because the aforementioned base cases can
be reduced to the general one by replacing each edge by one of multiplicity r − 1.
From the approximation point of view, it was proven in [17] that, when H is a planar
graph, there is a randomized polynomial O(1)-approximation algorithm for v-coverH . For the
cases of v-coverCθr and v-packCθr , O(log n)-approximations are known for every r ≥ 1 because
of [21] (see also [36]). Moreover, v-coverCθr admits a deterministic 9-approximation
√ [13].
Also, about e-packCθr (G) it is known, from [28], that there is a polynomial O( log n)approximation algorithm for the case where r = 2. Notice also that for r = 1, it is trivial
to compute e-coverCθr (G) in polynomial time. However, to our knowledge, nothing is known
about the computation of e-coverCθr (G) for r ≥ 3.
Our results. In this paper we introduce a unified approach for the study of the combinatorial interconnections and the approximability of the parameters v-coverCθr , e-coverCθr ,
v-packCθr , and e-packCθr . Our main combinatorial result is the following.
Theorem 1. For every r ∈ N≥2 and every x ∈ {v, e} the graph class Cθr has the x-EPproperty with (optimal) gap function f (k) = O(k · log k).
Our proof is unified and treats simultaneously the covering and the packing parameters
for both the vertex and the edge cases. This verifies the optimal combinatorial bound for the
case where x = v [14] and optimally improves the previous bound in [32] for the case where
x = e. Based on the proof of Theorem 1, we prove the following algorithmic result.
Theorem 2. For every r ∈ N≥2 and every x ∈ {v, e}, there is an algorithm that, given a
graph G, outputs an O(log OPT)-approximation of x-coverCθr (G) and x-packCθr (G) in O(n ·
log(n) · m) steps when x = v and in O(m2 log n) steps when x = e.
Theorem 2 improves the results in [21] for the cases of v-coverCθr and v-packCθr and,
to our knowledge, is the first approximation algorithm for e-coverCθr and e-packCθr for
r ≥ 3. We were also able to derive the following Erdős-Pósa-type result with linear gap
on graphs of bounded tree-partition width (the definition of this width parameter is given
in Subsection 2.2).
Theorem 3. Let t ∈ N. For every x ∈ {v, e}, the following holds: if H is a finite collection of
connected graphs and G is a graph of tree-partition width at most t, then x-coverH (G) ≤ α · xpackH (G), where α is a constant which depends only on t and H.
Let θr,r′ (for some r, r′ ∈ N≥1 ) denote the graph obtained by taking the disjoint union
of θr and θr′ and identifying one vertex of θr with one of θr′ . Another consequence of our
results is that, for every r, r′ ∈ N≥1 , the class Cθr,r′ has the edge Erdős–Pósa property.
′

Theorem 4. For every r, r′ ∈ N, there is a function f1r,r : N≥1 → N≥1 such that for every
′
simple graph G where k = e-packCθ ′ (G), it holds that e-coverCθ ′ (G) ≤ f1 r,r (k).
r,r

r,r

2 The Maximum Cactus Subgraph problem asks, given a graph G and an integer k, whether G contains
a subgraph with k edges where no two cycles share an edge. It is easy to reduce to this problem the Vertex
Cycle Packing problem on cubic graphs which, in turn, can be proved to be NP-complete using a simple
variant of the NP-completeness proof of Exact Cover by 2-Sets [19].

3

Our techniques. Our proofs are based on the notion of partitioned protrusion that,
roughly, is a tree-structured subgraph of G with small boundary to the rest of G (see
Subsection 2.2 for the precise definition). Partitioned protrusions were essentially introduced
in [7] by the name edge-protrusions and can be seen as the edge-analogue of the notion of
protrusions introduced in [4] (see also [5]). Our approach makes strong use of the main result
of [7], that is equivalently stated as Proposition 1 in this paper. According to this result,
there exists a polynomial algorithm that, given a graph G and an integer k as an input,
outputs one of the following: (1) a collection of k edge/vertex disjoint Cθr -subgraphs of G,
(2) a Cθr -subgraph J with O(log k) edges, or (3) a large partitioned protrusion of G.
Our approximation algorithm does the following for each k ≤ |V (G)|. If the first case of
the above combinatorial result applies on G, we can safely output a packing of k Cθr -subgraphs
in G. In the second case, we make some progress as we may remove the vertices/edges of J
from G and then set k := k − 1. In order to deal with the third case, we prove that in a graph
G with a sufficiently large partitioned protrusion, we can either find some Cθr -subgraph with
O(log k) edges (which is the same as in the second case), or we can replace it by a smaller
graph where both x-coverH and x-packH remain invariant (Lemma 1). The proof that such a
reduction is possible is given in Section 3 and is based on a suitable dynamic programming
encoding of partial packings and coverings that is designed to work on partitioned protrusions.
Notice that the “essential step” in the above procedure is the second case that reduces the
packing number of the current graph by 1 to the price of reducing the covering number by
O(log k). This is the main argument that supports the claimed O(log OPT)-approximation
algorithm (Theorem 2) and the corresponding Erdős–Pósa relations in Theorem 1. Finally,
Theorem 3 is a combinatorial implication of Lemma 1 and Theorem 4 follows by combining
Theorem 3 with the results of Ding and Oporowski in [11].
Organization of the paper. In Section 2 we provide all concepts and notation that we
use in our proofs. Section 3 contains the proof of Lemma 1, which is the main technical
part of the paper. The presentation and analysis of our approximation algorithm is done
in Section 4, where Theorem 1 and Theorem 2 are proven. Section 5 contains the proofs of
Theorem 3 and Theorem 4. Finally, we summarize our results and provide several directions
for further research in Section 6.

2
2.1

Preliminaries
Basic definitions

Let t = (x1 , . . . , xl ) ∈ Nl and χ, ψ : N → N. We say that χ(n) = Ot (ψ(n)) if there exists
a computable function φ : Nl → N such that χ(n) = O(φ(t) · ψ(n)). For every i, j ∈ N, we
denote by Ji, jK the interval of {i, . . . , j}.
Graphs. All graphs in this paper are undirected, loopless, and may have multiple edges.
For this reason, a graph G is represented by a pair (V, E) where V is its vertex set, denoted
by V (G) and E is its edge multi-set, denoted by E(G). The edge-multiplicity of an edge of G
is the number of times it appears in E(G). We set n(G)P
= |V (G)| and m(G) =P|E(G)|. If H
is a finite collection
of
connected
graphs,
we
set
n(H)
=
H∈H m(H),
H∈H n(H), m(H) =
S
and ∪ H = G∈H G. We denote by δ(G) the minimum degree of G, that is the minimum
number of neighbors a vertex can have in G.
Let x ∈ {v, e} where, in the rest of this paper, v will be interpreted as “vertex” and e will
be interpreted as “edge”. Given a graph G, we denote by Ax (G) the set of vertices or edges
of G depending on whether x = v or x = e, respectively.
4

Given a graph H and a graph J that are both subgraphs of the same graph G, we define
the subgraph H ∩G J of G as the graph (V (H) ∩ V (J), E(H) ∩ E(J)).
Given a graph G and a set S ⊆ V (G), such that all vertices of S have degree 2 in G, we
define diss(G, S) as the graph obtained from G after we dissolve in it all vertices in S, i.e.,
replace each maximal path whose internal vertices are in S with an edge whose endpoints
are the endpoints of the path.
A rooted tree is a pair (T, s) where T is a tree and s ∈ V (T ) is a distinguished vertex
called the root of T . If v ∈ V (T ), a vertex u ∈ V (T ) is a descendant of v in (T, s) if v
lies on the (unique) path from u to s. Note that v is a descendant of itself. We denote by
children(T,s) (v) the set of children of v, which are the vertices that are both neighbors and
descendants of v.
Given a graph G and an edge e = (u, v) ∈ E(G), the subdivision of e is defined as the
operation of removing e and adding a new vertex w and the edges (w, u) and (w, v). A graph
H is called a subdivision of G, if it can be obtained by performing a series of subdivisions in
G.
Minors and topological minors. Given two graphs G and H, we say that H is a minor
of G if there exits some function φ : V (H) → 2V (G) such that
• for every v ∈ V (H), G[φ(v)] is connected;
• for every two distinct v, u ∈ V (H), φ(v) ∩ φ(u) = ∅; and
• for every edge e = {v, u} ∈ E(H) of multiplicity l, there are at least l edges in G with
one endpoint in φ(v) and the other in φ(u).
We say that H is a topological minor of G if there exits some collection P of paths in G and
an injection φ : V (H) → V (G) such that
• no path in P has an internal vertex that belongs to some other path in P;
• φ(V (H)) is the set of endpoints of the paths in P; and
• for every two distinct v, u ∈ V (H), {v, u} is an edge of H of multiplicity l if and only
if there are l paths in P between φ(v) and φ(u).
Given a graph H, we define by ex(H) the set of all topologically-minor minimal graphs
that contain H as a minor. Notice that the size of ex(H) is upper-bounded by some function
of m(H) and that H is a minor of G if it contains a member of ex(H) as a topological minor.
An H-minor model of G is any minimal subgraph of G that contains a member of ex(H) as
a topological minor.
Subdivisions. The subdivision of an edge {u, v} of a graph is the operation that introduces
a new vertex w to the graph adjacent to u and v and deletes the edge. A graph G is a
subdivision of H if it can be obtained from H by repeteadly subdividing edges. If G is a
graph and H is a finite collection of connected graphs, an H-subdivision of G is a subgraph
M of G that is a subdivision of a graph, denoted by M̂ , that is isomorphic to a member of H.
Clearly, the vertices of M̂ are vertices of G and its edges correspond to paths in G between
their endpoints such that internal vertices of a path do not appear in any other path. We refer
to the vertices of M̂ in G as the branch vertices of the H-subdivision M , whereas internal
vertices of the paths between branch vertices will be called subdivision vertices of M . Note
that we are here dealing with what is sometimes called a topological minor model. A graph
which contains no H-subdivision is said to be H-free. Notice that G has an H-subdivision iff
G contains a graph of H as a topological minor.
5

Packings and coverings. An x-H-packing of size k of a graph G is a collection P of k
pairwise x-disjoint H-subdivisions of G. Given an x ∈ {v, e}, we define P≥k
x,H (G) as the set of
all x-H-packings of G of size at least k. An x-H-covering of a graph G is a set C ⊆ Ax (G)
such that G \ C does not contain any H-subdivision. We define C≤k
x,H (G) as the set of all
x-H-coverings of G of size at most k. We finally define
x-coverH (G) = min{k | C≤k
x,H (G) 6= ∅}
and

x-packH (G) = max{k | P≥k
x,H (G) 6= ∅}.

These numbers are well-defined: G always has a packing of size 0 (the empty packing) and a
covering of size |Ax (G)| (which contains all vertices/edges of G). It is easy to observe that,
for every graph G and every finite collection of connected graphs H, the following inequalities
hold:
v-coverH (G) ≤ e-coverH (G),

v-packH (G) ≤ e-packH (G),

v-packH (G) ≤ v-coverH (G),

e-packH (G) ≤ e-coverH (G).

Notice that the definition of these invariants differs from that given in the introduction.

2.2

Boundaried graphs

Informally, a boundaried graph will be used to represent a graph that has been obtained by
“dissecting” a larger graph along some of its edges, where the boundary vertices correspond
to edges that have been cut.
Boundaried graphs. A boundaried graph G = (G, B, λ) is a triple consisting of a graph
G, where B is a set of vertices of degree one (called boundary) and λ is a bijection from B
to a subset of N≥1 . The edges with at least one endpoint in B are called boundary edges.
We define E s (G) as the subset of E(G) of boundary edges. We stress that instead of N≥1
we could choose any other set of symbols to label the vertices of B. We denote the set of
labels of G by Λ(G) = λ(B). Given a finite collection of connected graphs H, we say that a
boundaried graph G is H-free if G \ B is H-free.
Two boundaried graphs G1 and G2 are compatible if Λ(G1 ) = Λ(G2 ). Let now G1 =
(G1 , B1 , λ1 ) and G2 = (G2 , B2 , λ2 ) be two compatible boundaried graphs. We define the
graph G1 ⊕G2 as the non-boundaried graph obtained by first taking the disjoint union of G1
−1
and G2 , then, for every i ∈ Λ(G1 ), identifying λ−1
1 (i) with λ2 (i), and finally dissolving all
resulting identified vertices. Suppose that e is an edge of G = G1 ⊕G2 that was created after
dissolving the vertex resulting from the identification of a vertex v1 in B1 and a vertex v2 in
B2 and that ei is the boundary edge of Gi that has vi as endpoint, for i = 1, 2.
Figure 1 shows the result of the operation ⊕ on two graphs. Boundaries are drawn in
gray and their labels are written next to them. The graphs G1 and G2 on this picture are
compatible as Λ(G1 ) = Λ(G2 ) = {0, 1, 2, 3}.
For every t ∈ N≥1 , we denote by Bt all boundaried graphs whose boundary is labeled by
numbers in J1, tK. Given a boundaried graph G = (G, B, λ) and a subset S of V (G) such
that all vertices in S have degree 2 in G, we define diss(G, S) as the graph Ĝ = (Ĝ, B, λ)
where Ĝ = diss(G, S).
Let W be a graph and S be a non-empty subset of V (W ). An S-splitting of W is a pair
(GS , GS c ) consisting of two boundaried graphs GS = (GS , BS , λS ) and GS c = (GS c , BS c , λS c )
that can be obtained as follows: First, let W + be the graph obtained by subdividing in W

6

0

2

1

1

=

⊕

G1

2

0

3

3
G2

G

Figure 1: Gluing graphs together: G = G1 ⊕ G2 .
every edge with one endpoint in S and the other in V (W ) \ S and let B be the set of
created vertices. Let λ be any bijection from B to a subset of N≥1 . Then GS = W + [S ∪ B],
GS c = W + \ S, BS = BS c = B, and λS = λS c = λ. Notice that there are infinite such pairs,
depending on the numbers that will be assigned to the boundaries of GS and GS c . Moreover,
keep in mind that all the boundary edges of GS are non-loop edges with exactly one endpoint
in B and the same holds for the boundary edges of GS c . An example of a splitting is given
in Figure 2, where boundaries are depicted by gray vertices.
5

5
3
3 6

GS

W

6

GS c

Figure 2: Cutting a graph: (GS , GS c ) is an S-splitting of W , where S consists of all the
white vertices.
We say that G′ = (G′ , B ′ , λ′ ) is a boundaried subgraph of G = (G, B, λ) if G′ is a
subgraph of G, B ′ ⊆ B ∩ V (G′ ) and λ′ = λ|B ′ . On the other hand, G is a subgraph of a
(non-boundaried) graph H if G = HS for some S-splitting (HS , HS c ), where S ⊆ V (H).
If H is a graph, G is a subgraph of H, and F = (F, B, λ) is a boundaried subgraph of H,
we define G ∩H F as follows. Let S = V (G) ∩ (V (F ) \ B) and let G+ be the graph obtained
by subdividing once every edge of G that has one endpoint in S and the other in V (G) \ S.
We call B ′ the set of created vertices and let G′ = G+ [S ∪ B ′ ]. Then G′ is a subgraph of
F where B ′ ⊆ B. For every v ∈ B ′ , we set λ′ (v) = λ(v), which is allowed according to the
previous remark. Then G ∩H F = (G′ , B ′ , λ′ ). Observe that G ∩H F is part of an S-splitting
of G (but not necessarily of H).
Given two boundaried graphs G′ = (G′ , B ′ , λ′ ) and G = (G, B, λ), we say that they are
isomorphic if there is an isomorphism from G′ to G that respects the labelings of B and B ′ ,
i.e., maps every vertex x ∈ B ′ to λ−1 (λ′ (x)) ∈ B. Given a boundaried graph G = (G, B, λ),
we denote n(G) = n(G) − |B| and m(G) = m(G).
Given a boundaried graph G = (G, B, λ) and an x ∈ {v, e}, we set Ax (G) = V (G) \ B or
Ax (G) = E(G), depending on whether x = v or x = e.
7

Partial structures. Let H be a family of graphs. A boundaried subgraph J of a boundaried
graph G is a partial H-subdivision if there is a boundaried graph H which is compatible with
G and a boundaried subgraph J′ of H which is compatible with J such that J ⊕ J′ is an
H-subdivision of G⊕H. Intuitively, this means that J can be extended into an H-subdivision
in some larger graph. In this case, the H-subdivision J ⊕ J′ is said to be an extension of J.
Similarly, for every p ∈ N≥1 , a collection of boundaried subgraphs J = {J1 , . . . , Jp } of a
graph G is a partial x-H-packing if there is a boundaried graph H which is compatible with G
and a collection of boundaried subgraphs {J′1 , . . . , J′p } of H such that {J1 ⊕ J′1 , . . . , Jp ⊕ J′p }
is an x-H-packing of G ⊕ H. The obtained packing is said to be an extension of the partial
packing J . A partial packing is H-free if none of its members (the boundaried graphs
{J1 , . . . , Jp }) has an H-subdivision. Observe that if the graphs in H are connected, then
every partial subdivision of an H-free partial x-H-packing in G must contain at least one
boundary vertex of G.
Partitions and protrusions. A rooted tree-partition of a graph G is a triple D = (X , T, s)
where (T, s) is a rooted tree and X = {Xt }t∈V (T ) is a partition of V (G) where either n(T ) = 1
or for every {x, y} ∈ E(G), there exists an edge {t, t′ } ∈ E(T ) such that {x, y} ⊆ Xt ∪ Xt′
(see also [11, 20, 37]). Given an edge f = {t, t′ } ∈ E(T ), we define Ef as the set of edges of
G with one endpoint in Xt and the other in Xt′ . Notice that all edges in Ef are non-loop
edges. The width of D is defined as
max{|Xt |t∈V (T ) } ∪ {|Ef |f ∈E(T ) }.
The tree-partition width of G is the minimum width over all tree-partitions of G and will be
denoted by tpw(G). The elements of X are called bags.
In order to decompose graphs along edge cuts, we introduce the following edge-counterpart
of the notion of (vertex-)protrusion introduced in [4, 5].
Given a rooted tree-partition D = (X , T, s) of G and a vertex i ∈ V (T ), we define Ti as
the subtree of T induced by the descendants of i (including i) and
[
Xh , and Gi = G[Vi ].
Vi =
h∈V (Ti )

Let W be a graph and t ∈ N≥1 . A pair P = (G, D) is a t-partitioned protrusion of W if
there exists an S ⊆ V (W ) such that

• G = (G, B, λ) is a boundaried graph where G ∈ Bt and G = GS for some S-splitting
(GS , GS c ) of W and
• D = (X , T, s) is a rooted tree-partition of G \ B of width at most t, where Xs are the
neighbors in G of the vertices in B.

We say that a t-partitioned protrusion (G, D) (with D = ({Xu }u∈V (T ) , T, s)) of a graph W
is H-free if G is H-free. Recall that in the rooted tree-partition D, for every u ∈ V (T ), we
denote by Vu the union of the bags indexed by descendants of u (including u). For every
vertex u ∈ V (T ), we define the t-partitioned protrusion Pu of W as a pair Pu = (Gu , Du ),
where Du = ({Xv }v∈VTu , Tu , u) and Gu is defined as GVu for some Vu -splitting (GVu , GVuc )
of W . Informally speaking, the rooted tree-partition Du is the part of D corresponding to the
subgraph of G induced by vertices in the bags that are descendants of u. Figure 3 provides
an example of partitioned protrusions. We choose the labeling function of Gs so that it is the
same as the one of G, i.e., Gs = G. Notice that the labelings of all other Gu ’s are arbitrary.
For every u ∈ V (T ) we define
Gu = {Gl | l ∈ children(T,s) (u)}.
8

D
Du

B

s

u

Xs

Xu

Gu
G
W
Figure 3: The partitioned protrusion Pu = (Gu , Du ) as a substructure of (G, D). White
circles represent bags of the rooted tree-partitions. Only the edges between B and Xs are
depicted

2.3

Encodings, signatures, and folios

In this section we introduce tools that we will use to sort boundaried graphs depending on
the subdivisions that are realizable inside.
Encodings. Let H be a family of graphs, let t ∈ N≥1 , and let x ∈ {v, e}. Recall that if M
is an H-subdivision in G, we denote by M̂ a graph isomorphic to some graph of H such that
M is a subdivision of M̂ (see Subsection 2.1). If G = (G, B, λ) ∈ Bt is a boundaried graph
and S ⊆ Ax (G), we define µxH (G, S) as the collection of all sets {(J1 , L1 ), . . . , (Jσ , Lσ )} such
that
(i) {J1 , . . . , Jσ } is a partial x-H-packing of G \ S of size σ and
(ii) Li = V (M̂i ) ∩ V (G), where Mi is an extension of Ji , for every i ∈ J1, σK.

F

G

H = {K4 , K2,3 }

Figure 4: A member of P≥1
e,H (F ⊕ G). Branch vertices are circled.

9

J

Figure 5: A partial subdivision from the packing of Figure 4. Branch vertices are circled.
In other words, Li contains branch vertices of the partial subdivision Ji for every i ∈ J1, σK
(see Figures 4 and 5). The set µxH (G, S) encodes all different restrictions in G of partial
x-H-packings that avoid the set S. Given a boundaried graph G = (G, B, λ) and a set
L ⊆ V (G) such that every vertex of V (G) \ L has degree 2 in G, we define κ(G, L) as the
boundaried graph obtained from G by dissolving every vertex of V (G) \ L, i.e., κ(G, L) =
(diss(G, V (G) \ L), B, λ). In the definition of κ we assume that the boundary vertices of
κ(G, L) remain the same as in G while the other vertices are treated as new vertices (see
Figure 6).

Ĵ

Figure 6: The compression of the partial packing of Figure 5: Ĵ = κ(J, L).
This allows us to introduce the following notation aimed at representing, intuitively, the
essential part of each partial packing.
µ̂xH (G, S) =

{Jˆ = {Ĵ1 , . . . , Ĵσ } = {κ(J1 , L1 ), . . . , κ(Jσ , Lσ )} |
{(J1 , L1 ), . . . , (Jσ , Lσ )} ∈ µH (G, S)}.

Isomorphisms. If G = (G, B, λ) and G′ = (G′ , B ′ , λ′ ) are two compatible boundaried
graphs in Bt , S ∈ V (G), and S ′ ∈ V (G′ ), we say that a member Jˆ of µ̂xH (G, S) and a
member Jˆ′ of µ̂xH (G′ , S ′ ) are isomorphic if there is a bijection between them such that
paired elements are isomorphic. We also say that µ̂xH (G, S) and µ̂xH (G′ , S ′ ) are isomorphic
if there is a bijection between them such that paired elements are isomorphic.
We now come to the point where we can define, for every boundaried graph, a signature
encoding all the possible partial packings that can be realized in this graph.
Signatures and folios. For every y ∈ N, we set
sigxH (G, y) =

{µ̂xH (G, S), S ⊆ Ax (G), |S| = y}

and, given two compatible t-boundaried graphs G and G′ and a y ∈ N, we say that sigxH (G, y)
and sigxH (G′ , y) are isomorphic if there is a bijection between them such that paired elements
are isomorphic.
Finally, for ρ ∈ N, we set
folioH,ρ (G)

=

(sigvH (G, 0), . . . , sigvH (G, ρ), sigeH (G, 0), . . . , sigeH (G, ρ)).
10

Given two t-boundaried graphs G and G′ , a ρ ∈ N, and a finite collection of connected
graphs H, we say that G ≃H,ρ G′ if G and G′ are compatible, neither G nor G′ contains an
H-subdivision, and the elements of folioH,ρ (G) and folioH,ρ (G′ ) are position-wise isomorphic.

3

The reduction

The purpose of this section is to prove the following lemma.
Lemma 1. There exists a function f2 : N2 → N and an algorithm that, given a positive
integer t, a finite collection H of connected graphs where h = m(H), and a t-partitioned
protrusion P = (G, (X , T, s)) of a graph W with n(G) > f2 (h, t), outputs either
• an H-subdivision of W with at most f2 (h, t) edges or
• a graph W ′ such that
x-packH (W ′ ) = x-packH (W ),
x-coverH (W ′ ) = x-coverH (W ), and
n(W ′ ) < n(W ).
Furthermore, this algorithm runs in time Ot,h (n(T )). Moreover, this algorithm can be enhanced so that given a x-H-packing (resp. x-H-covering) in W ′ then it outputs a same size
x-H-packing (resp. x-H-covering) in W .
In other words we can, in linear time, either find a small H-subdivision, or reduce the
graph to a smaller one where the parameters of packing and covering stay the same. The
main lines of the proof are the following. We consider the equivalence relation ≃H,t on H-free
t-partitioned protrusions. Informally, ≃H,t relates the partitioned protrusions in which the
same partial packings are realizable. The first step is to show that this relation has a finite
number of equivalence classes. Recall that each vertex i of the tree T of the partitioned
protrusion P defines a partitioned protrusion Pi . We then show that if T is too large (i.e.
it has a long path or a vertex of large degree), then for several vertices, such partitioned
protrusions belong to the same equivalence class of ≃H,t . We finally show that in this case,
some of these vertices can be deleted without changing the packing and covering numbers.
Before giving the proof of Lemma 1, we need to prove several intermediate results. In
the sequel, unless stated otherwise, we assume that x ∈ {v, e}, t ∈ N≥1 and that H is a finite
collection of connected graphs. We set h = m(H). Recall that, for a t-partitioned protrusion
(G, (X , T, s)) of a graph W , and v ∈ V (T ), we denote by Gv the set of all boundaried graphs
of the form GVu , for some Vu -splitting (GVu , GVuc ) of W , where u is a child of v. Informally,
these are the boundaried graphs induced by the bags of the subtrees of T rooted at the
children of v.
Lemma 2. There are two functions f3 : N2 → N and f4 : N2 → N such that, for every
graph W and every t-partitioned protrusion (G, (X , T, s)) of W , if P is an H-free partial
x-H-packing in G then:
(a) The partial subdivisions of graphs in H that are contained in P have in total at most
f3 (h, t) branch vertices.
(b) P intersects at most f4 (h, t) graphs of Gs .

11

Proof. Proof of (a). First, note that any H-free partial x-H-packing in G has cardinality
at most t, because each partial subdivision it contains must use a boundary edge of G, and
two distinct subdivisions of the same packing are (at least) edge-disjoint. Also, each of these
partial subdivisions contains at most maxH∈H n(H) ≤ h branch vertices. Consequently,
for every H-free partial x-H-packing in G, the number of branch vertices of graphs of H it
induces in G is at most t · h. Hence the function f3 (h, t) := t · h upper-bounds the amount
of branch vertices each H-free partial packing can contain.
Proof of (b). Let ζ be the maximum multiplicity of an edge in a graph of H. Because of (a),
every H-free partial x-H-packing P in G has at most f3 (h, t) branch vertices of graphs of H, so
at most f3 (h, t) graphs of Gs may contain such vertices. Besides, P might also contain paths
free of branch vertices linking pairs of branch vertices. Since there are at most (f3 (h, t))2
such pairs and no pair will need to be connected with more than ζ ≤ h distinct paths, it
follows that at most (f3 (h, t))2 · h graphs of Gs contain vertices from these paths. Therefore,
every H-free partial x-H-packing intersects at most f3 (h, t) + (f3 (h, t))2 · h =: f4 (h, t) graphs
of Gs .
Lemma 3. There is a function f5 : N2 → N such that the image of the function µ̂xH , when
its domain is restricted to
{(G, S), G is H-free and S ⊆ Ax (G)},
has size upper-bounded by f5 (h, t).
Proof. Let G be an H-free t-boundaried graph and let S ⊆ Ax (G). From Lemma 2(a), every
H-free partial x-H-packing in G contains at most f3 (h, t) branch vertices. This partial
packing can in addition use at most t boundary vertices. Let Ch,t be the class of all (≤ t)boundaried graphs on at most f3 (h, t) + t vertices. Clearly the size of this class is a function
depending on h and t only. Recall that the elements of the set µ̂xH (G, S) are obtained
from partial x-H-packings by dissolving internal vertices of the paths linking branch vertices,
hence every element of µ̂xH (G, S) is a t-boundaried graph of Bt having at most f3 (h, t) + t
vertices. Therefore, for any H-free t-boundaried graph G and subset S ⊆ Ax (G), we have
µ̂xH (G, S) ⊆ Ch,t . As a consequence, the image of the function µ̂xH when restricted to H-free
t-boundaried graphs G ∈ Bt (and subsets S ⊆ Ax (G)) is a subset of the power set of Ch,t , so
its size is upper-bounded by a function (which we call f5 ) that depends only on h and t.
Corollary 1. There is a function f6 : N2 → N such that the relation ≃H,t partitions H-free
t-boundaried graphs into at most f6 (h, t) equivalence classes.
The following lemma follows directly from the definition of µ̂xH .
Lemma 4. Let F, G ∈ Bt be two compatible t-boundaried graphs and let k ∈ N. Then we
have:
≥k
x
ˆ
ˆ
P≥k
x,H (F ⊕ G) 6= ∅ ⇐⇒ ∃J ∈ µ̂H (G, ∅), Px,H (F ⊕ ∪ J ) 6= ∅.

The choice of the definition of the relation ≃ is justified by the following lemma. Roughly
speaking, it states that we can replace a t-partitioned protrusion of a graph with any other
≃H,t -equivalent t-partitioned protrusion without changing the covering and packing number
of the graph. The reduction algorithm that we give after this lemma relies on this powerful
property.
Lemma 5 (protrusion replacement). Let F, G, G′ ∈ Bt be three compatible boundaried graphs
such that G ≃H,t G′ . For every k ∈ N, we have:
12

≥k
′
(i) P≥k
x,H (F ⊕ G) 6= ∅ ⇐⇒ Px,H (F ⊕ G ) 6= ∅ and
≤k
′
(ii) C≤k
x,H (F ⊕ G) 6= ∅ ⇐⇒ Cx,H (F ⊕ G ) 6= ∅.

Proof. Notice that, by definition of ≃,t , the boundaried graphs G and G′ are H-free.
Proof of item (i), “⇒”. Let M be an x-H-packing of size at least k in F ⊕ G, whose set of
branch vertices is L. We define
JF
JG

=
=

ĴG

=

∪ M) ∩F⊕G F,
(∪
∪ M) ∩F⊕G G, and
(∪
[
κ(M ∩F⊕G G, L ∩ V (G)).

M∈M

Note that ĴG ∈ µ̂xH (G, ∅) and that F⊕ĴG has an x-H-packing of size at least k (cf. Lemma 4).
By definition of ≃, there is a bijection ψ between µ̂xH (G, ∅) and µ̂xH (G′ , ∅). Let Ĵ′G be the
image of ĴG by ψ. Since Ĵ′G and ĴG are isomorphic, F ⊕ Ĵ′G also has an x-H-packing of
size at least k. By Lemma 4, this implies that such a packing exists in F ⊕ G′ as well. The
direction “⇐” is symmetric as G and G′ play the same role.
Proof of item (ii), “⇒”. Let C ⊆ Ax (F ⊕ G) be a minimum x-H-covering of F ⊕ G of size
at most k. Let S = C ∩ Ax (G). Since we assume that G is H-free and that C is minimum,
we can also assume that |S| ≤ t (otherwise we could get a smaller covering by taking the t
boundary vertices/edges of G). By our assumption that G ≃H,t G′ , there is an isomorphism
between sigxH (G, |S|) and sigxH (G′ , |S|). Let S ′ ⊆ Ax (G′ ) be a set such that µ̂xH (G, S) is sent
to µ̂xH (G′ , S ′ ) by this isomorphism. Then observe that every partial packing J ′ of G′ \ S ′ ,
∪ J ′ ) has an H-subdivision, can be translated into a partial packing J
such that (F \ C) ⊕ (∪
∪ J ) also has such a subdivision, in the same way as in the proof
of G\ S such that (F \ C) ⊕ (∪
of item (i) above. As C is a cover, this would lead to contradiction. Therefore µxH (G, S)
does not contain such a partial packing. As a consequence, (C ∩ Ax (F)) ∪ S ′ is a covering of
F ⊕ G′ of size at most k. As in the previous case, the proof of direction “⇐” comes from the
symmetry in the statement.
Lemma 5 can be rewritten as follows.
Corollary 2. Under the assumptions of Lemma 5, we have x-pack(F ⊕ G) = x-pack(F ⊕ G′ )
and x-cover(F ⊕ G) = x-cover(F ⊕ G′ ).
Recall that f6 (h, t) denotes the number of equivalence classes of ≃H,t among boundaried
graphs of Bt . For every h, t ∈ N, let
f7 (h, t) = f6 (h, t) · f4 (h, t)

and f2 (h, t) = 2ht3 · (f3 (h, t))

f6 (h,t)+1

.

Let us give some intuition about these definitions. The first remark is an application of the
pigeonhole principle.
Observation 1. In a collection of more than f3 (h, t) H-free boundaried graphs of Bt , there
is one that is equivalent (w.r.t. ≃H,t ) to f4 (h, t) other graphs of the collection.
Observation 2. If (T, s, X ) is a rooted tree-partition of a graph G with the following properties:
• (T, X ) has width at most t;
• T has height at most f6 (h, t); and
13

• T has degree at most f3 (h, t) + 1,
then G has at most f2 (h, t) vertices, and every H-subdivision of G has at most f2 (h, t) edges.
f (h,t)+1
Proof. The above assumptions imply that T has at most (f3 (h, t)) 6
vertices. Every
f (h,t)+1
·t ≤
bag of (T, X ) contains at most t vertices of G, therefore G has at most (f3 (h, t)) 6
f2 (h, t) vertices. Also, every bag induces a subgraph with at most t(t − 1)/2 multiedges (i.e.
without counting multiplicities), and for every edge f of T we have |Ef | ≤ t, hence every bag
f (h,t)+1
contributes for at most t2 + t multiedges. Therefore G has at most (t + t2 ) (f3 (h, t)) 6
multiedges. Now, observe that an edge of G is used at most h times by an H-subdivision
(if it is a multiple edge), since every path connecting two branch vertices of a subdivision
uses a given edge at most once. We deduce that an H-subdivision of G contains at most
f (h,t)+1
h · (t + t2 ) (f3 (h, t)) 6
≤ f2 (h, t) edges.
The two next lemmas are the main tools used in the proof of Lemma 1. Under different
conditions, they provide either a small subdivision, or a reduced graph. Lemma 6 considers
the case where a vertex of T has high degree, whereas Lemma 7 deals with the situation
where T has a long path.
Lemma 6. Let P = (G, (X , T, s)) be a t-partitioned protrusion of a graph W , and let
u ∈ V (T ) be a vertex with more than f3 (h, t) children such that for every v ∈ children(T,s) (u),
we have m(Gv ) ≤ f6 (h, t). Then, either
• W contains an H-subdivision M with at most f6 (h, t) edges or
• there exists a graph W ′ such that
x-packH (W ′ ) = x-packH (W ),
x-coverH (W ′ ) = x-coverH (W ), and
n(W ′ ) < n(W ).
Moreover, there is an algorithm that, given such P, W, and u, returns either M or W ′ as
above in Oh,t (1) steps.
Proof. As u has more than f3 (h, t) children, it contains a collection of d = f4 (h, t) + 1
children v1 , . . . , vd , such that Gv1 ≃H,t Gvi for every i ∈ J2, dK (by Observation 1). Let us
now assume that Gu is H-free. Since every x-H-packing of W will intersect at most f4 (h, t)
bags of children of u (by Lemma 2(b)), we can safely delete one of the f4 (h, t) + 1 equivalent
subgraphs mentioned above. We use the following algorithm in order to find such a bag to
delete or a small H-subdivision.
1. Let A be an array of f6 (h, t) counters initialized to 0, each corresponding to a distinct
equivalence class of ≃H,t ;
2. Pick a vertex v ∈ children(T,s) (u) that has not been considered yet;
3. If Gv contains an H-subdivision M, then return M and exit;
4. Otherwise, increment the counter of A corresponding to the equivalence class of Gu by
one;
5. If this counter reaches d + 1, return v, otherwise go back to Line 2.

14

Notice that the subdivision returned in Line 3 has size at most t · f6 (h, t) (as we assume
that m(Gv ) ≤ f6 (h, t)) and that the vertex returned in Line 5 has the desired property. By
Corollary 1, the relation ≃H,t has at most f6 (h, t) equivalence classes, thus the main loop will
be run at most f6 (h, t) · f4 (h, t) + 1 times (by the pigeonhole principle). Eventually, Lines 3
and 4 can be performed in Oh,t (1)-time given that Gv has size bounded by a function of h
and t.
In the end, we return W ′ = W \ V (Gv ) if the algorithm outputs v and M otherwise.
Lemma 7. There is an algorithm that, given a t-partitioned protrusion P = (G, (X , T, s))
of a graph W and a vertex u ∈ V (T ) such that
• u has height exactly f6 (h, t) in (T, s),
• the graph of Gu is H-free, and
• Tu has maximum degree at most f3 (h, t),
outputs a graph W ′ such that
x-packH (W ′ ) = x-packH (W ),
x-coverH (W ′ ) = x-coverH (W ), and
n(W ′ ) < n(W ).
Moreover, this algorithm runs in Oh,t (1)-time.
Proof. As in the proof of Observation 2, we use the fact that every H-subdivision of Gu uses
every (multi)edge at most h times. A consequence is that the boundaried subgraph of Gu
obtained by setting the multiplicity of every edge e to the minimum of h and the multiplicity
of e contains an H-subdivision iff Gu does. As the number of vertices and edges of this
subgraph is bounded by a function of h and t, we can therefore check in Oh,t (1)-time if Gu
contains an H-subdivision. If one is found, it has at most f2 (h, t) edges (Observation 2) and
we are done.
Let us now consider the case where Gu is H-free. By definition of the vertex u, there
is a path of f6 (h, t) + 1 vertices from a leaf of Tu to u. Let us arbitrarily choose, for every
vertex v of this path, a Vv -splitting (GGv , GGcv ) of G. By definition of f6 (h, t) (the number
of equivalence classes in ≃H,t in Bt ), there are two distinct vertices v, w on this path such
that Gv ≃H,t Gw . As mentioned above, the number edges of Gu is bounded by a function of
h and t, hence finding these two vertices can be done in Oh,t (1)-time. Let us assume without
loss of generality that w is a descendant of v. Let H be the boundaried graph such that
W = H ⊕ GGv and let W ′ = H ⊕ GGw . By Corollary 2, we have x-packH (W ′ ) = x-packH (W )
and x-coverH (W ′ ) = x-coverH (W ). Furthermore, the graph W ′ is clearly smaller than W .
We are now ready to prove Lemma 1.
Proof of Lemma 1. Observe that since n(G) > f2 (h, t) and each bag of (X , T, s) contains at
most t vertices, we have
f (h,t)
n(T ) > f2 (h, t)/t = (f6 (h, t) · f4 (h, t)) 6
.
Therefore, T has either diameter more than f6 (h, t) or a vertex of degree more than f6 (h, t) ·
f4 (h, t).
Let us consider the following procedure.

15

1. By a DFS on (T, s), compute the height of each vertex of T and find (if it exists)
a vertex v of degree more than f3 (h, t) + 1 and height at most f6 (h, t) − 1 that has
minimum height.
2. If such a vertex v is found, then apply the algorithm of Lemma 6 on P and v, and
return the obtained result.
3. Otherwise, find a vertex u of height exactly f6 (h, t) in (T, s) and then apply the algorithm of Lemma 7 on P and (Tu , u) and return the obtained result.
Observe that since n(G) > f2 (h, t), Observation 2 implies that either T has diameter more
than f6 (h, t), or it contains a vertex of degree more than f3 (h, t) + 1. Therefore, the vertex
u of line 3 always exists in the case where no vertex of high degree is found in line 1. The
correctness of this algorithm follows from Lemma 6 and Lemma 7. The DFS done in the first
step takes time O(n(T )) and the rest of the algorithm takes time Oh,t (1) according to the
aforementioned lemmata.
The fact that a x-H-packing of W ′ can be lifted to an equal size x-H-packing of W follows
easily when Lemma 6 is applied, as then W ′ is a subgraph of W . In the case that Lemma 7
is applied, the new x-H-packing is obtained because of Corollary 2 and the supporting protrusion replacement Lemma 5, whose proof indicates which part of the x-H-packing of W ′
should be replaced with what in order to obtain an equal size x-H-packing of W .

4

From the Erdős-Pósa property to approximation

For the purposes of this section we define Θr = ex(θr ). We need the following that is one of
the main results in [7, Theorem 3.2].
Proposition 1. There is an algorithm that, with input three positive integers r ≥ 2, w, z and
a connected m-edge graph W , where m ≥ z > r ≥ 2, outputs one of the following:
• a Θr -subdivision of W with at most z edges,
• a (2r − 2)-partitioned protrusion (G, D) of W , where G = (G, B, λ) and such that G
is a connected graph and n(G) > w, or
• an H-minor model of W for some graph H with δ(H) ≥

z−5r

1
4r(2w+1) ,
r−1 2

in Or (m) steps.

4.1

A lemma on reduce or progress

The proof of the next lemma combines Proposition 1 and Lemma 1.
Lemma 8 (Reduce or progress). There is an algorithm that, with input x ∈ {v, e}, r ∈ N≥2 ,
k ∈ N and an n-vertex graph W , outputs one of the following:
• a Θr -subdivision of W with at most Or (log k) edges;
• a graph W ′ where
x-coverH (W ′ ) = x-coverH (W ),
x-packH (W ′ ) = x-packH (W ), and
n(W ′ ) < n(W ); or
16

• an H-minor model in W , for some graph H with δ(H) ≥ k(r + 1),
in Or (m) steps. Moreover, this algorithm can be enhanced so that, when the second case
applies, given a x-H-packing (resp. x-H-covering) in W ′ then it outputs a same size x-Hpacking (resp. x-H-covering) in W .
Proof. We set t = 2r − 2, w = f2 (h, t), z = 2r(w − 1) log(k(r + 1)(r − 1))+ 5r, and h = m(Θr ).
Observe that z = Or (log k) and h, t, w = Or (1). Also observe that our choice for variable z
z−5r
ensures that 2 2r(w−1) /(r − 1) = k(r + 1).
By applying the algorithm of Proposition 1 to r, w, z, and W , we obtain in Or (m(W ))time either:
• a Θr -subdivision in W of at most z edges (first case),
• a (2r − 2)-edge-protrusion Y of W with extension > w (second case), or
• an H-minor model M in W , for some graph H with δ(H) ≥ k(r + 1) (third case).
In the first case, we return the obtained Θr -subdivision.In the second case, by applying
the algorithm of Lemma 1 on Y , we get in O(n(W ))-time either a Θr -subdivision of W on at
most w = Or (1) vertices, or a graph W ′ where, for x ∈ {v, e}, x-coverH (W ′ ) = x-coverH (W ),
x-packH (W ′ ) = x-packH (W ) and n(W ′ ) < n(W ).In the third case, we return the minor model
M.
In each of the above cases, we get after O(m) steps either a minor model of a graph with
minimum degree more than k(r + 1), a Θr -subdivision in W with at most z edges, or an
equivalent graph of smaller size.
It might not be clear yet to what purpose the minor model of a graph of degree more
than k(r + 1) output by the algorithm of Lemma 8 can be used. An answer is given by the
following lemmata, which state that such a graph contains a packing of at least k minor
models of Θr . These lemmata will be used in the design of the appoximation algorithms in
Subsection 4.2.
Lemma 9. There is an algorithm that, given k, r ∈ N≥1 and a graph G with δ(G) ≥ kr,
returns a member of P≥k
e,Θr (G) in G in O(m) steps.
Proof. Starting from any vertex u, we grow a maximal path P in G by iteratively adding to
P a vertex that is adjacent to the previously added vertex but does not belong to P . Since
δ(G) ≥ kr, any such path will have length at least kr + 1. At the end, all the neighbors of
the last vertex v of P belong to P (otherwise P could be extended). Since v has degree at
least kr, v has at least kr neighbors in P . Let w0 , . . . , wkr−1 be an enumeration of the kr
first neighbors of v in the order given by P , starting from u. For every i ∈ J0, k − 1K, let
Si be the subgraph of G induced by v and the subpath of P starting at wir and ending at
w(i+1)r−1 . Observe that for every i ∈ J0, k − 1K, Si contains a Θr -subdivision and that the
intersection of every pair of graphs from {Si }i∈J0,k−1K is {v}. Hence P contains a member of
P≥k
e,Θr (G), as desired. Every edge of G is considered at most once in this algorithm, yielding
to a running time of O(m) steps.
Corollary 3. There is an algorithm that, given r ∈ N≥1 and a graph G with δ(G) ≥ r,
returns a Θr -subdivision in G in O(m)-steps.
Observe that the previous lemma only deals with edge-disjoint packings. An analogue of
Lemma 9 for vertex-disjoint packings can be proved using Proposition 2, to the price of a
worse time complexity.
17

Proposition 2 (Theorem 12 of [2]). Given k, r ∈ N≥1 and an input graph G such that
δ(G) ≥ k(r + 1) − 1, a partition (V1 , . . . , Vk ) of V (G) satisfying ∀i ∈ J1, kK , δ(G[Vi ]) ≥ r can
be found in O(nc ) steps for some c ∈ N.
Lemma 10. There is an algorithm that, given k, r ∈ N≥1 and a graph G with δ(G) ≥
c
k(r + 1) − 1, outputs a member of P≥k
v,Θr (G) in O(n + m) steps, where c is the constant of
Proposition 2.
Proof. After applying the algorithm of Proposition 2 on G to obtain in O(nc )-time k graphs
G[V1 ], . . . , G[Vk ], we extract a Θr -subdivision from each of them using Corollary 3.

4.2

Approximation algorithms

As Θr -subdivisions are exactly the subgraph minimal graphs that contain Θr as a minor, a
graph has a Θr -x-packing of size k iff it contains k x-disjoint subgraphs, each containing θr
as a minor. Therefore, Theorem 1 is a direct combinatorial consequence of the following.
Theorem 5. There is a function f8 : N → N and an algorithm that, with input x ∈ {v, e},
r ∈ N≥2 , k ∈ N, and an n-vertex graph W , outputs either a x-Θr -packing of W of size k or
an x-Θr -covering of W of size at most f8 (r)·k ·log k. Moreover, this algorithm runs in O(m2 )
steps if x = e and in Or (nc + n · m) steps if x = v, where c is the constant from Proposition 2.
Proof. Let f8 (r) : N → N be a function such that each Θr -subdivision output by the algorithm
of Lemma 8 has size at most f8 (r) · log k. We consider the following procedure.
1. G := W ; P := ∅;
2. Apply the algorithm of Lemma 8 on (x, r, k, G):
Progress: if the output is a Θr -subdivision M , let G := G \ Ax (M ) and P = P ∪ {M };

Win: if the output is a H-minor model M in W for some graph H with δ(H) ≥ k(r+1),
apply the algorithm of Lemma 9 (if x = e) or the one of Lemma 10 (if x = v) to H
to obtain a member of P≥k
x,Θr (H). Using M , translate this packing into a member
(W
)
and
return
this
new packing;
of P≥k
x,Θr
Reduce: otherwise, the output is a graph G′ . Then let G := G′ .
3. If |P | = k then return P which is a member of P≥k
x,Θr (W );
≤f (r) log k
(W );
4. If n(W ) = 0 then return P which is in this case a member of Cx,Θ8r

5. Otherwise, go back to Line 2.
This algorithm clearly returns the desired result. Furthermore, the loop is executed at most
|Ax (W )| times (as an element of Ax (W ) is deleted each time we reach the Progress case) and
each call to the algorithm of Lemma 8 takes O(m(W )) steps. When the algorithm reaches
the “Win” case (which can happen at most once), the calls to the algorithm of Lemma 9 (if
x = e) or the one of Lemma 10 (if x = v), respectively, take O(m(H)) and O ((n(H))c ) steps.
Therefore, in total, this algorithm terminates in O(m2 ) steps if x = e and in O (nc + n · m)
steps if x = v.
Observe that if the algorithm of Theorem 5 reaches the “Win” case, then the input graph
is known to contain an x-Θr -packing of size at least k. As a consequence, if we are only
interested in the existence of a packing or covering, the call to the algorithm of Lemma 9 or
Lemma 10 is not necessary.
18

Corollary 4. There is an algorithm that, with input x ∈ {v, e}, r ∈ N≥2 , k ∈ N, and a graph
W , outputs 0 only if W has an x-Θr -packing of size k or 1 only if W has an x-Θr -covering
of size at most f8 (r) · k · log k. Furthermore this algorithm runs in Or (n · m) steps when x = v
and in Or (m2 ) steps when x = e.
We now conclude this section with the proof of Theorem 2. For the same reason as in
the proof of Theorem 1 at the beginning of this section, we can deal with Θr -subdivisions
instead of dealing with subgraphs that contain θr as a minor.
Proof of Theorem 2. Let us call A the algorithm of Corollary 4. Let k0 ∈ J1, n(W )K be an
integer such that A(x, r, k0 , W ) = 1 and A(x, r, k0 − 1, W ) = 0, and let us show that the value
f8 (r) · k0 log k0 is an O(log OP T )-approximation of x-packΘr (W ) and coverΘr (W ).
First, notice that for every k > x-packΘr (W ), the value returned by A(x, r, k,
W ) is 1. Symmetrically, for every k such that f8 (r) · k log k < x-coverΘr (W ), the value of
A(x, r, k, W ) is 0. Therefore, the value k0 is such that:
k0 − 1 ≤ x-packΘr (W ) and
x-coverΘr (W ) ≤ f8 (r) · k0 log k0 .
As every minimal covering must contain at least one vertex or edge (depending on whether
x = v or x = e) of each element (i.e. subdivision) of a maximal packing x-packΘr (W ) ≤
x-coverΘr (W ), we have the following two equations:
x-packΘr (W ) ≤ f8 (r) · k0 log k0 ≤ (x-packΘr (W ) + 1) log(x-packΘr (W ) + 1)
x-coverΘr (W ) ≤ f8 (r) · k0 log k0 ≤ (x-coverΘr (W ) + 1) log(x-coverΘr (W ) + 1).

(1)
(2)

Dividing (1) by x-packΘr (W ) and (2) by coverΘr (W ), we get:
1≤

log x-packΘr (W )
k0 log k0
≤ log(x-packΘr (W ) + 1) +
x-packΘr (W )
x-packΘr (W )
= O(log(x-packΘr (W ))),

1≤

and

k0 log k0
log x-coverΘr (W )
≤ log(x-coverΘr (W ) + 1) +
x-coverΘr (W )
x-coverΘr (W )
= O(log(x-coverΘr (W ))).

Therefore the value k0 log k0 is both an O(log OP T )-approximation of x-packΘr (W ) and
coverΘr (W ). The value k0 can be found by performing a binary search in the interval J1, nK,
with O(log n) calls to Algorithm A. Hence, our approximation algorithm runs in O(n · log(n) ·
m) steps when x = v and in O(m2 · log(n)) steps when x = e.

5

Erdős–Pósa property and tree-partition width

Using the machinery introduced in Section 3, we are able to prove a slightly more general
version of Theorem 3.
Theorem 6. Let t ∈ N. For every x ∈ {v, e}, the following holds: if H is a finite collection of
connected graphs and G is a graph of tree-partition width at most t, then x-coverH (G) ≤ α · xpackH (G), where α is a constant which depends only on t and H.

19

Proof. Let k = x-packH (G). This proof is similar to that of Theorem 5 (progress or reduce).
We start with P := ∅ and G0 := G and repeatedly apply Lemma 1 to Gi , which provides
the existence of either a smaller graph Gi+1 with the same parameters x-coverH and x-packH
(reduce), or that of an H-subdivision M with at most f2 (h, t) edges, in which case we set
Gi+1 := Gi \ Ax (M ) and P := P ∪ {M } (progress) and continue. Notice that while the
algorithm of Lemma 1 requires a t-partitioned protrusion, it is enough here to know that
such a partitioned protrusion exists as we do not actually run the algorithm. This is the case
because the considered graphs are subgraph of G, which has tree-partition width at most t, so
we can consider a t-partitioned protrusion containing the whole graph. We stop this process
when the current graph has at most f2 (h, t) vertices. Let Gj be this graph. In the end, P
contains at most k H-subdivisions. Therefore, C := ∪ Ax (P ) ∪ Ax (Gj ) is an x-H-covering of
G of size (k + 1) · f2 (h, t), as required.
Theorem
S 3 can be obtained from Theorem 6 by considering packing and covering of the
graphs in H∈H ex(H), where H is the family of graphs mentioned in the statement of
Theorem 3.
We define Θr,r′ = ex(θr,r′ ). The rest of this section is devoted to the proof of Theorem 4.
Prior to this, we need to introduce a result of Ding et al. [11].
Tree-partition width has been studied in [11, 20, 37]. In particular, the authors of [11]
characterized the classes of graphs of bounded tree-partition width in terms of excluded
topological minors. The statement of this result requires additional definitions.
Walls, fans, paths, and stars.
edge set is:

The n-wall is the graph with vertex set J1, nK 2 and whose

{{(i, j), (i, j + 1)}, 1 ≤ i, j ≤ n}

∪ {{(2i − 1, 2j + 1), (2i, 2j + 1)}, 1 < 2i ≤ n and 1 ≤ 2j + 1 ≤ n}
∪ {{(2i, 2j), (2i + 1, 2j)}, 1 ≤ 2i < n and 1 ≤ 2j ≤ n} .
The 7-wall is depicted in Figure 7. The n-fan is the graph obtained by adding a dominating
vertex to a path on n vertices. A collection of paths is said to be independent if two paths
of the collection never share interior vertices. The n-star is the graph obtained by replacing
every edge of K1,n with n independent paths of two edges. The n-path is the graph obtained
by replacing every edge of an n-edge path with n independent paths of two edges. Examples
of these graphs are depicted in Figure 7. The wall number (resp. fan number, star number,
and path number ) of a graph G is defined as the largest integer k such that G contains a
minor model of a k-wall (resp. of a k-fan, of a k-star, of a k-path), or infinity is no such
integer exists. Let γ(G) denote the maximum of the wall number, fan number, star number,
and path number of a graph G.
We need the following result.
Proposition 3 ([11]). There is a function f9 : N → N such that every graph G satisfies
tpw(G) ≤ f9 (γ(G)).
In other words, for every integer k, every graph of large enough tree-partition width
contains a minor model of one of the following graphs: the k-wall, the k-fan, the k-path, or
the k-star.
Notice that for every r, r′ ∈ N, r′ ≤ r, the graph θr,r′ is a minor of the following graphs:
the r-path, the r-star, the (r + r′ + 1)-fan, and the r-wall (for r ≥ 6). Hence, every graph of
large enough tree-partition width contains a Θr,r′ -subdivision. This can easily be generalized
to edge-disjoint packings, as follows.
20

7-fan
7-wall

4-path

4-star

Figure 7: Unavoidable patterns of graphs of large tree-partition width.
Lemma 11. For every r, r′ ∈ N, r′ ≤ r, and every k ∈ N≥1 , every graph G satisfying
γ(G) ≥ k(r + r′ + 2) − 1 contains an e-Θr,r′ -packing of size k.
Using Proposition 3, we get the following corollary.
Corollary 5. For every r, r′ ∈ N, r′ ≤ r, and every k ∈ N≥1 , every graph G satisfying
tpw(G) ≥ f9 (k(r + r′ + 2) − 1) contains an e-Θr,r′ -packing of size k.
We are now able to give the proof of Theorem 4. As in the proof of Theorem 1 at the
beginning of Subsection 4.2, we can consider Θr,r′ -subdivisions instead of sugraphs containing
θr,r′ as a minor.
Proof of Theorem 4. According to Corollary 5, for every k ∈ N, there is a number tk such that
every graph G with e-coverΘr,r′ (G) = k satisfies tpw(G) ≤ tk . Indeed, such a graph does not
contain a packing of k + 1 Θr,r′ -subdivisions. Then by Theorem 3 the value e-coverΘr,r′ (G)
is bounded above by f2 (h, tk ) · e-packΘr,r′ (G), and this concludes the proof.

6

Concluding remarks

The main algorithmic contribution of this paper is a log(OPT)-approximation algorithm for
the parameters v-packθr , v-coverθr , e-packθr , and e-coverθr , for every positive integer r. This
improves the results of [21] in the case of vertex packings and coverings and is the first
approximation algorithm for the parameters e-packθr and e-coverθr for general r. Our proof
uses a reduction technique of independent interest, which is not specific to the graph θr and
can be used for any other (classes of) graphs.
On the combinatorial side, we optimally improved the gap of the edge-Erdős-Pósa property of minor models of θr for every r. Also, we were able to show that every class of
graphs has the (edge and vertex) Erdős-Pósa property in graphs of bounded tree-partition
width, with linear gap. An other outcome of this work is that minor models of θr,r′ have the
21

edge-Erdős-Pósa. Recall that prior to this work, the only graphs for which this was known
were θr ’s.
As mentioned in [32], the planarity of a graph H is a necessary condition for the minor
models of H to have the edge-Erdős-Pósa property. However, little is known on which
planar graphs have this property and with which gap. This is the first direction of research
that we want to highlight here. Also, the question of an approximation algorithm can be
asked for packing and covering the minor models of different graphs. It was proved in [8]
that the gap of the vertex-Erdős-Pósa property of minor models of every planar graph is
O(k polylog k). It would be interesting to check if these results can be used to derive a
polylog(OPT)-approximation for vertex packing and covering minor models of any planar
graph.
Notice that all our results are strongly exploiting Lemma 1 that holds for every finite
collection H of connected graphs. Actually, what is missing in order to have an overall
generalization of all of our results, is an extension of Proposition 1 where Θr is replaced by
any finite collection H of connected planar graphs. This is an an interesting combinatorial
problem even for particular instantiations of H.

References
[1] A. P. Alberto Caprara and R. Rizzi. Packing cycles in undirected graphs. Journal of
Algorithms, 48(1):239 – 256, 2003.
[2] C. Bazgan, Z. Tuza, and D. Vanderpooten. Efficient algorithms for decomposing graphs
under degree constraints. Discrete Applied Mathematics, 155(8):979 – 988, 2007.
[3] E. Birmelé, J. A. Bondy, and B. A. Reed. The Erdős–Pósa property for long circuits.
Combinatorica, 27:135–145, 2007.
[4] H. L. Bodlaender, F. V. Fomin, D. Lokshtanov, E. Penninkx, S. Saurabh, and D. M.
Thilikos. (Meta) kernelization. In Proceedings of the 2009 50th Annual IEEE Symposium
on Foundations of Computer Science (FOCS), pages 629–638, Washington, DC, USA,
2009. IEEE Computer Society.
[5] H. L. Bodlaender, F. V. Fomin, D. Lokshtanov, E. Penninkx, S. Saurabh, and D. M.
Thilikos. (Meta) kernelization. CoRR, abs/0904.0727, 2009.
[6] H. L. Bodlaender, S. Thomassé, and A. Yeo. Kernel bounds for disjoint cycles and
disjoint paths. Theoretical Computer Science, 412(35):4570–4578, 2011.
[7] D. Chatzidimitriou, J.-F. Raymond, I. Sau, and D. M. Thilikos. Minors in graphs of
large θr -girth. CoRR, abs/1510.03041, 2015.
[8] C. Chekuri and J. Chuzhoy. Large-treewidth graph decompositions and applications.
In Proceedings of the Forty-fifth Annual ACM Symposium on Theory of Computing
(STOC), pages 291–300, New York, NY, USA, 2013. ACM.
[9] R. Diestel. Graph Theory, volume 173 of Graduate Texts in Mathematics. SpringerVerlag, Heidelberg, third edition, 2005.
[10] R. Diestel, K. ichi Kawarabayashi, and P. Wollan. The Erdős–Pósa property for
clique minors in highly connected graphs. Journal of Combinatorial Theory, Series
B, 102(2):454 – 469, 2012.

22

[11] G. Ding and B. Oporowski. On tree-partitions of graphs. Discrete Mathematics, 149(1–
3):45 – 58, 1996.
[12] P. Erdős and L. Pósa. On independent circuits contained in a graph. Canadian Journal
of Mathematics, 17:347–352, 1965.
[13] S. Fiorini, G. Joret, and U. Pietropaoli. Hitting diamonds and growing cacti. In Proceedings of Integer Programming and Combinatorial Optimization, volume 6080 of Lecture
Notes in Computer Science, pages 191–204. Springer Berlin Heidelberg, 2010.
[14] S. Fiorini, G. Joret, and I. Sau. Optimal Erdős–Pósa property for pumpkins. Manuscript,
2013.
[15] S. Fiorini, G. Joret, and D. R. Wood. Excluded forest minors and the Erdős-Pósa
property. Combinatorics, Probability & Computing, 22(5):700–721, 2013.
[16] F. V. Fomin, D. Lokshtanov, N. Misra, G Philip, and S. Saurabh. Quadratic Upper
Bounds on the Erdős–Pósa Property for a Generalization of Packing and Covering Cycles. Journal of Graph Theory 74(4), 417-424’ 2013
[17] F. V. Fomin, D. Lokshtanov, N. Misra, and S. Saurabh. Planar F-deletion: Approximation, kernelization and optimal FPT-algorithms. In Proceedings of the IEEE 53rd
Annual Symposium on Foundations of Computer Science (FOCS), pages 470–479, Oct
2012.
[18] J. Geelen and K. Kabell. The Erdős–Pósa property for matroid circuits. Journal of
Combinatorial Theory, Series B, 99(2):407–419, Mar. 2009.
[19] P. A. Golovach. Personal communication, 2015.
[20] R. Halin. Tree-partitions of infinite graphs. Discrete Mathematics, 97(1–3):203 – 217,
1991.
[21] G. Joret, C. Paul, I. Sau, S. Saurabh, and S. Thomassé. Hitting and harvesting pumpkins. SIAM Journal on Discrete Mathemarics, 28(3):1363–1390, 2014.
[22] N. Kakimura, K.-i. Kawarabayashi, and Y. Kobayashi. Erdős-Pósa property and its
algorithmic applications: Parity constraints, subset feedback set, and subset packing. In
Proceedings of the Twenty-third Annual ACM-SIAM Symposium on Discrete Algorithms
(SODA), pages 1726–1736. SIAM, 2012.
[23] K.-I. Kawarabayashi and Y. Kobayashi. Edge-disjoint odd cycles in 4-edge-connected
graphs. In Procedings of the 29th International Symposium on Theoretical Aspects of
Computer Science, (STACS), February 29th - March 3rd, 2012, Paris, France, pages
206–217, 2012.
[24] K.-I. Kawarabayashi and A. Nakamoto. The erdős–pósa property for vertex- and edgedisjoint odd cycles in graphs on orientable surfaces. Discrete Mathematics, 307(6):764 –
768, 2007.
[25] T. Kloks, C. Lee, and J. Liu. New algorithms for k-face cover, k-feedback vertex set,
and k-disjoint cycles on plane and planar graphs. In Proceedings of Graph-Theoretic
Concepts in Computer Science, volume 2573 of Lecture Notes in Computer Science,
pages 282–295. Springer Berlin Heidelberg, 2002.

23

[26] D. Král’ and H.-J. Voss. Edge-disjoint odd cycles in planar graphs. Journal of Combinatorial Theory, Series B, 90(1):107 – 120, 2004.
[27] M. Krivelevich, Z. Nutov, M. R. Salavatipour, J. V. Yuster, and R. Yuster. Approximation algorithms and hardness results for cycle packing problems. ACM Transactions on
Algorithms, 3(4), Nov. 2007.
[28] M. Krivelevich, Z. Nutov, and R. Yuster. Approximation algorithms for cycle packing
problems. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete
Algorithms (SODA), pages 556–561, Philadelphia, PA, USA, 2005. SIAM.
[29] M. Pontecorvi and P. Wollan. Disjoint cycles intersecting a set of vertices. Journal of
Combinatorial Theory, Series B, 102(5):1134 – 1141, 2012.
[30] D. Rautenbach and B. Reed. The Erdős–Pósa property for odd cycles in highly connected
graphs. Combinatorica, 21:267–278, 2001.
[31] Bruce A. Reed. Tree width and tangles: A new connectivity measure and some applications, pages 87–162. Cambridge University Press, 1997.
[32] J.-F. Raymond, I. Sau, and D. M. Thilikos. An edge variant of the Erdős–Pósa property.
CoRR, abs/1311.1108, 2013.
[33] Jean-Florent Raymond and Dimitrios M. Thilikos. Recent results on the Erdős–Pósa
property. to appear in Discrete Applied Mathematics, 2017.
[34] B. A. Reed, N. Robertson, P. D. Seymour, and R. Thomas. Packing directed circuits.
Combinatorica, 16(4):535–554, 1996.
[35] N. Robertson and P. D. Seymour. Graph Minors. V. Excluding a planar graph. Journal
of Combinatorial Theory, Series B, 41(2):92–114, 1986.
[36] M. R. Salavatipour and J. Verstraete. Disjoint cycles: Integrality gap, hardness, and
approximation. In Proceedings of Integer Programming and Combinatorial Optimization, volume 3509 of Lecture Notes in Computer Science, pages 51–65. Springer Berlin
Heidelberg, 2005.
[37] D. Seese. Tree-partite graphs and the complexity of algorithms. In Proceedings of Fundamentals of Computation Theory, volume 199 of Lecture Notes in Computer Science,
pages 412–421. Springer Berlin Heidelberg, 1985.

24

