BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Discrete Mathematics Group - ECPv6.17.1//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:20250101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20260804T163000
DTEND;TZID=Asia/Seoul:20260804T173000
DTSTAMP:20260725T124528Z
CREATED:20260617T111737Z
LAST-MODIFIED:20260725T124528Z
UID:12779-1785861000-1785864600@dimag.ibs.re.kr
SUMMARY:Tomohiro Koana\, A Single-Exponential FPT Algorithm for 2-Vertex-Connectivity Augmentation
DESCRIPTION:We study restricted-link augmentation to 2-vertex-connectivity. An instance consists of a graph $G$\, possibly disconnected\, a set $L$ of admissible links on its vertices\, integer link costs in $\{1\, \ldots\, W\}$\, and an integer $k$; the task is to add at most $k$ links of minimum total cost so that the resulting multigraph is 2-vertex-connected. Recent work gives $O^*(k^{O(k)})$-time algorithms for unweighted λ-vertex-connectivity augmentation for every λ ≤ 4 [Carmesin and Ramanujan\, SODA 2026]\, and an $O^*((k + λ)^{O(k)})$-time algorithm for arbitrary λ [Korhonen and Thorup\, FOCS 2026]. We give a deterministic algorithm with running time $O^*(36^k W)$. Thus\, for λ = 2\, the unweighted running time improves from $O^*(k^{O(k)})$ to $O^*(36^k)$\, and the algorithm also handles link costs with pseudo-polynomial dependence on $W$. \nWe reduce the problem to a boundary-pair variant of 2-vertex-connected spanning subgraph\, where each vertex is assigned a pair of incident edges with an associated pair cost. We solve this variant using a cancellation identity\, inspired by Cut&Count [Cygan et al.\, TALG 2022]\, obtained by applying Möbius inversion to decompositions along cut vertices: the identity cancels every connected spanning graph with more than one block and keeps exactly the 2-vertex-connected spanning graphs.
URL:https://dimag.ibs.re.kr/event/2026-08-04/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20260805T163000
DTEND;TZID=Asia/Seoul:20260805T173000
DTSTAMP:20260725T142224Z
CREATED:20260520T141609Z
LAST-MODIFIED:20260725T142224Z
UID:12683-1785947400-1785951000@dimag.ibs.re.kr
SUMMARY:Meike Hatzel\, Directed tree-cutwidth and immersions
DESCRIPTION:The first major step towards the graph minor structure theorem by Robertson and Seymour was the grid theorem\, a result describing that every graph of large treewidth contains a grid as minor. In 2014 Wollan gave a definition for a tree-like decomposition and a width parameter tree-cutwidth with respect to immersions\, a different graph containment relation. He provided results linking this parameter to immersions of large walls. This talk presents a version of this parameter for directed graphs\, the directed tree-cutwidth. The main result is a grid theorem for directed tree-cutwidth establishing that it is linked to directed immersions of large cylindrical walls. \nThe presented work is joined with Marcin Briański\, Karolina Okrasa\, and Michał Pilipczuk.
URL:https://dimag.ibs.re.kr/event/2026-08-05/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;VALUE=DATE:20260810
DTEND;VALUE=DATE:20260815
DTSTAMP:20260522T224718Z
CREATED:20260522T224718Z
LAST-MODIFIED:20260522T224718Z
UID:12688-1786320000-1786751999@dimag.ibs.re.kr
SUMMARY:2026 Summer School on Combinatorics and Algorithms (2026 조합론 및 알고리즘 여름학교)
DESCRIPTION:The 2026 Summer School on Combinatorics and Algorithms is a venue for students and early-career researchers to learn selected topics in theoretical computer science and discrete mathematics. It will be a great opportunity for young and aspiring researchers to study topics which are important but not covered during the lectures in the university classes. \nWebsite: https://combialgo.dimag.kr/2026/ \nLecturers and Topics\n\nDaniel Dadush\, CWI\, Amsterdam\n\nAlgorithms & Geometry of Linear Programming\n\n\nMagnus Wahlström\, Royal Holloway\, University of London\n\nMatroids\, delta-matroids\, and applications\n\n\n\nSchedule\n\nStart on 10 August 2026 Monday\, 2 PM\nEnd on 14 August 2025 Friday\, 5 PM
URL:https://dimag.ibs.re.kr/event/2026-08-10/
LOCATION:Bldg. E11\, KAIST
CATEGORIES:Workshops and Conferences
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20260818T163000
DTEND;TZID=Asia/Seoul:20260818T173000
DTSTAMP:20260326T020259Z
CREATED:20260326T020259Z
LAST-MODIFIED:20260326T020259Z
UID:12486-1787070600-1787074200@dimag.ibs.re.kr
SUMMARY:Jinyoung Park (박진영)\, TBA
DESCRIPTION:
URL:https://dimag.ibs.re.kr/event/2026-08-18/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR