Approximation algorithm for unrooted prize-collecting forest with multiple components and its application on prize-collecting sweep coverage

In this paper, we introduce a polynomial-time 2-approximation algorithm for the Unrooted Prize-Collecting Forest with K Components (URPCFK) problem. Given a graph G and an integer K, URPCFK 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 RPCFK, 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.