Algorithms for the Prize-Collecting k-Steiner Tree Problem

Note that for any PC $k$ ST instance ${ℐ}_{\mathrm{PC}k\mathrm{ST}}=(V,E,r,R,k,{\{{\pi }_v\}}_{v\in V},{\{c_e\}}_{e\in E})$ , getting rid of the input of integer $k$ and terminals $R$ yields a PCST instance ${ℐ}_{\mathrm{PCST}}=(V,E,r,{\{{\pi }_v\}}_{v\in V},{\{c_e\}}_{e\in E})$ ; getting rid of the input of penalty costs ${\{{\pi }_v\}}_{v\in v}$ yields a $k$ ST instance ${ℐ}_{k\mathrm{ST}}=(V,E,r,R,k,{\{c_e\}}_{e\in E})$ . Let trees $F_{\mathrm{PC}k\mathrm{ST}}$ , $F_{\mathrm{PCST}}$ , and $F_{k\mathrm{ST}}$ be the optimal solutions for the instances ${ℐ}_{\mathrm{PC}k\mathrm{ST}}$ , ${ℐ}_{\mathrm{PCST}}$ , and ${ℐ}_{k\mathrm{ST}}$ , respectively. For a tree or circle $F$ in $G$ , let ${\mathrm{cost}}_c(F)={\sum }_{e\in E(F)}{c}_e$ and ${\mathrm{cost}}_{\pi }(F)={\sum }_{v\in V\setminus V(F)}{\pi }_v.$ Let ${\mathrm{OPT}}_{\mathrm{PC}k\mathrm{ST}}$ be the total cost of the tree $F_{\mathrm{PC}k\mathrm{ST}}$ , i.e.,

$${\mathrm{OPT}}_{\mathrm{PC}k\mathrm{ST}}={\mathrm{cost}}_c(F_{\mathrm{PC}k\mathrm{ST}})+{\mathrm{cost}}_{\pi }(F_{\mathrm{PC}k\mathrm{ST}});$$

and ${\mathrm{OPT}}_{\mathrm{PCST}}$ denotes the total cost of the tree $F_{\mathrm{PCST}}$ , i.e.,

$${\mathrm{OPT}}_{\mathrm{PCST}}={\mathrm{cost}}_c(F_{\mathrm{PCST}})+{\mathrm{cost}}_{\pi }(F_{\mathrm{PCST}});$$

and ${\mathrm{OPT}}_{k\mathrm{ST}}$ denotes the total cost of the tree $F_{k\mathrm{ST}}$ , i.e.,

$${\mathrm{OPT}}_{k\mathrm{ST}}={\mathrm{cost}}_c(F_{k\mathrm{ST}}).$$

The following lemmas give two lower bounds for the total cost of the tree $F_{\mathrm{PC}k\mathrm{ST}}$ .

Lemma 1 The total cost of the tree $F_{\mathrm{PCST}}$ is at most the total cost of the tree $F_{\mathrm{PC}k\mathrm{ST}}$ , i.e.,

$${\mathrm{OPT}}_{\mathrm{PCST}}⩽{\mathrm{OPT}}_{\mathrm{PC}k\mathrm{ST}}.$$

Proof Note that the optimal solution $F_{\mathrm{PC}k\mathrm{ST}}$ for ${ℐ}_{\mathrm{PC}k\mathrm{ST}}$ is feasible for ${ℐ}_{\mathrm{PCST}}$ . Thus, the total cost of the tree $F_{\mathrm{PC}k\mathrm{ST}}$ is no less than the total cost of the tree $F_{\mathrm{PCST}}$ . Therefore,

$$OP{T}_{\mathrm{PCST}}={\mathrm{cost}}_c(F_{\mathrm{PCST}})+{\mathrm{cost}}_{\pi }(F_{\mathrm{PCST}})⩽$$ $${\mathrm{cost}}_c(F_{\mathrm{PC}k\mathrm{ST}})+{\mathrm{cost}}_{\pi }(F_{\mathrm{PC}k\mathrm{ST}})=$$ $${\mathrm{OPT}}_{\mathrm{PC}k\mathrm{ST}}$$

Lemma 2 The total cost of the tree $F_{k\mathrm{ST}}$ is at most the total cost of the tree $F_{\mathrm{PC}k\mathrm{ST}}$ , i.e.,

$${\mathrm{OPT}}_{k\mathrm{ST}}⩽{\mathrm{OPT}}_{\mathrm{PC}k\mathrm{ST}}.$$

Proof Note that the optimal solution $F_{\mathrm{PC}k\mathrm{ST}}$ for ${ℐ}_{\mathrm{PC}k\mathrm{ST}}$ is feasible for ${ℐ}_{k\mathrm{ST}}$ . Thus, the total edge cost of the tree $F_{\mathrm{PC}k\mathrm{ST}}$ is no less than the total edge cost of the optimal solution $F_{k\mathrm{ST}}$ for ${ℐ}_{k\mathrm{ST}}$ . Therefore,

