Loading Events

« All Events

  • This event has passed.
:

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

Monday, December 10, 2018 @ 5:00 PM - 6:00 PM KST

Room B109, IBS

Let H be a planar graph. By a classical result of Robertson and Seymour, there is a function f(k) such that for all k 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 depending on H. This bound is best possible, up to the value of c, and improves upon a recent bound of Chekuri and Chuzhoy. The proof is constructive and yields the first polynomial-time O(log 𝖮𝖯𝖳)-approximation algorithm for packing subgraphs containing an H-minor.

This is joint work with Wouter Cames van Batenburg, Gwenaël Joret, and Jean-Florent Raymond.

Details

Date:
Monday, December 10, 2018
Time:
5:00 PM - 6:00 PM KST
Event Category:
Event Tags:

Venue

Room B109
IBS

Organizer

Sang-il Oum (엄상일)
Website:
https://dimag.ibs.re.kr/home/sangil/