Name
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 H-minor. 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.
|
Year | DOI | Venue |
|---|---|---|
2019 | 10.5555/3310435.3310525 | SODA '19: Symposium on Discrete Algorithms
San Diego
California
January, 2019 |
DocType | Volume | Citations |
Conference | abs/1807.04969 | 0 |
PageRank | References | Authors |
0.34 | 0 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Wouter Cames van Batenburg | 1 | 0 | 1.01 |
| Tony Huynh | 2 | 11 | 9.36 |
| Gwenaël Joret | 3 | 196 | 28.64 |
| Jean-Florent Raymond | 4 | 12 | 8.42 |