A primal-dual approximation algorithm for the k-prize-collecting minimum vertex cover problem with submodular penalties

Abstract

In this paper, we consider the k-prize-collecting minimum vertex cover problem with submodular penalties, which generalizes the well-known minimum vertex cover problem, minimum partial vertex cover problem and minimum vertex cover problem with submodular penalties. We are given a cost graph G=(V,E;c) and an integer k. This problem determines a vertex set S\subseteq V such that S covers at least k edges. The objective is to minimize the total cost of the vertices in S plus the penalty of the uncovered edge set, where the penalty is determined by a submodular function. We design a two-phase combinatorial algorithm based on the guessing technique and the primal-dual framework to address the problem. When the submodular penalty cost function is normalized and nondecreasing, the proposed algorithm has an approximation factor of 3. When the submodular penalty cost function is linear, the approximation factor of the proposed algorithm is reduced to 2, which is the best factor if the unique game conjecture holds.

Key words： vertex cover; k-prize-collecting; primal-dual; approximation algorithm

1 Introduction

The minimum vertex cover problem (MVC) is one of the most important and fundamental problems in graph theory and combinatorial optimization [1,2]. In the MVC, we are given a graph G=(V,E) with vertex set V=\{v_1,v_2,\dots ,v_n\} and edge set E=\{e_1,e_2,\dots ,e_m\}. For each vertex v\in V, there is an associated nonnegative cost c(v). The MVC finds a vertex set S to cover all the edges of the graph such that the total cost of the vertices in S is minimized, where an edge is said to be covered by S if at least one of its incident vertices is in S. For this problem, Karp [1] proved it is NP-hard. This result is improved by Khot and Regev [3], who proved that the MVC cannot be approximated within 2-\epsilon for any \epsilon >0 under the unique game conjecture. Based on the LP-rounding, Hochbaum [4] presented a 2-approximation algorithm with a running time of O(n^3). Based on the primal-dual framework, Bar-Yehuda and Even [5] proposed a linear-time 2-approximation algorithm.

Bshouty and Burroughs [6] proposed the minimum partial vertex cover problem (MPVC) which is a generalization of the MVC. In this variant, we are given an additional parameter k, which is called the covering requirement. The objective of the MPVC is to find a minimum cost subset of V that covers at least k edges in E. If k=m, the MPVC is exactly the MVC. For the MPVC, Bshouty and Burroughs [6] presented a 2-approximation algorithm with a running time of O(n^3) based on the LP-rounding. On the basis of Lagrangian relaxation, Hochbaum [7] presented a 2-approximation algorithm with a running time of O(nm\log {\displaystyle \frac{n^2}{m}}\log n). Based on the local-ratio technique, Bar-Yehuda [8] presented a 2-approximation algorithm with a running time of O(n^2). Furthermore, on the basis of the primal-dual framework, Gandhi et al. [9] presented a 2-approximation algorithm with a running time of O(n(n\log n+m)) and Julián [10] reduced the running time to O(n\log n+m) based on the pruning technique.

Karp [1] proposed the prize-collecting minimum vertex cover problem (PCMVC), which is another generalization of the MVC. In this variant, each edge e can be either covered by a vertex set or uncovered and a penalty \pi (e) is paid. The objective is to minimize the total cost of vertices in this set plus the overall penalty of uncovered edges. If \pi (e)=\mathrm{\infty } for every edge e, the PCMVC is exactly the MVC. For the PCMVC, based on the LP-rounding technique, Hochbaum [11] presented a 2-approximation algorithm with a running time of O(n^3). Based on the primal-dual framework, Bar-Yehuda and Rawitz [12] proposed a linear-time 2-approximation algorithm.

Submodular function is a set function with the property of decreasing marginal return, and plays a key role in combinatorial optimization somewhat similar to that played by convex/concave function in continuous optimization. There has been a lot of work on the submodular function optimization [13-16]. The minimum submodular vertex cover problem (MSVC) is one type of submodular function optimization problem and its objective is to find a minimum cost subset S of V to cover all the edges, where the cost of S is determined by a submodular function. Iwata and Nagano [17] presented a combinatorial 2-approximation algorithm based on the primal-dual framework. If the submodular function is linear, the MSVC is exactly the MVC. Recently, Xu et al. [18] considered the minimum submodular vertex cover problem with submodular penalties (MSVCS), which is a generalization of the PCMVC and MSVC. In the MSVCS, the cost of vertex set and the penalty of uncovered edge set are determined by two submodular function, respectively. If the penalty of any edge set is infinity, the MSVCS is exactly the MSVC; If two submodular functions are all linear, the MSVCS is exactly the PCMVC. Xu et al. [18] presented a combinatorial 4-approximation algorithm by relaxing the dual program to a slightly weaker version, which was improved by Kamiyama [19] with a 3-approximation algorithm.

Motivated by the above work, in this paper, we consider the k-prize-collecting minimum vertex cover problem with submodular penalties (k-PCVCS), which is a generalization of the MVC [1], MPVC [6], and PCMVC [11]. The k-PCVCS finds a vertex set S that covers at least k edges, and the objective is to minimize the total cost of the vertices in S plus the penalty of the uncovered edge set, where k\le m, and the penalty is determined by a submodular function. In this paper, we design a two-phase combinatorial algorithm based on the guessing technique and the primal-dual framework to address the k-PCVCS. When the submodular penalty cost function is normalized and nondecreasing, the proposed algorithm has an approximation factor of 3. When the submodular penalty cost function is linear, this problem is a special case of the P-prize-collecting set cover problem [20]. For this problem, the approximation factor of the algorithm in [20] is 4, which is the current best factor. In this paper, we prove that the approximation factor of the two-phase combinatorial algorithm is 2, which is the best factor if the unique game conjecture holds.

The remainder of this paper is structured as follows. In Section 2, we provide basic definitions and a formal problem statement. In Section 3, we focus on the k-PCVCS and propose the two-phase combinatorial algorithm. In Section 4, we provide a brief conclusion.

2 Preliminaries

Let E be a given ground set, and let \pi (\cdot ):2^E\to {\mathbb{R}}_{\ge 0} be a real-valued set function defined on all subsets of E. If

\begin{array}{r}\pi (E_1)+\pi (E_2)\ge \pi (E_1\cup E_2)+\pi (E_1\cap E_2),\mathrm{\forall }{E}_1,E_2\subseteq E,\end{array}

then \pi (\cdot ) is called a submodular function. The submodular function is nondecreasing if \pi (E_1)\le \pi (E_2), \mathrm{\forall }{E}_1\subseteq E_2\subseteq E. The submodular function \pi (\cdot ) is normalized if \pi (\mathrm{\varnothing })=0. If \pi (\cdot ) is normalized and

\begin{array}{r}\pi (E_1)+\pi (E_2)=\pi (E_1\cup E_2)+\pi (E_1\cap E_2),\mathrm{\forall }{E}_1,E_2\subseteq E,\end{array}

then \pi (\cdot ) is called a linear function.

The k-prize-collecting minimum vertex cover problem with submodular penalties (k-PCVCS) is defined as follows: consider an instance \mathcal{I}=(G;c,\pi ;k), where G=(V,E) is a graph with V=\{v_1,v_2,\dots ,v_n\} and E=\{e_1,e_2,\dots , e_m\}, k is an integer satisfying 0\le k\le m, c:V\to {\mathbb{R}}^{+} is a cost function and \pi (\cdot ):2^E\to {\mathbb{R}}_{\ge 0} is a submodular penalty cost function. An edge e is covered by a set if at least one of the incident vertices of e is in this set. The k-PCVCS finds a pair (S,R), where S\subseteq V is the vertex set that covers at least k edges, and R\subseteq E is the set of edges uncovered by S. The objective is to minimize the cost c(S)+\pi (R), where

