BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Discrete Mathematics Group - ECPv6.17.1//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: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
END:VCALENDAR