An approximation algorithm for the prize-collecting connected dominating set problem

In the prize-collecting connected dominating set (PC-CDS) problem, we are given a graph \(G=(V,E)\) $G=(V,E)$ and a non-negative penalty function \(\pi\) $\pi$ on V, the goal is to find a connected node set \(S\subseteq V\) $S\subseteq V$ such that the sum of the size of S and the total penalty on un-dominated nodes is minimized. In this paper, we present an \(O(\log |V|)\) $O(log|V|)$ -approximation algorithm for PC-CDS.