We devise constant-factor approximation algorithms for finding as many disjoint cycles as possible from a certain family of cycles in a given planar or bounded-genus graph. Here disjoint can mean vertex-disjoint or edge-disjoint, and the graph can be undirected or directed. The family of cycles under consideration must satisfy two properties: it must be uncrossable and allow for an oracle access that finds a weight-minimal cycle in that family for given nonnegative edge weights or (in planar graphs) the union of all remaining cycles in that family after deleting a given subset of edges. Our setting generalizes many problems that were studied separately in the past. For example, three families that satisfy the above properties are (i) all cycles in a directed or undirected graph, (ii) all odd cycles in an undirected graph, and (iii) all cycles in an undirected graph that contain precisely one demand edge, where the demand edges form a subset of the edge set. The latter family (iii) corresponds to the classical disjoint paths problem in fully planar and bounded-genus instances. While constant-factor approximation algorithms were known for edge-disjoint paths in such instances, we improve the constant in the planar case and obtain the first such algorithms for vertexdisjoint paths. We also obtain approximate min-max theorems of the Erd\H{o}s--P\'osa type. For example, the minimum feedback vertex set in a planar digraph is at most 12 times the maximum number of vertex-disjoint cycles.

This is joint work with Hanjo Thiele and Jens Vygen.

The single-source unsplittable flow (SSUF) problem asks to send flow in a digraph with capacities from a common source to different terminals with unrelated demands, each terminal being served through a single path. A seminal result of Dinitz, Garg, and Goemans showed that, whenever a fractional flow exists respecting the capacities, then there is an unsplittable one violating the capacities by at most the maximum demand. Goemans conjectured a very natural cost version of the same result, where the unsplittable flow is required to be no more expensive than the fractional one. So far there are no non-trivial graph classes for which it is known to hold. In the talk, we will see that a slight weakening of it (with at most twice as large violations) holds for planar graphs. This result is based on a connection to a highly structured discrepancy problem, whose repeated resolution allows us to successively reduce the number of paths used for each terminal, until we obtain an unsplittable flow.

This is joint work with Vera Traub and Rico Zenklusen.