BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Discrete Mathematics Group - ECPv6.16.3//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
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:20260602T163000
DTEND;TZID=Asia/Seoul:20260602T173000
DTSTAMP:20260531T005714
CREATED:20251210T144125Z
LAST-MODIFIED:20260524T215108Z
UID:11977-1780417800-1780421400@dimag.ibs.re.kr
SUMMARY:Maria Chudnovsky\, Induced minors and treewidth
DESCRIPTION:This talk deals with induced minor obstructions to treewidth. The natural setup for this problem is to consider the class of graphs excluding some planar graph\, and some complete bipartite graph as induced minors\, and some complete graph as a subgraph. Unfortunately\, such  classes still contain graphs of arbitrarily large treewidth. Moreover\, a result of Alecu\, Bonnet\, Bureo Villafana and Trotignon and its extensions suggest that there is no elegant characterization of families of bounded treewidth in terms of induced obstructions. \nOn the other hand\, it is conjectured that graphs in the classes as above have treewidth bounded by a poly-logarithmic function of their number of vertices. If true\, this will imply the existence of quasi-polynomial time algorithms for a host of problems on such  classes that are NP-complete in the general setting. \nWhile this conjecture remains open\, in joint work with Julien Codsi\, David Fischer and Daniel Lokshtanov\, we were able to prove the existence of a sub-polynomial bound on treewidth in terms of the number of vertices. This in turn leads to sub-exponential algorithmic behavior. \nIn this talk we will discuss some ideas of the proof\, and\, if time permits\, some results in the more general setting when the bound on the clique size is removed.
URL:https://dimag.ibs.re.kr/event/2025-06-02/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR