BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Discrete Mathematics Group - ECPv6.15.20//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:Discrete Mathematics Group
X-ORIGINAL-URL:https://dimag.ibs.re.kr
X-WR-CALDESC:Events for Discrete Mathematics Group
REFRESH-INTERVAL;VALUE=DURATION:PT1H
X-Robots-Tag:noindex
X-PUBLISHED-TTL:PT1H
BEGIN:VTIMEZONE
TZID:Asia/Seoul
BEGIN:STANDARD
TZOFFSETFROM:+0900
TZOFFSETTO:+0900
TZNAME:KST
DTSTART:20250101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20260120T163000
DTEND;TZID=Asia/Seoul:20260120T173000
DTSTAMP:20260416T075602
CREATED:20251012T113928Z
LAST-MODIFIED:20251212T235119Z
UID:11717-1768926600-1768930200@dimag.ibs.re.kr
SUMMARY:Tomáš Masařík\, Separator Theorem for Minor-free Graphs in Linear Time
DESCRIPTION:The planar separator theorem by Lipton and Tarjan [FOCS ’77\, SIAM Journal on Applied Mathematics ’79] states that any planar graph with $n$ vertices has a balanced separator of size $O(\sqrt{n})$ that can be found in linear time. This landmark result kicked off decades of research on designing linear or nearly linear-time algorithms on planar graphs. In an attempt to generalize Lipton-Tarjan’s theorem to nonplanar graphs\, Alon\, Seymour\, and Thomas [STOC ’90\, Journal of the AMS ’90] showed that any minor-free graph admits a balanced separator of size $O(\sqrt{n})$ that can be found in $O(n^{3/2})$ time. The superlinear running time in their separator theorem is a key bottleneck for generalizing algorithmic results from planar to minor-free graphs. Despite extensive research for more than two decades\, finding a balanced separator of size $O(\sqrt{n})$ in (linear) $O(n)$ time for minor-free graphs remains a major open problem. Known algorithms either give a separator of size much larger than $O(\sqrt{n})$ or have superlinear running time\, or both. \nIn this paper\, we answer the open problem affirmatively. Our algorithm is very simple: it runs a vertex-weighted variant of breadth-first search (BFS) a constant number of times on the input graph. Our key technical contribution is a weighting scheme on the vertices to guide the search for a balanced separator\, offering a new connection between the size of a balanced separator and the existence of a clique-minor model. We believe that our weighting scheme may be of independent interest. \nThis is a joint work with Édouard Bonnet\, Tuukka Korhonen\, Hung Le\, and Jason Li.
URL:https://dimag.ibs.re.kr/event/2026-01-20/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR