Approximation Algorithms for the Submodular Hitting Set Problem

1. Introduction

The hitting set problem involves a supergraph $H=(V,\mathcal{C})$, where $V$ is a finite set with elements called vertices and $\mathcal{C}$ is a family of subsets of $V$ called hyperedges. Let $k$ be the maximum size of all hyperedges and $\mathrm{\Delta }$ be the maximum degree of all vertices. A hitting set of $H$, also called a vertex cover of $H$, is a subset $X\subseteq V$ such that each hyperedge in $\mathcal{C}$ contains at least one vertex from $X$. The hitting set problem is to select a vertex subset of minimum size. For each vertex $u\in V$, if there is an associated nonnegative weight cost $w(u)$, we obtain the weighted version of the problem, the goal of which is to select a vertex subset of minimum covering cost. The minimum hitting set problem is NP-hard [] and it is one of the fundamental combinatorial optimization problems. In this case, it is conventional that for any subset $X$ of $V$ the covering cost of $X$ is the sum of the covering cost of all vertices in $X$, that is, $w(X)=\sum _{u\in X}w(u)$. Then this function $w(\cdot )$ induces a linear function from $2^V$ to $R_{+}$.

Most results of decision problems in combinatorial optimization, such as trees or cuts, vertex cover in graphs, facility location, set cover, are in general asking for the linear costs. However, nonlinear costs are more realistic in many settings and there have existed some works in the area of combinatorial optimization problems with submodular costs. Assume $E$ is a nonempty set and $2^E$ is the power set of $E$. Let $F(\cdot ):2^E\to R_{+}$ be a nonnegative-valued set function. We call $F(\cdot )$ submodular if for any $X,Y\in 2^E,F(X\cup Y)+F(X\cap Y)\le F(X)+F(Y)$ and $F(\cdot )$ modular if the equality holds. It is obvious that all modular functions are submodular and so all linear functions. We call $F(\cdot )$ monotone if $F(X)\le F(Y)$ for each pair of subsets $X,Y\in 2^E$ with $X\subseteq Y$. Submodular functions occur very often in a variety of subjects such as economics, engineering, computer science and management science. There is a greedy approximation which achieves an approximation ratio of $H(\mathrm{\Delta })$ for the hitting set problem with linear costs, where $H(\mathrm{\Delta })$ is the $\mathrm{\Delta }$-th harmonic number [1]. Moreover, using the greedy approximation, Wan et al. [2] gave some similar results for the hitting set problem with submodular costs.

One of the most fundamental problems related to submodular functions is the submodular function minimization problem. In this problem, we are given a finite set $E$ and a submodular function $F(\cdot )$ defined on $2^E$, then the goal is to select a subset $X$ of $E$ minimizing $F(X)$ among the power set of $E$, i.e., to select a minimizer of submodular function $F(\cdot )$ over $2^E$. It is known that this problem can be solved in polynomial time. Recently, constrained variants of the submodular function minimization problem have been extensively studied in various fields ([3-6]). For instance, Hochbaum [4] studied the submodular minimization problem with linear constraints having at most two variables per inequality. Kamiyama [5] studied the the submodular function minimization problem with covering type linear constraints. Koufogiannakis and Young [3] studied the monotone submodular function submodular minimization problem with general covering constrains. Iwata and Nagano [6] studied the submodular function minimization problem with set cover constraints. In this paper, we are motivated to study the submodular hitting set problem (SHSP). That is, given a nonnegative submodular function $f(\cdot ):2^V\to R_{+}$, the goal of the SHSP is to select a vertex subset $X\subseteq V$ to cover all the hyperedges that minimizes the submodular cost $f(X)$. We present a rounding algorithm and a primal-dual program for the SHSP and prove that they both have the approximation ratio $k$.

The paper is organized as follows. In Section 2, we give some definitions about submodular function. In Section 3, we present a rounding algorithm and a primal-dual program respectively for the SHSP and prove that they both have the approximation ratio $k$, where $k$ is the maximum number of vertices in all hyperedges.

2. Lovász Extension of a Submodular Function

In this section, we introduce the $Lov\acute{a}sz$ extension of a submodular function. Let $F(\cdot ):2^E\to R_{+}$ be a submodular function.

Assume $|E|=n$. Then for any vector $zz\in R^n$ and any non-empty subset $X\subseteq E$, we define $$zz(X)=\sum _{i\in X}zz(i),$$ where $zz(i)$ is the $i$-th coordinate value of vector $zz$. It is easy to see that $zz(\cdot )$ is a modular function from $2^E\to R.$