$${\mathrm{OPT}}_{k\mathrm{ST}}={\mathrm{cost}}_c(F_{k\mathrm{ST}})⩽{\mathrm{cost}}_c(F_{\mathrm{PC}k\mathrm{ST}})⩽$$ $${\mathrm{cost}}_c(F_{\mathrm{PC}k\mathrm{ST}})+{\mathrm{cost}}_{\pi }(F_{\mathrm{PC}k\mathrm{ST}})={\mathrm{OPT}}_{\mathrm{PC}k\mathrm{ST}}$$

Now, we are ready to give our simple approximation algorithm for any PC $k$ ST instance ${ℐ}_{\mathrm{PC}k\mathrm{ST}}$ . We first construct the corresponding PCST instance ${ℐ}_{\mathrm{PCST}}$ and $k$ ST instance ${ℐ}_{k\mathrm{ST}}$ . Then we solve ${ℐ}_{\mathrm{PCST}}$ with the currently best $1.9672$ -approximation algorithm for the PCST and obtain a tree $F_1$ ; solve ${ℐ}_{k\mathrm{ST}}$ with the currently best $4$ -approximation algorithm for the $k$ ST and obtain a tree $F_2$ . Last, we find a minimum spanning tree $F$ in the graph $(V^{\prime },E^{\prime })$ , where $V^{\prime }=V(F_1)\cup V(F_2)$ and $E^{\prime }=E(F_1)\cup E(F_2)$ , and output the tree $F$ as the solution for the PC $k$ ST instance ${ℐ}_{\mathrm{PC}k\mathrm{ST}}$ . The formal description of the simple approximation algorithm is presented as Algorithm 1. For a better understanding of the algorithm, see Fig. 1 and Fig. 2 .

10.26599/TST.2021.9010053.F001 Fig.  1Illustration of how to construct the graph G′ = (V′, E′). The circles and lines in the top graph present the vertices and edges in the graph G. In particular, the blue circles represent the vertices in R. The dotted lines represent the tree ${\text{𝑭}}_{\text{𝟏}}$ obtained from Step 1 in Algorithm 1. The dashed lines represent the tree ${\text{𝑭}}_{\text{𝟐}}$ obtained from Step 2 in Algorithm 1. The bottom graph $\text{𝑮}{}^{\prime }$ can be constructed by combining the trees ${\text{𝑭}}_{\text{𝟏}}$ and ${\text{𝑭}}_{\text{𝟐}}$ .

10.26599/TST.2021.9010053.F002 Fig.  2Illustration of how to obtain a feasible solution F from the graph ${\text{𝑮}}^{\prime }=$ (V′, E′). The dotted lines represent a tree in the minimum spanning tree F of $\text{𝑮}{}^{\prime }$ , where the tree F is obtained from Step 3 in Algorithm 1.

The following theorem gives the main result of the simple approximation algorithm.

Theorem 1 Algorithm 1 has an approximation ratio of $5.9672$ .

Proof The tree $F$ is feasible for ${ℐ}_{\mathrm{PC}k\mathrm{ST}}$ , because $F$ connects more vertices in $R$ than the tree $F_2$ and $F_2$ connects at least $k$ vertices in $R$ .

Note that $E(F)\subseteq E(F_1)\cup E(F_2)$ and $V\setminus V(F)\subseteq V\setminus V(F_1)$ . Hence,

$${\mathrm{cost}}_c(F)+{\mathrm{cost}}_{\pi }(F)⩽$$ $${\mathrm{cost}}_c(F_1)+{\mathrm{cost}}_c(F_2)+{\mathrm{cost}}_{\pi }(F_1)=$$ $$({\mathrm{cost}}_c(F_1)+{\mathrm{cost}}_{\pi }(F_1))+{\mathrm{cost}}_c(F_2)⩽$$ $$1.9672{\mathrm{OPT}}_{\mathrm{PCST}}+4{\mathrm{OPT}}_{k\mathrm{ST}}⩽$$ $$5.9672{\mathrm{OPT}}_{\mathrm{PC}k\mathrm{ST},}$$

where the last inequality follows from Lemmas 1 and 2.

This paper studies the PC $k$ ST and proposes two approximation algorithms with ratios of $5.9672$ and $5$ . We do believe that the PC $k$ ST could have many practical applications, because it generalizes both the PCST and $k$ ST. Actually, when setting $r\in R$ , $k=|R|$ , and ${\pi }_v=0$ for every $v\in V$ , the PC $k$ ST becomes the Steiner tree (ST) problem; when setting $R=V$ , the PC $k$ ST becomes the $k$ -prize-collecting Steiner tree ( $k$ PCST) problem. Our future research direction is to reduce the gap for the PC $k$ ST between the currently best ratio of $5$ and the hardness of approximation of $2$ .