In this paper, we introduce a polynomial-time 2-approximation algorithm for the Unrooted Prize-Collecting Forest with K Components ( \(\hbox {URPCF}_K\) ) problem. Given a graph G and an integer K, \(\hbox {URPCF}_K\) aims to find a forest with exactly K connected components while minimizing the sum of the forest’s cost and the penalties incurred by unspanned vertices. Unlike the rooted version \(\hbox {RPCF}_K\) , where a 2-approximation algorithm exists, solving the unrooted version by guessing roots leads to exponential time complexity for non-constant K. To address this challenge, we propose a rootless growing and rootless pruning algorithm. We also apply this algorithm to improve the approximation ratio for the Prize-Collecting Min-Sensor Sweep Cover problem (PCMinSSC) from 8 to 5.
