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:20190101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20200729T163000
DTEND;TZID=Asia/Seoul:20200729T173000
DTSTAMP:20260423T080431
CREATED:20200629T004429Z
LAST-MODIFIED:20240705T200034Z
UID:2567-1596040200-1596043800@dimag.ibs.re.kr
SUMMARY:Akanksha Agrawal\, Polynomial Kernel for Interval Vertex Deletion
DESCRIPTION:Given a graph G and an integer k\, the Interval Vertex Deletion (IVD) problem asks whether there exists a vertex subset S of size at most k\, such that G-S is an interval graph. A polynomial kernel for a parameterized problem is a polynomial time preprocessing algorithm that outputs an equivalent instance of the problem whose size is bounded by a polynomial function of the parameter. The existence of a polynomial kernel for IVD remained a well-known open problem in Parameterized Complexity. In this talk we look at a sketch of a polynomial kernel for the problem (with the solution size as the parameter). To illustrate one of the key ingredients of our kernel\, we will look at a polynomial kernel for IVD\, when parameterized by the vertex cover number.
URL:https://dimag.ibs.re.kr/event/2020-07-29/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
END:VCALENDAR