An efficient cost-sharing mechanism for the prize-collecting Steiner forest problem

In an instance of the prize-collecting Steiner forest problem (PCSF) we are given an undirected graph G = (V, E), non-negative edge-costs c(e) for all e ε E, terminal pairs R = {(si, ti)}1≤i≤k, and penalties π1,...,πk. A feasible solution (F, Q) consists of a forest F and a subset Q of terminal pairs such that for all (si, ti) ε R either si, ti are connected by F or (si, ti) ε Q. The objective is to compute a feasible solution of minimum cost c(F) + π (Q).