2024/07/10 by Sarel Cohen, Cohen, Sarel, Lior Kamma +3
Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Formal Methods in Verification #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.2407.07543
openalex publication_date 2024/07/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider the k-outconnected directed Steiner tree problem (k-DST). Given a directed edge-weighted graph G=(V,E,w), where V=\r\∪ S ∪ T, and an integer k, the goal is to find a minimum cost subgraph of G in which there are k edge-disjoint rt-paths for every terminal t∈ T. The problem is know to be NP-hard. Furthermore, the question on whether a polynomial time, subpolynomial approximation algorithm exists for k-DST was answered negatively by Grandoni et al. (2018), by proving an approximation hardness of Ω(|T|/log |T|) under NP≠ ZPP. Inspired by modern day applications, we focus on developing efficient algorithms for k-DST in graphs where terminals have out-degree 0, and furthermore constitute the vast majority in the graph. We provide the first approximation algorithm for k-DST on such graphs, in which the approximation ratio depends (primarily) on the size of S. We present a randomized algorithm that finds a solution of weight at most \mathcal O(k|S|log |T|) times the optimal weight, and with high probability runs in polynomial time.