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:20210101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20221108T163000
DTEND;TZID=Asia/Seoul:20221108T173000
DTSTAMP:20260419T224714
CREATED:20221018T044028Z
LAST-MODIFIED:20240707T074529Z
UID:6364-1667925000-1667928600@dimag.ibs.re.kr
SUMMARY:Jungho Ahn (안정호)\, Unified almost linear kernels for generalized covering and packing problems on nowhere dense classes
DESCRIPTION:Let $\mathcal{F}$ be a family of graphs\, and let $p$ and $r$ be nonnegative integers.\nThe $(p\,r\,\mathcal{F})$-Covering problem asks whether for a graph $G$ and an integer $k$\, there exists a set $D$ of at most $k$ vertices in $G$ such that $G^p\setminus N_G^r[D]$ has no induced subgraph isomorphic to a graph in $\mathcal{F}$\, where $G^p$ is the $p$-th power of $G$ and $N^r_G[D]$ is the set of all vertices in $G$ at distance at most $r$ from $D$ in $G$. The $(p\,r\,\mathcal{F})$-Packing problem asks whether for a graph $G$ and an integer $k$\, $G^p$ has $k$ induced subgraphs $H_1\,\ldots\,H_k$ such that each $H_i$ is isomorphic to a graph in $\mathcal{F}$\, and for distinct $i\,j\in \{1\, \ldots\, k\}$\, the distance between $V(H_i)$ and $V(H_j)$ in $G$ is larger than $r$. The $(p\,r\,\mathcal{F})$-Covering problem generalizes Distance-$r$ Dominating Set and Distance-$r$ Vertex Cover\, and the $(p\,r\,\mathcal{F})$-Packing problem generalizes Distance-$r$ Independent Set and Distance-$r$ Matching. By taking $(p’\,r’\,\mathcal{F}’)=(pt\, rt\, \mathcal{F})$\, we may formulate the $(p\,r\,\mathcal{F})$-Covering and $(p\, r\, \mathcal{F})$-Packing problems on the $t$-th power of a graph. Moreover\, $(1\,0\,\mathcal{F})$-Covering is the $\mathcal{F}$-Free Vertex Deletion problem\, and $(1\,0\,\mathcal{F})$-Packing is the Induced-$\mathcal{F}$-Packing problem. \nWe show that for every fixed nonnegative integers $p\,r$ and every fixed nonempty finite family $\mathcal{F}$ of connected graphs\, the $(p\,r\,\mathcal{F})$-Covering problem with $p\leq2r+1$ and the $(p\,r\,\mathcal{F})$-Packing problem with $p\leq2\lfloor r/2\rfloor+1$ admit almost linear kernels on every nowhere dense class of graphs\, and admit linear kernels on every class of graphs with bounded expansion\, parameterized by the solution size $k$. We obtain the same kernels for their annotated variants. As corollaries\, we prove that Distance-$r$ Vertex Cover\, Distance-$r$ Matching\, $\mathcal{F}$-Free Vertex Deletion\, and Induced-$\mathcal{F}$-Packing for any fixed finite family $\mathcal{F}$ of connected graphs admit almost linear kernels on every nowhere dense class of graphs and linear kernels on every class of graphs with bounded expansion. Our results extend the results for Distance-$r$ Dominating Set by Drange et al. (STACS 2016) and Eickmeyer et al. (ICALP 2017)\, and the result for Distance-$r$ Independent Set by Pilipczuk and Siebertz (EJC 2021). \nThis is joint work with Jinha Kim and O-joung Kwon.
URL:https://dimag.ibs.re.kr/event/2022-11-08/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR