## University of Waterloo COVID-19 update

Please see the University of Waterloo’s frequently asked questions for information about COVID-19 and how it has affected university operations.

Please visit the list of modified services if you have questions about university services.

Although the University of Waterloo is closed for in-person events until further notice, many virtual events and presentations of interest to computer scientists are taking place each week at the Cheriton School of Computer Science. Please check out what our students and faculty are doing.

# Seminar • Algorithms and Complexity — Polylogarithmic Approximation for k-Connected Directed Steiner Tree in Quasi-Bipartite Graphs

Wednesday, November 6, 2019 — 2:15 PM EST

Bundit Laekhanukit, Institute for Theoretical Computer Science
Shanghai University of Finance and Economics

In the k-Connected Directed Steiner Tree problem (k-DST), we are given a directed graph G=(V,E) with edge (or vertex) costs, a root vertex r, a set of q terminals T, and a connectivity requirement k>0; the goal is to find a minimum-cost subgraph H of G such that H has k edge-disjoint paths from the root r to each terminal t in T. The k-DST problem is a natural generalization of the classical Directed Steiner Tree problem (DST) in the fault-tolerant setting in which the solution subgraph is required to have an r,t-path, for every terminal t, even after removing k-1 vertices or edges.

Despite being a classical problem, there are not many positive results on the problem, especially for the case k >= 3. In this talk, we will present an O(log k log q)-approximation algorithm for k-DST when an input graph is quasi-bipartite, i.e., when there is no edge joining two non-terminal vertices. To the best of our knowledge, our algorithm is the only known non-trivial approximation algorithm for k-DST, for k >= 3, that runs in polynomial-time regardless of the structure of the optimal solution. In addition, our algorithm is tight for every constant k, due to the hardness result inherited from the Set Cover problem.

This is a joint work Chun-Hsiang (Kenny) Chan, Hao-Ting Wei and Yuhao Zhang.

Location
DC - William G. Davis Computer Research Centre
1304
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

### June 2020

S M T W T F S
31
2
3
4
6
7
12
13
14
15
16
18
19
20
21
23
24
25
26
27
28
29
30
1
2
3
4
1. 2020 (107)
1. June (6)
2. May (17)
3. April (20)
4. March (17)
5. February (25)
6. January (22)
2. 2019 (255)
1. December (21)
2. November (25)
3. October (16)
4. September (20)
5. August (18)
6. July (12)
7. June (23)
8. May (23)
9. April (32)
10. March (25)
11. February (16)
12. January (24)
3. 2018 (220)
4. 2017 (36)
5. 2016 (21)
6. 2015 (36)
7. 2014 (33)
8. 2013 (23)
9. 2012 (4)
10. 2011 (1)
11. 2010 (1)
12. 2009 (1)
13. 2008 (1)