For any $X\subseteq E$, define $\chi {\chi }_X\in \{0,1{\}}^n$ as follows: $$\chi {\chi }_X(i)=\{\begin{array}{ll}1,& \text{if }i\in X\text{,}\\ 0,& \text{otherwise,}\end{array}$$ called the characteristic vector of $X$.

Given a submodular function $F(\cdot )$, denote $$P(F)=\{zz\mid zz\in R^n,zz(X)\le F(X),\mathrm{\forall }X\subseteq E\}.$$ We call $P(F)$ a submodular polyhedron and its elements subbases. For any subbase $zz\in P(F)$, a subset $X$ of $E$ is called $zz$-tight whenever $zz(X)=F(X)$. There is a property for the collection of all $zz$-tight subsets.

Now we introduce the $Lov\acute{a}sz$ extension of a submodular function and its properties. Given a vector $pp\in R_{+}^n$ and suppose $p_1,p_2,\cdots ,p_l$ are all distinct coordinate values of $pp$ with $p_1>p_2>\cdots >p_l$. For each $j=1,2,\cdots ,l$, denote $N_j=\{i\mid pp(i)\ge p_j\}$. Then we define a vector function over $R_{+}^n$ as follows: $$\hat{F}(pp)=\sum _{j=1}^l(p_j-p_{j+1})F(N_j),$$ where $p_{l+1}=0$. The function $\hat{F}(\cdot )$ is said to be the $Lov\acute{a}sz$ extension of $F(\cdot )$. It is easy to see that for any subset $X$ of $E$, $\hat{F}(\chi {\chi }_X)=F(X)$ and $\hat{F}(00)=F(\mathrm{\varnothing })$.

It is known from [7] that $$\begin{array}{}\text{(1)}& \hat{F}(pp)=max\{\sum _{i=1}^{n}pp(i)zz(i)\mid zz\in P(F)\}.\end{array}$$ The problem (1) is a linear optimization over the submodular polyhedron, which is efficiently solved by Edmonds [8]. Combining (1) with the primal-dual theory, we get that $\hat{F}(pp)$ is equal to the optimal value of the following program: $$\begin{array}{}\text{(2)}& \begin{array}{r}\mathrm{m}\mathrm{i}\mathrm{n}\sum _{X\subseteq E}F(X)\cdot \zeta (X)\\ \mathrm{s}.\mathrm{t}.\sum _{\begin{array}{c}X\subseteq E\\ i\in X\end{array}}\zeta (X)=pp(i),\mathrm{\forall }i\in E,\\ \zeta (X)\ge 0,\mathrm{\forall }X\subseteq E.\end{array}\end{array}$$

There are some properties of the $Lov\acute{a}sz$ extension function and we list them here for later use.

3. Approximation Algorithms

In this section, we construct a rounding algorithm and a primal-dual algorithm for the SHSP.

For the given supergraph $H=(V,\mathcal{C})$, assume $|V|=n$, $\mathcal{C}=\{T_1,T_2,\dots ,T_m\}$ and $V={\cup }_{i=1}^m\{T_i\}$. Denote $k=max\{|T_i|\mid T_i\in \mathcal{C}\}.$ Assume there is a submodular function $f(\cdot ):2^V\to R_{+}$ with $f(\mathrm{\varnothing })=0$, where $f(X)$ means the covering cost of $X$ for any subset $X$ of $V$.

Firstly we define a binary variable $\zeta (X)$ for any subset $X\subseteq V$ as follows: $$\zeta (X)=\{\begin{array}{ll}1,& \text{if }X\text{ is selected to cover some hyperedges,}\\ 0,& \text{otherwise.}\end{array}$$ Therefore, the integer linear program for the SHSP is

$$\begin{array}{}\text{(3)}& \begin{array}{r}\mathrm{m}\mathrm{i}\mathrm{n}\sum _{X\subseteq V}f(X)\zeta (X)\\ \mathrm{s}.\mathrm{t}.\sum _{\begin{array}{c}X\subseteq V\\ X\cap T_i\ne \mathrm{\varnothing }\end{array}}\zeta (X)\ge 1,\mathrm{\forall }{T}_i\in \mathcal{C},\\ \zeta (X)\in \{0,1\},\mathrm{\forall }X\subseteq V.\end{array}\end{array}$$

In the above program, the first constraint ensures that each hyperedge $T_i\in \mathcal{C}$ is covered by some vertex subset $X$. Since $f(\cdot )$ is a submodular function, there must exist a unique subset $X$ of $V$ such that $\zeta (X)=1$ in the optimal solution of (3).

Recall that $\hat{f}(\chi {\chi }_X)=f(X)$, the convex programming for the SHSP is: $$\begin{array}{}\text{(4)}& \begin{array}{r}\mathrm{m}\mathrm{i}\mathrm{n}\hat{f}(xx)\\ \mathrm{s}.\mathrm{t}.\sum _{u\in T_i}xx(u)\ge 1,\mathrm{\forall }{T}_i\in \mathcal{C},\\ xx(u)\in \{0,1\},\mathrm{\forall }u\in V.\end{array}\end{array}$$ The relaxation of (4) is: $$\begin{array}{}\text{(5)}& \begin{array}{r}\mathrm{m}\mathrm{i}\mathrm{n}\hat{f}(xx)\\ \mathrm{s}.\mathrm{t}.\sum _{u\in T_i}xx(u)\ge 1,\mathrm{\forall }{T}_i\in \mathcal{C},\\ xx(u)\ge 0,\mathrm{\forall }u\in V.\end{array}\end{array}$$

3.1. A Rounding Algorithm for the SHSP

For a submodular function $f(\cdot )$, we define a set function $f^{\circ }(\cdot ):2^V\to R_{+}$ as $$f^{\circ }(X)=min\{f(Z)\mid X\subseteq Z\subseteq V\},\mathrm{\forall }X\subseteq V.$$ Then $f^{\circ }(\cdot )$ is monotone and submodular [10]. Moreover, this function $\widehat{f^{\circ }}(\cdot )$ has the following properties.

Since the program (5) can be solved in polynomial time via the ellipsoid method, we denote $x^{\ast }{x}^{\ast }\in R_{+}^n$ an optimal solution of (5). Based on the program (5), we give the following rounding algorithm.

Recall that $k=max\{|T_i|\mid T_i\in \mathcal{C}\}.$ For every hyperedge $T_i\in \mathcal{C}$, since $\sum _{u\in T_i}xx(u)\ge 1$, at least one of $x{x}^{\ast }(u)$ must be greater than $\frac{1}{k},$ which ensures $A$ is a hitting set. Since $A\subseteq A^{\circ }$, $A^{\circ }$ is also a hitting set. Moreover, the hitting set $A^{\circ }$ can be obtained in polynomial time by submodular function minimization theory. Therefore, Algorithm 1 can be implemented in polynomial time and the obtained $A^{\circ }$ is a hitting set. Finally, we analyze the approximation ratio of Algorithm 1.

3.2. A Primal-dual Algorithm

In this subsection, we give a primal-dual algorithm for the SHSP. For any subset $X\subseteq V$, we denote ${\mathcal{S}}_X=\{T_i\in \mathcal{C}\mid T_i\cap X\ne \mathrm{\varnothing }\}$ and we call $X$ is a hitting set if ${\mathcal{S}}_X=\mathcal{C}.$

Recall that for any given vector $pp\in R_{+}^n$, $\hat{f}(pp)$ is equal to the optimal value of (2). Combining (2) with (5), we consider the following relaxation program for the SHSP : $$\begin{array}{}\text{(8)}& \begin{array}{r}\mathrm{m}\mathrm{i}\mathrm{n}\sum _{X\subseteq V}f(X)\cdot \zeta (X)\\ \mathrm{s}.\mathrm{t}.\sum _{u\in T_i}xx(u)\ge 1,\mathrm{\forall }{T}_i\in \mathcal{C},\\ \sum _{\begin{array}{c}X\subseteq V\\ u\in X\end{array}}\zeta (X)=xx(u),\mathrm{\forall }u\in V,\\ \zeta (X)\ge 0,\mathrm{\forall }X\subseteq V.\end{array}\end{array}$$ We do not need to add the constraint that $xx(u)\ge 0$ for the second constraint of (8) ensures it for all $u\in V$. And the dual program for (8) is: $$\begin{array}{}\text{(9)}& \begin{array}{r}\mathrm{m}\mathrm{a}\mathrm{x}\sum _{T_i\in \mathcal{C}}y(T_i)\\ \mathrm{s}.\mathrm{t}.\sum _{\begin{array}{c}{T}_i\in \mathcal{C}\\ u\in T_i\end{array}}y(T_i)=zz(u),\mathrm{\forall }u\in V,\\ zz\in P(f),\\ y(T_i)\ge 0,\mathrm{\forall }{T}_i\in \mathcal{C}.\end{array}\end{array}$$ Before proposing the primal-dual algorithm for the SHSP, we give some necessary facts.

Given a subbase $zz\in P(f).$ Let $(f-zz)(\cdot ):2^V\to R_{+}$ be defined by $$(f-zz)(X)=f(X)-zz(X),\mathrm{\forall }X\subseteq V.$$ Then $(f-zz)(\cdot )$ is a submodular function. Observe that the definition of $(f-zz)(\cdot )$ is related to the modularity of $zz(\cdot )$. So we get the function $(f-zz)(\cdot )$ for any subbase $zz\in P(f)$ and there is a proposition for the function.

Based on the dual program (9), we give the following primal-dual algorithm.

To obtain the ratio of Algorithm 2, we first prove the following lemmas.

Algorithm outputs $\{(y_1,z{z}_1),(y_2,z{z}_2),\cdots ,(y_T,z{z}_T)\}$. Next we will prove it is a feasible region of the dual program (9).

We now analyze the approximation ratio of Algorithm 2.

Acknowledgment

The authors would like to thank Professor Ding-Zhu Du for his many valuable advices during their study of approximation algorithm.

This work is supported by the NSF of China (No. 11971146), the NSF of Hebei Province (No. A2019205089, No. A2019205092), Hebei Province Foundation for Returnees (CL201714) and Overseas Expertise Introduction Program of Hebei Auspices (25305008).