Speaker: 李陈筠然，北京化工大学

Inviter: 陈绍示老师

Title: On the constrained Steiner strong connectivity augmentation problem

Language: Chinese

Time & Venue: 2025.05.08 16:00-17:00 思源楼525

Abstract: In this talk, we consider the constrained Steiner strong connectivity augmentation (CStSCA) problem. Concretely, given a weighted digraph D = (V, A; w), where w : A →R+ is a weight function, K(⊆V ) is a vertex-set consisting of k fixed vertices (called as terminals) and Tk = (Vk , Ak ) is a strongly connected Steiner subgraph (of D), i.e., Tk contains at least one directed path from each terminal s to other each terminal t, where s, t ∈K, we are asked to find an arc-set A’⊆A\Ak to satisfy the constraints that, given each arc e ∈ Ak , the subgraph D[A’∪Ak \{e}] is still a strongly connected Steiner subgraph (of D), the objective is to minimize the summation of weights of all arcs in A′, where the summation is taken among all arc-sets to satisfy the constraints as mentioned-above. In particular, given a vertex-set K= {x, y}, we refer the CStSCA problem as to the constrained directed circuit augmentation (CDCA) problem, and given a vertex-set K= V , we refer the CStSCA problem as to the constrained strong connectivity augmentation (CSCA) problem. We obtain the following three main results. (1) We design an 2-approximation algorithm to solve the CDCA problem in time O(mn); (2) Using the preceding algorithm in (1) as a subroutine for many times, we present an 2k-approximation algorithm to solve the CStSCA problem in time O(kmn); (3) We provide an 2-approximation algorithm to solve the CSCA problem in time O(n(m + n log n) log n).