A Practical Sublinear Approximation for Group Steiner Tree

The Group Steiner Tree Problem (GSTP) is widely used in graph data management and mining, yet existing algorithms trade off practical efficiency against approximation quality: efficient methods offer only linear guarantees, while those with sublinear guarantees fail to scale to large graphs. In this paper, we present MonoGST+, a novel algorithm for GSTP that breaks this trade-off by achieving a sublinear approximation while matching the running time of state-of-the-art linear-approximation solvers. Our approach extends a 2-star-based reduction to weighted set cover with a suspendable search and a monotonicity- and unimodality-aware pruning strategy to eliminate redundant computation. Experiments on multiple real-world datasets demonstrate the effectiveness and efficiency of MonoGST+, providing a practical, high-quality solution for GSTP applications.