2026-07-27T05:06:48Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20265 2024-07-02T07:52:54Z ddc:004 open_access

An Improved Integrality Gap for Disjoint Cycles in Planar Graphs Schlomberg, Niklas Cycle packing planar graphs disjoint paths We present a new greedy rounding algorithm for the Cycle Packing Problem for uncrossable cycle families in planar graphs. This improves the best-known upper bound for the integrality gap of the natural packing LP to a constant slightly less than 3.5. Furthermore, the analysis works for both edge- and vertex-disjoint packing. The previously best-known constants were 4 for edge-disjoint and 5 for vertex-disjoint cycle packing. This result also immediately yields an improved Erdős-Pósa ratio: for any uncrossable cycle family in a planar graph, the minimum number of vertices (edges) needed to hit all cycles in the family is less than 8.38 times the maximum number of vertex-disjoint (edge-disjoint, respectively) cycles in the family. Some uncrossable cycle families of interest to which the result can be applied are the family of all cycles in a directed or undirected graph, in undirected graphs also the family of all odd cycles and the family of all cycles containing exactly one edge from a specified set of demand edges. The last example is an equivalent formulation of the fully planar Disjoint Paths Problem. Here the Erdős-Pósa ratio translates to a ratio between integral multi-commodity flows and minimum cuts. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Niklas Schlomberg 2024 Is Part Of LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2024.122 urn:nbn:de:0030-drops-202651 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.122 eng https://creativecommons.org/licenses/by/4.0/legalcode