Cycle Packing and Cycle Transversal in Graphs on Oriented Surfaces
Cycle Packing and Cycle Transversal in Graphs on Oriented Surfaces
View/Type of Scholarly Publication
DissertationDate of Exam
17.04.2026Date of Publication
11.05.2026Advisor
Vygen, JensCo-Referee
Végh, László A.Metadata
Show full item record
Citable Links 
Abstract
The topics of this thesis are the Cycle Packing Problem and the Cycle Transversal Problem in planar or bounded-genus graphs. Given a graph G and an implicitly given family C of cycles in G, the Cycle Packing Problem asks for a maximum-cardinality subset S ⊆ C of pairwise vertex- or edge-disjoint cycles. Dual to this problem is the Cycle Transversal Problem, which asks for a minimum-cardinality set T of vertices or edges, respectively, that hit all cycles in C. Both problems are well-studied for several choices of cycle families C, such as e.g. all cycles in G, all odd cycles, or all cycles containing exactly one edge from a specified set D ⊆ E(G) of demand edges. We examine the problems for a broad class of cycle families which are called uncrossable, a notion introduced by Goemans and Williamson in 1998. This includes all examples mentioned before. An application of particular interest is the famous Disjoint Paths Problem. Many versions of our problems are hard to approximate in general graphs and are known to remain NP-hard if G is planar; we also give a very general NP-hardness proof for planar Cycle Packing Problems. For the uncrossable and planar Cycle Packing Problem we give both combinatorial and LP-based constant-factor approximations, improving the best-known guarantees for many choices of C and yielding the first constant-factor approximation in some cases, including the Vertex-disjoint Paths Problem. Together with known results on the Cycle Transversal LP (Goemans and Williamson 1998, Berman and Yaroslavtsev 2012) this also yields constant bounds for the Erdős–Pósa ratio, i.e. the maximum ratio between maximum packings and minimum transversals. We further extend one of our approaches for the uncrossable Cycle Packing Problem to the case where G is embedded in an orientable surface of constant genus g, giving a guarantee of O(g2). For a more restricted class of cycle families C, which still includes all examples mentioned, we complement this with an O(g)-approximation for the Cycle Transversal Problem. Together, this establishes a new bound of O(g3) on the Erdős–Pósa ratio in such instances. Finally, we consider the notion of k-nice sets which is related to one of our main results for the Cycle Packing Problem. A k-nice set on a surface Σ is a set of pairwise non-homotopic simple loops on Σ. Bounds on the maximum size of k-nice sets have been studied under various circumstances. We consider the simple case where Σ is the torus and determine the maximum size of a k-nice set in this case for all k. In particular, we show an upper bound of k + 6, improving on a recent bound of k + O(√k log k) by Aougab and Gaster.
Classification (DDC)
510 MathematikSchlomberg, Niklas: Cycle Packing and Cycle Transversal in Graphs on Oriented Surfaces. - Bonn, 2026. - Dissertation, Rheinische Friedrich-Wilhelms-Universität Bonn.
Online-Ausgabe in bonndoc: https://nbn-resolving.org/urn:nbn:de:hbz:5-89964
Online-Ausgabe in bonndoc: https://nbn-resolving.org/urn:nbn:de:hbz:5-89964
@phdthesis{handle:20.500.11811/14137,
urn: https://nbn-resolving.org/urn:nbn:de:hbz:5-89964,
author = {{Niklas Schlomberg}},
title = {Cycle Packing and Cycle Transversal in Graphs on Oriented Surfaces},
school = {Rheinische Friedrich-Wilhelms-Universität Bonn},
year = 2026,
month = may,
note = {The topics of this thesis are the Cycle Packing Problem and the Cycle Transversal Problem in planar or bounded-genus graphs. Given a graph G and an implicitly given family C of cycles in G, the Cycle Packing Problem asks for a maximum-cardinality subset S ⊆ C of pairwise vertex- or edge-disjoint cycles. Dual to this problem is the Cycle Transversal Problem, which asks for a minimum-cardinality set T of vertices or edges, respectively, that hit all cycles in C. Both problems are well-studied for several choices of cycle families C, such as e.g. all cycles in G, all odd cycles, or all cycles containing exactly one edge from a specified set D ⊆ E(G) of demand edges. We examine the problems for a broad class of cycle families which are called uncrossable, a notion introduced by Goemans and Williamson in 1998. This includes all examples mentioned before. An application of particular interest is the famous Disjoint Paths Problem. Many versions of our problems are hard to approximate in general graphs and are known to remain NP-hard if G is planar; we also give a very general NP-hardness proof for planar Cycle Packing Problems. For the uncrossable and planar Cycle Packing Problem we give both combinatorial and LP-based constant-factor approximations, improving the best-known guarantees for many choices of C and yielding the first constant-factor approximation in some cases, including the Vertex-disjoint Paths Problem. Together with known results on the Cycle Transversal LP (Goemans and Williamson 1998, Berman and Yaroslavtsev 2012) this also yields constant bounds for the Erdős–Pósa ratio, i.e. the maximum ratio between maximum packings and minimum transversals. We further extend one of our approaches for the uncrossable Cycle Packing Problem to the case where G is embedded in an orientable surface of constant genus g, giving a guarantee of O(g2). For a more restricted class of cycle families C, which still includes all examples mentioned, we complement this with an O(g)-approximation for the Cycle Transversal Problem. Together, this establishes a new bound of O(g3) on the Erdős–Pósa ratio in such instances. Finally, we consider the notion of k-nice sets which is related to one of our main results for the Cycle Packing Problem. A k-nice set on a surface Σ is a set of pairwise non-homotopic simple loops on Σ. Bounds on the maximum size of k-nice sets have been studied under various circumstances. We consider the simple case where Σ is the torus and determine the maximum size of a k-nice set in this case for all k. In particular, we show an upper bound of k + 6, improving on a recent bound of k + O(√k log k) by Aougab and Gaster.},
url = {https://hdl.handle.net/20.500.11811/14137}
}
urn: https://nbn-resolving.org/urn:nbn:de:hbz:5-89964,
author = {{Niklas Schlomberg}},
title = {Cycle Packing and Cycle Transversal in Graphs on Oriented Surfaces},
school = {Rheinische Friedrich-Wilhelms-Universität Bonn},
year = 2026,
month = may,
note = {The topics of this thesis are the Cycle Packing Problem and the Cycle Transversal Problem in planar or bounded-genus graphs. Given a graph G and an implicitly given family C of cycles in G, the Cycle Packing Problem asks for a maximum-cardinality subset S ⊆ C of pairwise vertex- or edge-disjoint cycles. Dual to this problem is the Cycle Transversal Problem, which asks for a minimum-cardinality set T of vertices or edges, respectively, that hit all cycles in C. Both problems are well-studied for several choices of cycle families C, such as e.g. all cycles in G, all odd cycles, or all cycles containing exactly one edge from a specified set D ⊆ E(G) of demand edges. We examine the problems for a broad class of cycle families which are called uncrossable, a notion introduced by Goemans and Williamson in 1998. This includes all examples mentioned before. An application of particular interest is the famous Disjoint Paths Problem. Many versions of our problems are hard to approximate in general graphs and are known to remain NP-hard if G is planar; we also give a very general NP-hardness proof for planar Cycle Packing Problems. For the uncrossable and planar Cycle Packing Problem we give both combinatorial and LP-based constant-factor approximations, improving the best-known guarantees for many choices of C and yielding the first constant-factor approximation in some cases, including the Vertex-disjoint Paths Problem. Together with known results on the Cycle Transversal LP (Goemans and Williamson 1998, Berman and Yaroslavtsev 2012) this also yields constant bounds for the Erdős–Pósa ratio, i.e. the maximum ratio between maximum packings and minimum transversals. We further extend one of our approaches for the uncrossable Cycle Packing Problem to the case where G is embedded in an orientable surface of constant genus g, giving a guarantee of O(g2). For a more restricted class of cycle families C, which still includes all examples mentioned, we complement this with an O(g)-approximation for the Cycle Transversal Problem. Together, this establishes a new bound of O(g3) on the Erdős–Pósa ratio in such instances. Finally, we consider the notion of k-nice sets which is related to one of our main results for the Cycle Packing Problem. A k-nice set on a surface Σ is a set of pairwise non-homotopic simple loops on Σ. Bounds on the maximum size of k-nice sets have been studied under various circumstances. We consider the simple case where Σ is the torus and determine the maximum size of a k-nice set in this case for all k. In particular, we show an upper bound of k + 6, improving on a recent bound of k + O(√k log k) by Aougab and Gaster.},
url = {https://hdl.handle.net/20.500.11811/14137}
}
The following license files are associated with this item:
