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:20240101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20250121T163000
DTEND;TZID=Asia/Seoul:20250121T173000
DTSTAMP:20260417T110730
CREATED:20241213T151545Z
LAST-MODIFIED:20241213T151545Z
UID:10270-1737477000-1737480600@dimag.ibs.re.kr
SUMMARY:Laure Morelle\, Bounded size modifications in time $2^{{\sf poly}(k)}\cdot n^2$
DESCRIPTION:A replacement action is a function $\mathcal L$ that maps each graph to a collection of subgraphs of smaller size. \nGiven a graph class $\mathcal H$\, we consider a general family of graph modification problems\, called “$\mathcal L$-Replacement to $\mathcal H$”\, where the input is a graph $G$ and the question is whether it is possible to replace some induced subgraph $H_1$ of $G$ on at most $k$ vertices by a graph $H_2$ in ${\mathcal L}(H_1)$ so that the resulting graph belongs to $\mathcal H$. \n“$\mathcal L$-Replacement to $\mathcal H$” can simulate many graph modification problems including vertex deletion\, edge deletion/addition/edition/contraction\, vertex identification\, subgraph complementation\, independent set deletion\, (induced) matching deletion/contraction\, etc. \nWe prove here that\, for any minor-closed graph class $\mathcal H$ and for any action $\mathcal L$ that is hereditary\, there is an algorithm that solves “$\mathcal L$-Replacement to $\mathcal H$” in time $2^{{\sf poly}(k)}\cdot |V(G)|^2$\, where $\sf poly$ is a polynomial whose degree depends on $\mathcal H$.
URL:https://dimag.ibs.re.kr/event/2025-01-21/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR