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:20200811T163000
DTEND;TZID=Asia/Seoul:20200811T173000
DTSTAMP:20260420T001154
CREATED:20200725T052636Z
LAST-MODIFIED:20240707T082925Z
UID:2708-1597163400-1597167000@dimag.ibs.re.kr
SUMMARY:Yunbum Kook (국윤범)\, Vertex Sparsification for Edge Connectivity
DESCRIPTION:Graph compression or sparsification is a basic information-theoretic and computational question. A major open problem in this research area is whether $(1+\epsilon)$-approximate cut-preserving vertex sparsifiers with size close to the number of terminals exist. As a step towards this goal\, we initiate the study of a thresholded version of the problem: for a given parameter $c$\, find a smaller graph\, which we call connectivity-$c$ mimicking network\, which preserves connectivity among $k$ terminals exactly up to the value of $c$. We show that contraction-based connectivity-$c$ mimicking networks with $O(kc^4)$ edges exist by (1) introducing an extension of well-linkedness to a thresholded $c$-connectivity setting and (2) leveraging a kernelization result\, based on gammoid and the representative sets lemma\, to identify `essential edges’ in minimum edge cuts between a partition of terminals. We also develop an algorithm based on expander decomposition\, which can find a contraction-based $c$-mimicking network of the optimal size in $m(c\log n)^{O(c)}$. \nThese results lead to the first data structures for answering fully dynamic offline $c$-edge-connectivity queries for $c \ge 4$ in polylogarithmic time per query\, as well as more efficient algorithms for survivable network design on bounded treewidth graphs. \nThis is a joint work with Parinya Chalermsook\, Syamantak Das\, Bundit Laekhanukit\, Yang P. Liu\, Richard Peng\, Mark Sellke\, and Daniel Vaz.
URL:https://dimag.ibs.re.kr/event/2020-08-11/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR