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 language | English |
|---|---|
| Title of host publication | Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms |
| Subtitle of host publication | 30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019; San Diego; United States; 6 January 2019 through 9 January 2019 |
| Place of Publication | Philadelphia PA USA |
| Publisher | Society for Industrial & Applied Mathematics (SIAM) |
| Pages | 1485-1500 |
| Number of pages | 16 |
| ISBN (Electronic) | 9781611975482 |
| Publication status | Published - 1 Jan 2019 |
| Externally published | Yes |
| Event | ACM/SIAM Symposium on Discrete Algorithms, 2019 - Westin San Diego, San Diego, United States of America Duration: 6 Jan 2019 → 9 Jan 2019 Conference number: 30th https://www.siam.org/conferences/cm/conference/soda19 |
Conference
| Conference | ACM/SIAM Symposium on Discrete Algorithms, 2019 |
|---|---|
| Abbreviated title | SODA19 |
| Country/Territory | United States of America |
| City | San Diego |
| Period | 6/01/19 → 9/01/19 |
| Other | This 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 |