A tight Erdős-Pósa function for planar minors

Wouter Cames Van Batenburg, Tony Huynh, Gwenaël Joret, Jean Florent Raymond

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearch

Abstract

Let H be a planar graph. By a classical result of Robertson and Seymour, there is a function f : N → R such that for all k ∈ N and all graphs G, either G contains k vertex-disjoint subgraphs each containing H as a minor, or there is a subset X of at most f(k) vertices such that G−X has no Hminor. We prove that this remains true with f(k) = ck log k for some constant c = c(H). This bound is best possible, up to the value of c, and improves upon a recent result of Chekuri and Chuzhoy [STOC 2013], who established this with f(k) = ck logd k for some universal constant d. The proof is constructive and yields a polynomial-time O(log OPT)-approximation algorithm for packing subgraphs containing an H-minor.

Original languageEnglish
Title of host publicationProceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms
Subtitle of host publication30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019; San Diego; United States; 6 January 2019 through 9 January 2019
Place of PublicationPhiladelphia PA USA
PublisherSociety for Industrial & Applied Mathematics (SIAM)
Pages1485-1500
Number of pages16
ISBN (Electronic)9781611975482
Publication statusPublished - 1 Jan 2019
Externally publishedYes
EventACM/SIAM Symposium on Discrete Algorithms, 2019 - Westin San Diego, San Diego, United States of America
Duration: 6 Jan 20199 Jan 2019
Conference number: 30th
https://www.siam.org/conferences/cm/conference/soda19

Conference

ConferenceACM/SIAM Symposium on Discrete Algorithms, 2019
Abbreviated titleSODA19
CountryUnited States of America
CitySan Diego
Period6/01/199/01/19
OtherThis symposium focuses on research topics related to efficient algorithms and data structures for discrete problems. In addition to the design of such methods and structures, the scope also includes their use, performance analysis, and the mathematical problems related to their development or limitations. Performance analyses may be analytical or experimental and may address worst-case or expected-case performance. Studies can be theoretical or based on data sets that have arisen in practice and may address methodological issues involved in performance analysis.
Internet address

Cite this

Van Batenburg, W. C., Huynh, T., Joret, G., & Raymond, J. F. (2019). A tight Erdős-Pósa function for planar minors. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms: 30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019; San Diego; United States; 6 January 2019 through 9 January 2019 (pp. 1485-1500). Philadelphia PA USA: Society for Industrial & Applied Mathematics (SIAM).