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

Abstract: Let

H

be a planar graph. By a classical result of Robertson and Seymour, there is a function

f : m a t h b b N o m a t h b b R

such that for all

k i n m a t h b b 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) = c k l o g 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) = c k l o g^{d} k

for some universal constant

d

. The proof is constructive and yields a polynomial-time

O (l o g m a t h s f O P T)

-approximation algorithm for packing subgraphs containing an

H

-minor.

Recommendations

Cited in

(18)

This page was built for publication: A tight Erdős-Pósa function for planar minors