c(S)=\sum _{v:v\in S}c(v).

To obtain the expected approximation factor, a preprocessing step is required: guessing the maximum cost vertex v_{\mathrm{m}\mathrm{a}\mathrm{x}}^{\ast } in an optimal solution, where

v_{\mathrm{m}\mathrm{a}\mathrm{x}}^{\ast }=\arg \underset{v\in S^{\ast }}{max}c(v),

and (S^{\ast },R^{\ast }) is an optimal solution for instance \mathcal{I}. Using a preprocessing step: guessing the maximum cost of a vertex in an optimal solution. We can assume that v_{\mathrm{m}\mathrm{a}\mathrm{x}}^{\ast } is known.

Using v_{\mathrm{m}\mathrm{a}\mathrm{x}}^{\ast }, we construct a graph G\setminus \{v_{\mathrm{m}\mathrm{a}\mathrm{x}}^{\ast }\} by removing vertex v_{\mathrm{m}\mathrm{a}\mathrm{x}}^{\ast }, i.e., G\setminus \{v_{\mathrm{m}\mathrm{a}\mathrm{x}}^{\ast }\}=(V\setminus \{v_{\mathrm{m}\mathrm{a}\mathrm{x}}^{\ast }\},E\setminus \delta (\{v_{\mathrm{m}\mathrm{a}\mathrm{x}}^{\ast }\})), where \delta (\{v_{\mathrm{m}\mathrm{a}\mathrm{x}}^{\ast }\}) is the set of edges covered by vertex v_{\mathrm{m}\mathrm{a}\mathrm{x}}^{\ast }. Then, we construct an auxiliary instance \mathcal{I}\setminus \{v_{\mathrm{m}\mathrm{a}\mathrm{x}}^{\ast }\}=(G\setminus \{v_{\mathrm{m}\mathrm{a}\mathrm{x}}^{\ast }\};c^{\prime },\pi ;k-|\delta (\{v_{\mathrm{m}\mathrm{a}\mathrm{x}}^{\ast }\})|) of \mathcal{I}=(G;c,\pi ;k), where for any vertex v\inV\setminus \{v_{\mathrm{m}\mathrm{a}\mathrm{x}}^{\ast }\}

(1)\begin{array}{r}{c}^{\prime }(v)=\{\begin{array}{rl}& c(v),\mathrm{i}\mathrm{f}c(v)\le c(v_{\mathrm{m}\mathrm{a}\mathrm{x}}^{\ast });\\ & +\mathrm{\infty },\text{otherwise.}\end{array}\end{array}

Let OP{T}_{\mathcal{I}\setminus \{v_{\mathrm{m}\mathrm{a}\mathrm{x}}^{\ast }\}} be the optimal objective value of instance \mathcal{I}\setminus \{v_{\mathrm{m}\mathrm{a}\mathrm{x}}^{\ast }\}. We can obtain the following lemma.

Lemma 2.1 OP{T}_{\mathcal{I}\setminus \{v_{\mathrm{m}\mathrm{a}\mathrm{x}}^{\ast }\}}+c(v_{\mathrm{m}\mathrm{a}\mathrm{x}}^{\ast })=OP{T}_{\mathcal{I}}, where OP{T}_{\mathcal{I}}=c(S^{\ast })+\pi (R^{\ast }) is the objective value of the optimal solution (S^{\ast },R^{\ast }) of instance \mathcal{I}.

Proof By the definition of c^{\prime }(\cdot ) and v_{\mathrm{m}\mathrm{a}\mathrm{x}}^{\ast }=\arg \underset{v\in S^{\ast }}{max}c(v), we have

OP{T}_{\mathcal{I}}=\sum _{v:v\in S^{\ast }}c(v)=\sum _{v:v\in S^{\ast }}{c}^{\prime }(v).

Since S^{\ast } covers at least k edges in E, S^{\ast }\setminus \{v_{\mathrm{m}\mathrm{a}\mathrm{x}}^{\ast }\} covers at least k-|\delta (v_{\mathrm{m}\mathrm{a}\mathrm{x}}^{\ast })| edges in E\setminus \delta (\{v_{\mathrm{m}\mathrm{a}\mathrm{x}}^{\ast }\}), and (S^{\ast }\setminus \{v_{\mathrm{m}\mathrm{a}\mathrm{x}}^{\ast }\},R^{\ast }) is a feasible solution of instance \mathcal{I}\setminus \{v_{\mathrm{m}\mathrm{a}\mathrm{x}}^{\ast }\}, and we have

(2)\begin{array}{rl}OP{T}_{\mathcal{I}\setminus \{v_{\mathrm{m}\mathrm{a}\mathrm{x}}^{\ast }\}}& \le c^{\prime }(S^{\ast })-c^{\prime }(v_{\mathrm{m}\mathrm{a}\mathrm{x}}^{\ast })+\pi (R^{\ast })\\ & =OP{T}_{\mathcal{I}}-c(v_{\mathrm{m}\mathrm{a}\mathrm{x}}^{\ast }),\end{array}

where the inequality follows from the OP{T}_{\mathcal{I}\setminus \{v_{\mathrm{m}\mathrm{a}\mathrm{x}}^{\ast }\}} is the optimal objective value of instance \mathcal{I}\setminus \{v_{\mathrm{m}\mathrm{a}\mathrm{x}}^{\ast }\}, and the equality follows from the definition of c^{\prime }(\cdot ) in Eq. (1).

Let (S^{\prime },R^{\prime }) be an optimal solution of instance \mathcal{I}\setminus \{v_{\mathrm{m}\mathrm{a}\mathrm{x}}^{\ast }\}. By the definition of c^{\prime }(\cdot ) and \mathcal{I}\setminus \{v_{\mathrm{m}\mathrm{a}\mathrm{x}}^{\ast }\}\le OP{T}_{\mathcal{I}}-c(v_{\mathrm{m}\mathrm{a}\mathrm{x}}^{\ast })\le +\mathrm{\infty }, it is not hard to obtain that

c(v)=c^{\prime }(v),\mathrm{\forall }v\in S^{\prime }.

For instance \mathcal{I}, S^{\prime } covers at least k-|\delta (v_{\mathrm{m}\mathrm{a}\mathrm{x}}^{\ast })| edges in E\setminus \delta (\{v_{\mathrm{m}\mathrm{a}\mathrm{x}}^{\ast }\}), and S^{\prime }\cup \{v_{\mathrm{m}\mathrm{a}\mathrm{x}}^{\ast }\} covers at least k edges in E. Thus, (S^{\prime }\cup \{v_{\mathrm{m}\mathrm{a}\mathrm{x}}^{\ast }\},R^{\prime }) is a feasible solution of instance \mathcal{I}, and the optimal objective value of instance \mathcal{I} is

\begin{array}{rl}OP{T}_{\mathcal{I}}& \le c(S^{\prime }\cup \{v_{\mathrm{m}\mathrm{a}\mathrm{x}}^{\ast }\})+\pi (R^{\prime })\\ & =c(S^{\prime })+c(v_{\mathrm{m}\mathrm{a}\mathrm{x}}^{\ast })+\pi (R^{\prime })\\ & =c^{\prime }(S^{\prime })+\pi (R^{\prime })+c(v_{\mathrm{m}\mathrm{a}\mathrm{x}}^{\ast })\\ & =OP{T}_{\mathcal{I}\setminus \{v_{\mathrm{m}\mathrm{a}\mathrm{x}}^{\ast }\}}+c(v_{\mathrm{m}\mathrm{a}\mathrm{x}}^{\ast }).\end{array}

This statement and inequality Eq. (2) imply that the lemma holds. 　　　　　　　　　　　　　　　　　　　　 　　□

3 A combinatorial algorithm for k-PCVCS

In this section, we first present a two-phase primal-dual approximation algorithm for instance \mathcal{I}\setminus \{v_{\mathrm{m}\mathrm{a}\mathrm{x}}^{\ast }\}. Then, using this two-phase primal-dual algorithm and the guessing technique, we present a combinatorial approximation algorithm for instance \mathcal{I}. If the submodular penalty cost function \pi (\cdot ) is normalized and nondecreasing, we prove that the approximation factor of this combinatorial algorithm is 3. In particular, if \pi (\cdot ) is linear, we prove that this approximation factor is reduced to 2.

3.1 A two-phase algorithm for instance \mathcal{I}\setminus \{v_{\mathrm{m}\mathrm{a}\mathrm{x}}^{\ast }\}

For simplicity of notation, we use \mathcal{I}=(G;c,\pi ;k) to denote \mathcal{I}\setminus \{v_{\mathrm{m}\mathrm{a}\mathrm{x}}^{\ast }\}=(G\setminus \{v_{\mathrm{m}\mathrm{a}\mathrm{x}}^{\ast }\};c^{\prime },\pi ;k-|\delta (\{v_{\mathrm{m}\mathrm{a}\mathrm{x}}^{\ast }\})|).

We introduce a binary variable x_v for each vertex v\in V, where

\begin{array}{r}{x}_v=\{\begin{array}{rl}& 1,\text{if}v\text{is selected to cover some edges},\\ & 0,\text{otherwise.}\end{array}\end{array}

For each subset R\subseteq E, we introduce a binary variable z_R, where

\begin{array}{r}{z}_R=\{\begin{array}{rl}& 1,\text{if}R\text{is the set of the uncovered edges},\\ & 0,\text{otherwise.}\end{array}\end{array}

We have the following integer linear program for the k-PCVCS.

(3)\begin{array}{rl}& min\sum _{v:v\in V}c(v)x_v+\sum _{R:R\subseteq E}\pi (R)z_R\\ \mathit{s}\mathit{.}\mathit{t}\mathit{.}& \sum _{v:v\in V(e)}{x}_v+\sum _{R:R\subseteq E\mathrm{a}\mathrm{n}\mathrm{d}e\in R}{z}_R\ge 1,\mathrm{\forall }e\in E,\\ & \sum _{R:R\subseteq E}|R|z_R\le m-k,\\ & x_v,z_R\in \{0,1\},\mathrm{\forall }v\in V,\mathrm{\forall }R\subseteq E,\end{array}

where V(e) is the set of incident vertices of edge e, the first set of constraints of Eq. (3) guarantees that each edge e\in E is either covered by at least one of its incident vertices or in the set of uncovered edges, and the second constraint of Eq. (3) guarantees that the number of uncovered edges of any feasible solution is at most m-k. Relaxing the integrality constraints, we obtain the linear program as follows.

\begin{array}{rl}& min\sum _{v:v\in V}c(v)x_v+\sum _{R:R\subseteq E}\pi (R)z_R\\ \mathit{s}\mathit{.}\mathit{t}\mathit{.}& \sum _{v:v\in V(e)}{x}_v+\sum _{R:R\subseteq E\mathrm{a}\mathrm{n}\mathrm{d}e\in R}{z}_R\ge 1,\mathrm{\forall }e\in E,\\ & \sum _{R:R\subseteq E}|R|z_R\le m-k,\\ & x_v\ge 0\mathrm{a}\mathrm{n}\mathrm{d}{z}_R\ge 0,\mathrm{\forall }v\in V,\mathrm{\forall }R\subseteq E.\end{array}

Note that we need not to add the constraints x_v\le 1 and z_R\le 1 since they are automatically satisfied in an optimal solution. The corresponding dual program is

(4)\begin{array}{rl}& max\sum _{e:e\in E}{y}_e-(m-k)\gamma \\ s.t.& \sum _{e:e\in \delta (\{v\})}{y}_e\le c(v),\mathrm{\forall }v\in V,\\ & \sum _{e:e\in R}{y}_e-|R|\gamma \le \pi (R),\mathrm{\forall }R\subseteq E.\\ & y_e\ge 0\mathrm{a}\mathrm{n}\mathrm{d}\gamma \ge 0,\mathrm{\forall }e\in E,\end{array}

where \delta (\{v\}) is the set of edges covered by vertex v. For a dual feasible solution (\mathit{y},\gamma )=(\{y_e{\}}_{e\in E},\gamma ) of Eq. (4), we say that a vertex v\in V is tight if \sum _{e:e\in \delta (\{v\})}{y}_e=c(v), and an edge set R\subseteq E is tight if \sum _{e:e\in R}{y}_e=\pi (R).

Then, we present the two-phase primal-dual algorithm:

Phase 1 We keep \gamma =0 and find a dual feasible solution of ({\mathit{y}}^{\prime },0) such that each edge is covered by a tight vertex or is in a tight edge set. To obtain this feasible solution, we start from the trivial dual feasible solution of zero.

Initially, \gamma is frozen, the other dual variables are active, and their dual values are equal to 0. The dual values for the active dual variables are increased simultaneously until either some vertex or some edge set becomes tight. If a vertex becomes tight, then it is added to the tight vertex set V^{tight}, and the dual variables of all active edges covered by this vertex are frozen. Otherwise, if an edge set becomes tight, the dual variables of all active edges in this edge set are frozen. The process is iterated until all dual variables \{y_e{\}}_{e\in E} are frozen. For any e\in E, the dual value for any dual variables will no longer increase after becoming frozen, and let y_e^{\prime } be the dual value when it is frozen. If |\delta (V^{tight})|\ge k, then output pair (S,R):=(V^{tight},E\setminus \delta (V^{tight})) and stop the algorithm, where \delta (V^{tight}) is the set of edges covered by V^{tight}; otherwise, go to Phase 2.

Phase 2 Based on increasing dual variable \gamma, we select some vertices added to the tight vertex set V^{tight} such that V^{tight} covers at least k edges. We start from the dual feasible solution ({\mathit{y}}^{\prime },0) for dual program Eq. (4), which is proven in Lemma 3.3.

Initially, set the dual feasible solution (\mathit{y},\gamma )=({\mathit{y}}^{\prime },0); all dual variables covered by V^{tight} are frozen, and the other dual variables are active. The dual value of the active dual variables are increased simultaneously until a vertex becomes tight. This vertex is added to the tight vertex set V^{tight}, and the dual variables of all active edges covered by this vertex are frozen. This process is iterated until |\delta (V^{tight})|\ge k and output pair (S,R), where S=V^{tight} and R=E\setminus \delta (S).

For any e\in E, let y_e^{″} be the dual value for any e\in E when it is frozen. Since the dual value for any e\in E will no longer increase after y_e is frozen, ({\mathit{y}}^{″},\gamma ) is a dual feasible solution, which is proven in Lemma 3.5. Since the dual variable \gamma continues increasing until |\delta (V^{tight})|\ge k, we have

\gamma =\underset{e:e\in E}{max}(y_e^{″}-y_e^{\prime }).

We propose the detailed primal-dual algorithm in Algorithm 1.

Full size|PPT slide

Next, we use an example to illustrate our algorithm: we are given an instance \mathcal{I}=(G;c,\pi ;k) (Fig.1), where G=(V,E) and k=3. The vertex cost is c(v_1)=1, c(v_2)=8, and c(v_3)=c(v_4)=9, and the penalty function

Fig.1 For instance \mathcal{I}=(G;c,\pi ;k), we illustrate Phase 1 in a, b and c; and illustrate Phase 2 in d and e

Full size|PPT slide

\begin{array}{r}\pi (\{E^{\prime }\})=\{\begin{array}{rl}& 2,\text{if}{E}^{\prime }\subseteq E\mathrm{a}\mathrm{n}\mathrm{d}|T|=1,\\ & 3,\text{if}{E}^{\prime }\subseteq E\mathrm{a}\mathrm{n}\mathrm{d}|T|=2,\\ & 4,\text{if}{E}^{\prime }\subseteq E\mathrm{a}\mathrm{n}\mathrm{d}|T|=3,\\ & 5,\text{if}{E}^{\prime }=E.\end{array}\end{array}

Lemma 3.1 Algorithm 1 can be implemented in O(n^{16}\cdot \rho +n^{17}), where \rho is the time for one function evaluation, i.e., the time to determine \pi (S) given S.

Proof It is easy to obtain that the running time of Algorithm 1 is determined by the running time of Phase 1. Let E^{act}(j) be the set of active edges generated after the jth loop (or before the (j+1)th loop) of Phase 1, i.e., E^{act}(0)=E before the 1-loop.

In any loop of Phase 1, without loss of generality, we assume that the number of this loop is j+1, and simultaneously increase the dual variable \{y_e{\}}_{e\in E^{act}(j)} until either some vertex v becomes tight or some edge set E^{\prime } becomes tight. The tight vertex v can be determined by calculating the minimum value

\begin{array}{r}{\mathrm{\Delta }}_v=\underset{v:E^{act}(j)\cap \delta (v)\ne \mathrm{\varnothing }}{min}\frac{c(v)-\sum _{e:e\in \delta (v)\setminus E^{act}(j)}{y}_e}{|E^{act}(j)\cap \delta (v)|}.\end{array}

Clearly, the value of {\mathrm{\Delta }}_v can be found in O(n) by \{v:E^{act}(j)\cap \delta (v)\ne \mathrm{\varnothing }\}\subseteq V and |V|=n.

The tight edge set E^T can be determined by calculating the minimum value

\begin{array}{rl}{\mathrm{\Delta }}_{E^T}& =\underset{E^{\prime }:E^{act}(j)\cap E^{\prime }\ne \mathrm{\varnothing }}{min}\frac{\pi (E^{\prime })-\sum _{e:e\in E^{\prime }\setminus E^{act}(j)}{y}_e}{|E^{act}(j)\cap E^{\prime }|}\\ & =\underset{E_1^{\prime }\cup E_2^{\prime }:E_1^{\prime }\subseteq E^{act}(j)\mathrm{a}\mathrm{n}\mathrm{d}{E}_2^{\prime }\subseteq E\setminus E^{act}(j)}{min}\frac{\pi (E_1^{\prime }\cup E_2^{\prime })-\sum _{e:e\in E_2^{\prime }}{y}_e}{|E_1^{\prime }|}\\ & =\underset{E_1^{\prime }:E_1^{\prime }\subseteq E^{act}(j)}{min}\frac{\underset{E_2^{\prime }:E_2^{\prime }\subseteq E\setminus E^{act}(j)}{min}(\pi (E_1^{\prime }\cup E_2^{\prime })-\sum _{e:e\in E_2^{\prime }}{y}_e)}{|E_1^{\prime }|}\\ & =\underset{E_1^{\prime }:E_1^{\prime }\subseteq E^{act}(j)}{min}\frac{\underset{E_2^{\prime }:E_2^{\prime }\subseteq E\setminus E^{act}(j)}{min}(w_{E_1^{\prime },j}(S))}{|E_1^{\prime }|}\\ & =\underset{E_1^{\prime }:E_1^{\prime }\subseteq E^{act}(j)}{min}\frac{w(E_1^{\prime })}{|E_1^{\prime }|},\end{array}

where the relationship of the sets is shown in Fig.2, we define w_{E_1^{\prime },j}(E_1^{\prime })=\pi (E_1^{\prime }\cup E_2^{\prime })-\sum _{e:e\in E_2^{\prime }}{y}_e for any E_2^{\prime }\subseteq E\setminusE^{act}(j), and w(E_1^{\prime })=\underset{E_2^{\prime }:E_2^{\prime }\subseteq E\setminus E^{act}(j)}{min}(\pi (E_1^{\prime }\cup E_2^{\prime })-\sum _{e:e\in E_2^{\prime }}{y}_e) for any E_1^{\prime }\subseteq E^{act}(j). This means, for any E_1^{\prime }\subseteq E^{act}(j), w_{E_1^{\prime },j}(\cdot ):2^{E\setminus E^{act}(j)}\to {\mathbb{R}}_{\ge 0} is a real-valued set function defined on all subsets of E\setminus E^{act}(j), where the non negativity of w_{E_1^{\prime },j}(\cdot ) comes from the second set of constraints of Eq. (4) and \gamma =0 in Phase 1.

Fig.2 The relationship of E^{\prime }, E_1^{\prime } and E_2^{\prime }

Full size|PPT slide

Given an edges set E_1^{\prime }\subseteq E^{act}(j), for any two subsets E_2^{\prime }(1),E_2^{\prime }(2)\subseteq E\setminus E^{act}(j), we have

\begin{array}{rl}& w_{E_1^{\prime },j}(E_2^{\prime }(1))+w_{E_1^{\prime },j}(E_2^{\prime }(2))\\ =& \pi (E_1^{\prime }\cup E_2^{\prime }(1))-\sum _{e:e\in E_2^{\prime }(1)}{y}_e+\pi (E_1^{\prime }\cup E_2^{\prime }(2))-\sum _{e:e\in E_2^{\prime }(2)}{y}_e\\ \ge & \pi (E_1^{\prime }\cup (E_2^{\prime }(1)\cup E_2^{\prime }(2)))-\sum _{e:e\in E_2^{\prime }(1)\cup E_2^{\prime }(2)}{y}_e\\ & +\pi (E_1^{\prime }\cup (E_2^{\prime }(1)\cap E_2^{\prime }(2)))-\sum _{e:e\in E_2^{\prime }(1)\cap E_2^{\prime }(2)}{y}_e\\ =& w_{E_1^{\prime },j}(E_2^{\prime }(1)\cup E_2^{\prime }(2))+w_{E_1^{\prime },j}(E_2^{\prime }(1)\cap E_2^{\prime }(2)),\end{array}

where the inequality follows from the submodularity of \pi (\cdot ). Thus, w_{E_1^{\prime },j}(\cdot ) is a submodular function, and by [21]

(5)\begin{array}{r}w(E_1^{\prime })\mathrm{c}\mathrm{a}\mathrm{n}\mathrm{b}\mathrm{e}\mathrm{f}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{d}\mathrm{i}\mathrm{n}O(n^7\cdot \rho +n^8),\end{array}

where w(E_1^{\prime })=\underset{E_2^{\prime }\subseteq E\setminus E^{act}(j)}{min}(w_{E_1^{\prime },j}(E_2^{\prime })), and \rho is the time for one function evaluation, i.e., the time to determine \pi (E^{\prime }) given E^{\prime }\subseteq E.

For any two subsets E_1^{\prime }(1),E_1^{\prime }(2)\subseteq E^{act}(j), let

\begin{array}{rlr}& & S_1^{\prime }=\arg \underset{S:S\subseteq E\setminus E^{act}(j)}{min}{w}_{E_1^{\prime }(1),j}(S)\\ & \mathrm{a}\mathrm{n}\mathrm{d}& S_2^{\prime }=\arg \underset{S:S\subseteq E\setminus E^{act}(j)}{min}{w}_{E_1^{\prime }(2),j}(S),\end{array}

we have

\begin{array}{rl}& w(E_1^{\prime }(1))+w(E_1^{\prime }(2))\\ =& w_{E_1^{\prime }(1),j}(S_1^{\prime })+w_{E_1^{\prime }(2),j}(S_2^{\prime })\\ =& \pi (E_1^{\prime }(1)\cup S_1^{\prime })-\sum _{e:e\in S_1^{\prime }}{y}_e+\pi (E_1^{\prime }(2)\cup S_2^{\prime })-\sum _{e:e\in S_2^{\prime }}{y}_e\\ \ge & \pi ((E_1^{\prime }(1)\cup S_1^{\prime })\cup (E_1^{\prime }(2)\cup S_2^{\prime }))-\sum _{e:e\in S_1^{\prime }\cup S_2^{\prime }}{y}_e\\ & +\pi ((E_1^{\prime }(1)\cup S_1^{\prime })\cap (E_1^{\prime }(2)\cup S_2^{\prime }))-\sum _{e:e\in S_1^{\prime }\cap S_2^{\prime }}{y}_e\\ \ge & \underset{S:S\subseteq E\setminus E^{act}(j)}{min}(\pi ((E_1^{\prime }(1)\cup E_1^{\prime }(2))\cup S)-\sum _{e:e\in S}{y}_e)\\ & +\underset{S:S\subseteq E\setminus E^{act}(j)}{min}(\pi ((E_1^{\prime }(1)\cap E_1^{\prime }(2))\cup S)-\sum _{e:e\in S}{y}_e),\\ =& w(E_1^{\prime }(1)\cup E_1^{\prime }(2))+w(E_1^{\prime }(1)\cap E_1^{\prime }(2)),\end{array}

where the first inequality follows from the submodularity of \pi (\cdot ). Therefore, w(\cdot ) is a submodular function.

Thus, similar to the optimization problem of minimizing the ratio of a submodular function and a positive linear function [21], the value of {\mathrm{\Delta }}_{E^T} can be computed in O(n^{15}\cdot \rho +n^{16}) by (5). Since at least one edge is frozen in each loop of Phase 1, and Algorithm 1 can be implemented in O(n^{16}\cdot \rho +n^{17}).　　□

Let (S^{\ast },R^{\ast }) be the optimal pair for the k-PCVCS, let OPT be the objective value for (S^{\ast },R^{\ast }), and let (S,R) be the output pair by Algorithm 1 and OUT be the objective value for (S,R). Since (S,R) can be generated by either Phase 1 or Phase 2, we first consider the case in which (S,R) is generated by Phase 1.

Let ({\mathit{y}}^{\prime },0) be the dual value after Phase 1.

Lemma 3.2 ({\mathit{y}}^{\prime },0) is a feasible solution for dual program Eq. (4).

Proof In Phase 1, when any vertex becomes tight, the dual variable of the edges incident to this vertex will no longer increase, which means

\begin{array}{r}\sum _{e:e\in \delta (v)}{y}_e^{\prime }\le c(v),\mathrm{\forall }v\in V.\end{array}

Similarly, we have

(6)\begin{array}{r}\sum _{e:e\in E^{\prime }}{y}_e^{\prime }\le \pi (E^{\prime }),\mathrm{\forall }{E}^{\prime }\subseteq E.\end{array}

Therefore, ({\mathit{y}}^{\prime },0) is a feasible solution for dual program Eq. (4). 　　　　　　　　　　　　　　　　　　　　　□

Lemma 3.3 If the pair (S,R) is generated by Phase 1, the cost of the vertex set of S is

c(S)=\sum _{v:v\in S}c(v)\le 2\sum _{e:e\in \delta (S)}{y}_e^{\prime }.

Proof Since any vertex v\in S is tight, we have

\begin{array}{rl}c(S)=& \sum _{v:v\in S}c(v)=\sum _{v:v\in S}\sum _{e:e\in \delta (v)}{y}_e^{\prime }=\sum _{e:e\in \delta (S)}{y}_e^{\prime }|V(e)\cap S|\\ \le & 2\sum _{e:e\in \delta (S)}{y}_e^{\prime },\end{array}

where V(e) is the set of incident vertices of edge e and the first inequality follows from the fact that any edge in E is incident to two vertices. 　　　　　　　　　　 　　　　　　　　□

In Phase 1, let \mathcal{T} be the set of tight edge sets, i.e., for any E^T\in \mathcal{T}, we have \pi (E^T)=\sum _{e:e\in E^T}{y}_e^{\prime }. Let E^{tight}={\cup }_{E^T:E^T\in \mathcal{T}}{E}^T.

Lemma 3.4.

(7)\begin{array}{r}\pi (E^{tight})=\sum _{e:e\in E^{tight}}{y}_e^{\prime }.\end{array}

Proof Considering any two different tight edge sets E_1^T and E_2^T in \mathcal{T}, we have

\begin{array}{r}\pi (E_1^T)=\sum _{e:e\in E_1^T}{y}_e^{\prime },\text{and}\pi (E_2^T)=\sum _{e:e\in E_2^T}{y}_e^{\prime }.\end{array}

Therefore,

\begin{array}{rl}\sum _{e:e\in E_1^T\cup E_2^T}{y}_e^{\prime }+\sum _{e:e\in E_1^T\cap E_2^T}{y}_e^{\prime }=& \sum _{e:e\in E_1^T}{y}_e^{\prime }+\sum _{e:e\in E_2^T}{y}_e^{\prime }\\ =& \pi (E_1^T)+\pi (E_2^T)\\ \ge & \pi (E_1^T\cup E_2^T)+\pi (E_1^T\cap E_2^T)\\ \ge & \pi (E_1^T\cup E_2^T)+\sum _{e:e\in E_1^T\cap E_2^T}{y}_e^{\prime },\end{array}

where the first inequality follows from the submodularity of \pi (\cdot ) and the second inequality follows from inequality Eq. (6), which implies that

\begin{array}{r}\sum _{e:e\in E_1^T\cup E_2^T}{y}_e^{\prime }\ge \pi (E_1^T\cup E_2^T).\end{array}

Furthermore, this statement and inequality Eq. (6) imply that \sum _{e:e\in E_1^T\cup E_2^T}{y}_e=\pi (E_1^T\cup E_2^T), which means that E_1^T\cup E_2^T is a tight subset. By repeating the merging of the tight subsets in \mathcal{T}, we obtain that E^{tight}={\cup }_{E^T\in \mathcal{T}}{E}^T is a tight subset, and the lemma holds. 　　　　　　　　　　　　　　　　　　　 □

Then, we consider the case in which (S,R) is generated by Phase 2 Consistent with the above definition, let ({\mathit{y}}^{\prime },0) be the value of the dual variables after Phase 1, and let ({\mathit{y}}^{″},\gamma ) be the value of the dual variables after Phase 2.

Lemma 3.5 ({\mathit{y}}^{″},\gamma ) is a feasible solution of dual program Eq. (4).

Proof In Algorithm 1, any dual variable of an edge that is covered by any tight vertex remains unchanged, which means

\begin{array}{r}\sum _{e:e\in \delta (v)}{y}_e^{″}\le c(v),\mathrm{\forall }v\in V.\end{array}

Since \gamma keeps increasing in Phase 2, we have \gamma =\underset{e\in E}{max}(y_e^{″}-y_e^{\prime }) and

\begin{array}{r}{y}_e^{″}-\gamma \le y_e^{\prime },\mathrm{\forall }e\in E.\end{array}

Thus, for any edge set E^{\prime }\subseteq E, we have

\sum _{e:e\in E^{\prime }}{y}_e^{″}-|E^{\prime }|\gamma =\sum _{e:e\in E^{\prime }}(y_e^{″}-\gamma )\le \sum _{e:e\in E^{\prime }}{y}_e^{\prime }\le \pi (E^{\prime }),

where the last inequality follows from Lemma 3.2. Therefore, the lemma holds. 　　　　　　　　　　　　　　　　　□

Lemma 3.6 If the pair (S,R) is generated by Phase 2, the cost of vertex set S is

\begin{array}{r}c(S)\le 2\sum _{e:e\in E}{y}_e^{″}-2\sum _{e:e\in E\setminus \delta (S\setminus \{v_{\mathrm{l}\mathrm{a}\mathrm{s}\mathrm{t}}\})}{y}_e^{\prime }-2(m-k)\gamma +c(v_{\mathrm{l}\mathrm{a}\mathrm{s}\mathrm{t}}),\end{array}

where v_{\mathrm{l}\mathrm{a}\mathrm{s}\mathrm{t}} is the last vertex added to the tight vertex set in Phase 2.

Proof Since v_{\mathrm{l}\mathrm{a}\mathrm{s}\mathrm{t}} is the last vertex added to the tight vertex set in Phase 2,

(8)

Any edge e\in E\setminus \delta (S\setminus \{v_{\mathrm{l}\mathrm{a}\mathrm{s}\mathrm{t}}\})) is not covered by any tight vertex before the last iteration of Phase 2, and dual variables \{y_e{\}}_{e\in E\setminus \delta (S\setminus \{v_{\mathrm{l}\mathrm{a}\mathrm{s}\mathrm{t}}\})} and \gamma both increase simultaneously until vertex v_{\mathrm{l}\mathrm{a}\mathrm{s}\mathrm{t}} becomes tight. Thus, we have

y_e^{″}=y_e^{\prime }+\gamma ,\mathrm{\forall }e\in E\setminus \delta (S\setminus \{v_{\mathrm{l}\mathrm{a}\mathrm{s}\mathrm{t}}\}).

Since any vertex v\in S is tight, we have

\begin{array}{r}c(v)=\sum _{e:e\in \delta (\{v\})}{y}_e^{″},\mathrm{\forall }v\in S.\end{array}

Thus, the cost of vertex set S is

\begin{array}{rl}c(S)=& \sum _{v:v\in S}c(v)=\sum _{v:v\in S\setminus \{v_{\mathrm{l}\mathrm{a}\mathrm{s}\mathrm{t}}\}}\sum _{e:e\in \delta (v)}{y}_e^{″}+c(v_{\mathrm{l}\mathrm{a}\mathrm{s}\mathrm{t}})\\ =& \sum _{e:e\in \delta (S\setminus \{v_{\mathrm{l}\mathrm{a}\mathrm{s}\mathrm{t}}\})}{y}_e^{″}|V(e)\cap (S\setminus \{v_{\mathrm{l}\mathrm{a}\mathrm{s}\mathrm{t}}\})|+c(v_{\mathrm{l}\mathrm{a}\mathrm{s}\mathrm{t}})\\ \le & 2\sum _{e:e\in \delta (S\setminus \{v_{\mathrm{l}\mathrm{a}\mathrm{s}\mathrm{t}}\})}{y}_e^{″}+c(v_{\mathrm{l}\mathrm{a}\mathrm{s}\mathrm{t}})\\ =& 2\sum _{e:e\in E}{y}_e^{″}-2\sum _{e:e\in E\setminus \delta (S\setminus \{v_{\mathrm{l}\mathrm{a}\mathrm{s}\mathrm{t}}\})}{y}_e^{″}+c(v_{\mathrm{l}\mathrm{a}\mathrm{s}\mathrm{t}})\\ =& 2\sum _{e:e\in E}{y}_e^{″}-2\sum _{e:e\in E\setminus \delta (S\setminus \{v_{\mathrm{l}\mathrm{a}\mathrm{s}\mathrm{t}}\})}(y_e^{\prime }+\gamma )+c(v_{\mathrm{l}\mathrm{a}\mathrm{s}\mathrm{t}})\\ =& 2\sum _{e:e\in E}{y}_e^{″}-2\sum _{e:e\in E\setminus \delta (S\setminus \{v_{\mathrm{l}\mathrm{a}\mathrm{s}\mathrm{t}}\})}{y}_e^{\prime }\\ & -2|E\setminus \delta (S\setminus \{v_{\mathrm{l}\mathrm{a}\mathrm{s}\mathrm{t}}\})|\gamma +c(v_{\mathrm{l}\mathrm{a}\mathrm{s}\mathrm{t}})\\ \le & 2\sum _{e:e\in E}{y}_e^{″}-2\sum _{e:e\in E\setminus \delta (S\setminus \{v_{\mathrm{l}\mathrm{a}\mathrm{s}\mathrm{t}}\})}{y}_e^{\prime }-2(m-k)\gamma +c(v_{\mathrm{l}\mathrm{a}\mathrm{s}\mathrm{t}}),\end{array}

where the first inequality follows from the fact that any edge is incident to two vertices, and the second inequality follows from |E|=m, inequality Eq. (8) and \gamma \ge 0.　　　　　□

Theorem 3.7 If \pi (\cdot ) is a normalized and nondecreasing function, Algorithm 1 can output a feasible solution (S,R) of instance \mathcal{I} satisfying

c(S)+\pi (R)\le 3OPT+c(v_{\mathrm{l}\mathrm{a}\mathrm{s}\mathrm{t}}),

where OPT is the optimal value of instance \mathcal{I}.

Proof By Lemma 3.2 and Lemma 3.5, we have

(9)\begin{array}{rl}& \sum _{e\in E}{y}_e^{\prime }\le OP{T}_{DP}\le OPT\\ \mathrm{a}\mathrm{n}\mathrm{d}& \sum _{e\in E}{y}_e^{″}-(m-k)\gamma \le OP{T}_{DP}\le OPT,\end{array}

where OP{T}_{DP} is the optimal value of dual program Eq. (4) and OP{T}_{DP}\le OPT follows from the famous duality theorem.

Regardless of whether (S,R) is generated by Phase 1 or Phase 2, we have R\subseteq E^{tight}. By the nondecreasing function \pi (\cdot ) and Lemma 3.4, we have

\pi (R)\le \pi (E^{tight})=\sum _{e:e\in E^{tight}}{y}_e^{\prime }.

If (S,R) is generated by Phase 1, the objective value of (S,R) is

c(S)+\pi (R)\le 2\sum _{e:e\in \delta (S)}{y}_e^{\prime }+\sum _{e:e\in E^{tight}}{y}_e^{\prime }\le 3\sum _{e\in E}{y}_e^{\prime }\le 3OPT,

where the first inequality follows from Lemma 3.3, the second inequality follows from \delta (S)\subseteq E and E^{tight}\subseteq E, and the last inequality follows from inequality Eq. (9).

If (S,R) is generated by Phase 2, the objective value of (S,R) is

\begin{array}{rl}& c(S)+\pi (R)\\ \le & 2\sum _{e:e\in E}{y}_e^{″}-2\sum _{e:e\in E\setminus \delta (S\setminus \{v_{\mathrm{l}\mathrm{a}\mathrm{s}\mathrm{t}}\})}{y}_e^{\prime }\\ & -2(m-k)\gamma +c(v_{\mathrm{l}\mathrm{a}\mathrm{s}\mathrm{t}})+\sum _{e:e\in E^{tight}}{y}_e^{\prime }\\ \le & 2(\sum _{e\in E}{y}_e^{″}-(m-k)\gamma )+\sum _{e\in E}{y}_e^{\prime }+c(v_{\mathrm{l}\mathrm{a}\mathrm{s}\mathrm{t}})\\ \le & 3OPT+c(v_{\mathrm{l}\mathrm{a}\mathrm{s}\mathrm{t}}),\end{array}

where the first inequality follows from Lemma 3.6, the second inequality follows from E^{tight}\subseteq E and y_e^{\prime }\ge 0 for any e\in E, and the last inequality follows from inequality Eq. (9).

Therefore, the theorem holds. 　　　　　　　　　　　　 □

In particular, if \pi (\cdot ) is a linear function, i.e., \pi (E^{\prime })=\sum _{e:e\in E^{\prime }}\pi (\{e\}) for any E^{\prime }\subseteq E, we have the following theorem.

Theorem 3.8 If \pi (\cdot ) is a linear function, Algorithm 1 can output a feasible solution (S,R) of instance \mathcal{I} satisfying

c(S)+\pi (R)\le 2OPT+c(v_{\mathrm{l}\mathrm{a}\mathrm{s}\mathrm{t}}),

where OPT is the optimal value of instance \mathcal{I}.

Proof Since R\subseteq E^{tight}, any edge e\in R is tight and

\pi (R)=\sum _{e:e\in R}\pi (\{e\})=\sum _{e:e\in R}{y}_e^{\prime }.

If (S,R) is generated by Phase 1, the objective value of (S,R) is

c(S)+\pi (R)\le 2\sum _{e:e\in \delta (S)}{y}_e^{\prime }+\sum _{e:e\in R}{y}_e^{\prime }\le 2\sum _{e\in E}{y}_e^{\prime }\le 2OPT,

where the first inequality follows from Lemma 3.3, the second inequality follows from R=E\setminus \delta (S), and the last inequality follows from inequality (9).

If (S,R) is generated by Phase 2, the objective value of (S,R) is

\begin{array}{rl}& c(S)+\pi (R)\\ \le & 2\sum _{e:e\in E}{y}_e^{″}-2\sum _{e:e\in E\setminus \delta (S\setminus \{v_{\mathrm{l}\mathrm{a}\mathrm{s}\mathrm{t}}\})}{y}_e^{\prime }\\ & -2(m-k)\gamma +c(v_{\mathrm{l}\mathrm{a}\mathrm{s}\mathrm{t}})+\sum _{e:e\in R}{y}_e^{\prime }\\ \le & 2\left(\sum _{e\in E}{y}_e^{″}-(m-k)\gamma \right)+c(v_{\mathrm{l}\mathrm{a}\mathrm{s}\mathrm{t}})\\ \le & 2OPT+c(v_{\mathrm{l}\mathrm{a}\mathrm{s}\mathrm{t}}),\end{array}

where the first inequality follows from Lemma 3.6, the second inequality follows from R=E\setminus \delta (S)\subseteq E\setminus \delta (S\setminus \{v_{\mathrm{l}\mathrm{a}\mathrm{s}\mathrm{t}}\}), and the last inequality follows from inequality Eq. (9). Therefore, the theorem holds.　　　　　　　　　　　　　　　　　　　□

3.2 A combinatorial algorithm of the k-PCVCS

In fact, we cannot know the maximum cost vertex v_{\mathrm{m}\mathrm{a}\mathrm{x}}^{\ast } in advance; however, we can guess this vertex by enumerating all the vertices in V. Thus, for each v\in V, the combinatorial algorithm constructs the auxiliary instance \mathcal{I}\setminus \{v\} defined in Section 2, and we find a feasible solution (S_v,R_v) of instance \mathcal{I}\setminus \{v\} using Algorithm 1. Let

v^{\prime }=\arg \underset{v\in V}{min}(c(S_v)+\pi (R_v)+c(v)),

and the combinatorial algorithm outputs (S,R)=(S_{v^{\prime }}\cup \{v^{\prime }\},R_{v^{\prime }}). We propose the detailed algorithm in Algorithm 2.

Full size|PPT slide

Theorem 3.9 If \pi (\cdot ) is a normalized and nondecreasing function, Algorithm 2 is a combinatorial 3-approximation algorithm for the k-PCVCS. Specifically, if \pi (\cdot ) is a linear function, Algorithm 2 is a 2-approximation algorithm.

Proof Let (S^{\ast },R^{\ast }) be the optimal solution for instance \mathcal{I} and OP{T}_{\mathcal{I}} be the objective value of S^{\ast },R^{\ast }. Let v_{\mathrm{m}\mathrm{a}\mathrm{x}}^{\ast }=\arg \underset{v\in S^{\ast }}{max}c(v) and let \mathcal{I}\setminus \{v_{\mathrm{m}\mathrm{a}\mathrm{x}}^{\ast }\} be the auxiliary instance defined in Section 2. Let (S_{v_{\mathrm{m}\mathrm{a}\mathrm{x}}^{\ast }},R_{v_{\mathrm{m}\mathrm{a}\mathrm{x}}^{\ast }}) be the output solution of instance \mathcal{I}\setminus \{v_{\mathrm{m}\mathrm{a}\mathrm{x}}^{\ast }\} using Algorithm 1. By the definition of \mathcal{I}\setminus \{v_{\mathrm{m}\mathrm{a}\mathrm{x}}^{\ast }\}, we have

(10)\begin{array}{r}c(v_{\mathrm{l}\mathrm{a}\mathrm{s}\mathrm{t}})\le c(v_{\mathrm{m}\mathrm{a}\mathrm{x}}^{\ast }),\end{array}

where v_{\mathrm{l}\mathrm{a}\mathrm{s}\mathrm{t}} is the last vertex added to S_{v_{\mathrm{m}\mathrm{a}\mathrm{x}}^{\ast }}.

Since v^{\prime }=\arg \underset{v\in V}{min}(c(S_v)+\pi (S_v)+c(v)), the objective of (S,R) is

\begin{array}{rl}OUT=& c(S_{v^{\prime }}\cup \{v^{\prime }\})+\pi (R_{v^{\prime }})\\ \le & c(S_{v_{\mathrm{m}\mathrm{a}\mathrm{x}}^{\ast }}\cup \{v_{\mathrm{m}\mathrm{a}\mathrm{x}}^{\ast }\})+\pi (R_{v_{\mathrm{m}\mathrm{a}\mathrm{x}}^{\ast }})\\ =& c(S_{v_{\mathrm{m}\mathrm{a}\mathrm{x}}^{\ast }})+\pi (R_{v_{\mathrm{m}\mathrm{a}\mathrm{x}}^{\ast }})+c(v_{\mathrm{m}\mathrm{a}\mathrm{x}}^{\ast })\\ \le & 3OP{T}_{\mathcal{I}\setminus \{v_{\mathrm{m}\mathrm{a}\mathrm{x}}^{\ast }\}}+c(v_{\mathrm{l}\mathrm{a}\mathrm{s}\mathrm{t}})+c(v_{\mathrm{m}\mathrm{a}\mathrm{x}}^{\ast })\\ \le & 3(OP{T}_{\mathcal{I}\setminus \{v_{\mathrm{m}\mathrm{a}\mathrm{x}}^{\ast }\}}+c(v_{\mathrm{m}\mathrm{a}\mathrm{x}}^{\ast }))\\ \le & 3OP{T}_{\mathcal{I}},\end{array}

where the second inequality follows from Theorem 3.7, the third inequality follows from inequality Eq. (10), and the last inequality follows from Lemma 2.1.

If \pi (\cdot ) is a linear function, similar to the proof above, the objective of (S,R) is

\begin{array}{rl}OUT\le & c(S_{v_{\mathrm{m}\mathrm{a}\mathrm{x}}^{\ast }})+\pi (R_{v_{max}^{\ast }})+c(v_{\mathrm{m}\mathrm{a}\mathrm{x}}^{\ast })\\ \le & 2OP{T}_{\mathcal{I}\setminus \{v_{\mathrm{m}\mathrm{a}\mathrm{x}}^{\ast }\}}+c(v_{\mathrm{l}\mathrm{a}\mathrm{s}\mathrm{t}})+c(v_{\mathrm{m}\mathrm{a}\mathrm{x}}^{\ast })\\ \le & 2(OP{T}_{\mathcal{I}\setminus \{v_{\mathrm{m}\mathrm{a}\mathrm{x}}^{\ast }\}}+c(v_{\mathrm{m}\mathrm{a}\mathrm{x}}^{\ast }))\\ \le & 2OP{T}_{\mathcal{I}},\end{array}

where the second inequality follows from Theorem 3.8.

For each v\in V, Algorithm 2 must run Algorithm 1 once. This statement and Lemma 3.1 imply that Algorithm 2 can be implemented in can be computed in O(n^{17}\cdot \rho +n^{18}). 　　　　□

4 Conclusions

In this paper, we consider the k-prize-collecting minimum vertex cover problem with submodular penalties (k-PCVCS), which strictly requires both \delta (S)\cap R=\mathrm{\varnothing } and \delta (S)\cup R=E to be established, where (S,R) is a feasible solution for k-PCVCS, and \delta (S) is the set of edges covered by S. When the submodular penalty cost function is normalized and nondecreasing, we propose a combinatorial 3-approximation algorithm. In many practical situations, we can relax the condition of k-PCVCS as \delta (S)\cap R\ne \mathrm{\varnothing } and \delta (S)\cup R=E. For this relaxed problem, for the submodular penalty cost function that is not normalized and nondecreasing, the proposed algorithm also has an approximation ratio of 3. When the submodular penalty cost function is linear, we prove the approximation factor of the proposed algorithm is reduced to 2, which is the best factor if the unique game conjecture holds.

In the real world, the penalty cost function may not be submodular, and the topic could be further studied in the following ways. The version with general \pi (\cdot ) penalties is worth considering, such as, \pi (\cdot ) is subadditive or supermodular. Recently, there have been many studies on the minimum vertex cover problem with hard capacities [22-24], in which each vertex v is associated with a capacity c_v. The goal of this problem is to select a minimum cost vertex set S such that all edges are covered by S and each vertex v\in S covers at most c_v edges in \delta (v). Thus, the k-PCVCS with hard capacities, which can be viewed as a generalization of the k-PCVCS, deserves to be explored. It is possible to design a combinatorial 3-approximation algorithm, but it is a challenge.

Acknowledgements

The work was supported in part by the National Natural Science Foundation of China (Grant No. 12071417).

References

1 Karp R M. Reducibility among combinatorial problems. In: Miller R E, Thatcher J W, Bohlinger J D, eds. Complexity of Computer Computations. Boston: Springer, 1972, 85–103

2 Vazirani V V. Approximation Algorithms. Berlin, Heidelberg: Springer, 2001

3 Khot S, Regev O . Vertex cover might be hard to approximate to within 2 -ε. Journal of Computer and System Sciences, 2008, 74( 3): 335–349

4 Hochbaum D S . Approximation algorithms for the set covering and vertex cover problems. SIAM Journal on Computing, 1982, 11( 3): 555–556

5 Bar-Yehuda R, Even S . A linear-time approximation algorithm for the weighted vertex cover problem. Journal of Algorithms, 1981, 2( 2): 198–203

6 Bshouty N H, Burroughs L. Massaging a linear programming solution to give a 2-approximation for a generalization of the vertex cover problem. In: Proceedings of the 15th Annual Symposium on Theoretical Aspects of Computer Science. 1998, 298–308

7 Hochbaum D S. The t-vertex cover problem: extending the half integrality framework with budget constraints. In: Proceedings of International Workshop on Approximation Algorithms for Combinatorial Optimization. 1998, 111–122

8 Bar-Yehuda R . Using homogeneous weights for approximating the partial cover problem. Journal of Algorithms, 2001, 39( 2): 137–144

9 Gandhi R, Khuller S, Srinivasan A . Approximation algorithms for partial covering problems. Journal of Algorithms, 2004, 53( 1): 55–84

10 Mestre J . A primal-dual approximation algorithm for partial vertex cover: making educated guesses. Algorithmica, 2009, 55( 1): 227–239

11 Hochbaum D S . Solving integer programs over monotone inequalities in three variables: a framework for half integrality and good approximations. European Journal of Operational Research, 2002, 140( 2): 291–321

12 Bar-Yehuda R, Rawitz D . On the equivalence between the primal-dual schema and the local ratio technique. SIAM Journal on Discrete Mathematics, 2005, 19( 3): 762–797

13 Li Y, Du D, Xiu N, Xu D . Improved approximation algorithms for the facility location problems with linear/submodular penalties. Algorithmica, 2015, 73( 2): 460–482

14 Du D, Lu R, Xu D. A primal-dual approximation algorithm for the facility location problem with submodular penalties. Algorithmica, 2012, 63(1–2): 1–2

15 Liu X, Li W . Approximation algorithms for the multiprocessor scheduling with submodular penalties. Optimization Letters, 2021, 15( 6): 2165–2180

16 Liu X, Li W, Xie R. A primal-dual approximation algorithm for the k-prize-collecting minimum power cover problem. Optimization Letters, 2021,

17 Iwata S, Nagano K. Submodular function minimization under covering constraints. In: Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science. 2009, 671–680

18 Xu D, Wang F, Du D, Wu C . Approximation algorithms for submodular vertex cover problems with linear/submodular penalties using primal-dual technique. Theoretical Computer Science, 2016, 630: 117–125

19 Kamiyama N . A note on the submodular vertex cover problem with submodular penalties. Theoretical Computer Science, 2017, 659: 95–97

20 Guo J S, Liu W, Hou B. An approximation algorithm for p-prize-collecting set cover problem. Journal of the Operations Research Society of China, 2021,

21 Fleischer L, Iwata S . A push-relabel framework for submodular function minimization and applications to parametric optimization. Discrete Applied Mathematics, 2003, 131( 2): 311–322

22 Kao M J, Shiau J Y, Lin C C, Lee D T . Tight approximation for partial vertex cover with hard capacities. Theoretical Computer Science, 2019, 778: 61–72

23 Cheung W C, Goemans M X, Wong S C W. Improved algorithms for vertex cover with hard capacities on multigraphs and hypergraphs. In: Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms. 2014, 1714–1726

24 Wong S C W. Tight algorithms for vertex cover with hard capacities on multigraphs and hypergraphs. In: Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms. 2017, 2626–2637