2003/06/09 by Eran Halperin, Robert Krauthgamer · 2 citations
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Optimization and Search Problems
paper · doi:10.1145/780542.780628
openalex publication_date 2003/06/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
We provide the first hardness result of a polylogarithmic approximation ratio for a natural NP-hard optimization problem. We show that for every fixed ε>0, the GROUP-STEINER-TREE problem admits no efficient log2-ε k approximation, where k denotes the number of groups (or, alternatively, the input size), unless NP has quasi polynomial Las-Vegas algorithms. This hardness result holds even for input graphs which are Hierarchically Well-Separated Trees, introduced by Bartal [FOCS, 1996]. For these trees (and also for general trees), our bound is nearly tight with the log-squared approximation currently known. Our results imply that for every fixed ε>0, the DIRECTED-STEINER TREE problem admits no log2-ε n--approximation, where n is the number of vertices in the graph, under the same complexity assumption.