BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Discrete Mathematics Group - ECPv6.15.20//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:20240101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20250625T163000
DTEND;TZID=Asia/Seoul:20250625T173000
DTSTAMP:20260511T230420
CREATED:20250606T142052Z
LAST-MODIFIED:20250611T082038Z
UID:10973-1750869000-1750872600@dimag.ibs.re.kr
SUMMARY:Roohani Sharma\, Uniform and Constructive Polynomial Kernel for Deletion to $K_{2\,p}$ Minor-Free Graphs
DESCRIPTION:Let $\mathcal F$ be a fixed\, finite family of graphs. In the $\mathcal F$-Deletion problem\, the input is a graph G and a positive integer k\, and the goal is to determine if there exists a set of at most k vertices whose deletion results in a graph that does not contain any graph of $\mathcal F$ as a minor. The $\mathcal F$-Deletion problem encapsulates a large class of natural and interesting graph problems like Vertex Cover\, Feedback Vertex Set\, Treewidth-$\eta$ Deletion\, Treedepth-$\eta$ Deletion\, Pathwidth-$\eta$ Deletion\, Outerplanar Deletion\, Vertex Planarization and many more. We study the $\mathcal F$-Deletion problem from the kernelization perspective. \nIn a seminal work\, Fomin\, Lokshtanov\, Misra & Saurabh [FOCS 2012] gave a polynomial kernel for this problem when the family F contains at least one planar graph. The asymptotic growth of the size of the kernel is not uniform with respect to the family $\mathcal F$: that is\, the size of the kernel is $k^{f(\mathcal F)}$\, for some function f that depends only on $\mathcal F$. Also the size of the kernel depends on non-constructive constants. \nLater Giannopoulou\, Jansen\, Lokshtanov & Saurabh [TALG 2017] showed that the non-uniformity in the kernel size bound of Fomin et al. is unavoidable as Treewidth-$\eta$ Deletion\, cannot admit a kernel of size $O(k^{(\eta +1)/2 -\epsilon)}$\, for any $\epsilon >0$\, unless NP $\subseteq$ coNP/poly. On the other hand it was also shown that Treedepth-$\eta$ Deletion\, admits a uniform kernel of size $f(\mathcal F) k^6$\, showcasing that there are subclasses of $\mathcal F$ where the asymptotic kernel sizes do not grow as a function of the family $\mathcal F$. This work leads to the natural question of determining classes of $\mathcal F$ where the problem admits uniform polynomial kernels. \nIn this work\, we show that if all the graphs in $\mathcal F$ are connected and $\mathcal F$ contains $K_{2\,p}$ (a bipartite graph with 2 vertices on one side and p vertices on the other)\, then the problem admits a uniform kernel of size $f(\mathcal F) k^{10}$ where the constants in the size bound are also constructive. The graph $K_{2\,p}$ is one natural extension of the graph $\theta_p$\, where $\theta_p$ is a graph on two vertices and p parallel edges. The case when $\mathcal F$ contains $\theta_p$ has been studied earlier and serves as (the only) other example where the problem admits a uniform polynomial kernel. \nThis is joint work with William Lochet.
URL:https://dimag.ibs.re.kr/event/2025-06-25/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR