Surviving in Directed Graphs: A Quasi-polynomial-time Polylogarithmic Approximation for Two-connected Directed Steiner Tree

Joint work with Bundit Laekhanukit The high-level goal of survivable network design is to design cheap networks that satisfy giving connectivity requirements even in the preserve of node or edge faults. While many approximation algorithms are known for a variety of such problems in undirected graphs, not much is known for directed ones. In this work we present the first non-trivial approximation algorithm for the 2-edge connectivity generalization of Directed Steiner Tree (DST). Analogously to DST, our approach gives a polylogarithmic approximation in quasi-polynomial time, or an $n^{\epsilon}$ approximation in polynomial time. Our approach is based on a complex LP-rounding algorithm that combines the notion of divergent trees and Zelikosky’s height reduction via a probabilistic mapping.Non UBCUnreviewedAuthor affiliation: IDSIA, University of LuganoFacult