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:20200101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210824T163000
DTEND;TZID=Asia/Seoul:20210824T173000
DTSTAMP:20260424T133208
CREATED:20210810T073000Z
LAST-MODIFIED:20240707T081032Z
UID:4212-1629822600-1629826200@dimag.ibs.re.kr
SUMMARY:Eun Jung Kim (김은정)\, A Constant-factor Approximation for Weighted Bond Cover
DESCRIPTION:The Weighted $\mathcal F$-Vertex Deletion for a class $\mathcal F$ of graphs asks\, given a weighted graph $G$\, for a minimum weight vertex set $S$ such that $G-S\in\mathcal F$. The case when $\mathcal F$ is minor-closed and excludes some graph as a minor has received particular attention but a constant-factor approximation remained elusive for Weighted $\mathcal F$-Vertex Deletion. Only three cases of minor-closed $\mathcal F$ are known to admit constant-factor approximations\, namely Vertex Cover\, Feedback Vertex Set and Diamond Hitting Set. \nWe study the problem for the class $\mathcal F$ of $\theta_c$-minor-free graphs\, under the equivalent setting of the Weighted c-Bond Cover\, and present a constant-factor approximation algorithm using the primal-dual method. For this\, we leverage a structure theorem implicit in [Joret et al.\, SIDMA’14] which states the following: any graph $G$ containing a $\theta_c$-minor-model either contains a large two-terminal protrusion\, or contains a constant-size $\theta_c$-minor-model\, or a collection of pairwise disjoint constant-sized connected sets that can be contracted simultaneously to yield a dense graph. In the first case\, we tame the graph by replacing the protrusion with a special-purpose weighted gadget. For the second and third case\, we provide a weighting scheme which guarantees a local approximation ratio. Besides making an important step in the quest of (dis)proving a constant-factor approximation for Weighted $\mathcal F$-Vertex Deletion\, our result may be useful as a template for algorithms for other minor-closed families. \nThis is joint work with Euiwoong Lee and Dimitrios M. Thilikos.
URL:https://dimag.ibs.re.kr/event/2021-08-24/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR