An approximation algorithm for the partial vertex cover problem in hypergraphs

Abstract

Let $\mathcal {H}=(V,\mathcal {E})$ be a hypergraph with set of vertices $V, n:=|V|$ and set of (hyper-)edges $\mathcal {E}, m:=|\mathcal {E}|$. Let $l$ be the maximum size of an edge, $\varDelta$ be the maximum vertex degree and $D$ be the maximum edge degree. The $k$-partial vertex cover problem in hypergraphs is the problem of finding a minimum cardinality subset of vertices in which at least $k$ hyperedges are incident. For the case of $k=m$ and constant $l$ it known that an approximation ratio better than $l$ cannot be achieved in polynomial time under the unique games conjecture (UGC) (Khot and Ragev J Comput Syst Sci, 74(3):335–349, 2008), but an $l$-approximation ratio can be proved for arbitrary $k$ (Gandhi et al. J Algorithms, 53(1):55–84, 2004). The open problem in this context has been to give an $\alpha l$-ratio approximation with $\alpha < 1$, as small as possible, for interesting classes of hypergraphs. In this paper we present a randomized polynomial-time approximation algorithm which not only achieves this goal, but whose analysis exhibits approximation phenomena for hypergraphs with $l\ge 3$ not visible in graphs: if $\varDelta$ and $l$ are constant, and $2\le l\le 4\varDelta$, we prove for $l$-uniform hypergraphs a ratio of $l\left( 1-\frac{l-1}{4\varDelta }\right)$, which tends to the optimal ratio 1 as $l\ge 3$ tends to $4\varDelta$. For the larger class of hypergraphs where $l, l \ge 3$, is not constant, but $D$ is a constant, we show a ratio of $l(1-1/6D)$. Finally for hypergraphs with non-constant $l$, but constant $\varDelta$, we get a ratio of $l (1- \frac{2 - \sqrt{3}}{6\varDelta })$ for $k\ge m/4$, leaving open the problem of finding such an approximation for $k < m/4$.

1 Introduction

A hypergraph $\mathcal {H}=(V,\mathcal {E})$ consists of a set $V$, say $|V| = n$, and a set $\mathcal {E}$ of subsets of $V$, $|\mathcal {E}|=m$. We call the elements of $V$ vertices and the elements of $\mathcal {E}$ (hyper-)edges. The $k$-partial vertex cover in hypergraphs can be stated as follows. A set $X\subseteq V$ is called a $k$-partial vertex cover for $\mathcal{H}$ if at least $k$ edges of $\mathcal{H}$ are incident in $X$. The (unweighted) $k$-partial vertex cover problem for hypergraphs is to find a $k$-vertex cover of minimum cardinality. If $k$ is equal to the number of hyperedges, we have the well-known hitting set problem in hypergraphs. For graphs it is the vertex cover problem, whose approximation complexity has been studied for nearly 4 decades.

Among the motivations to study hypergraphs are not only the natural question of generalizing graph theory to hypergraphs (Berge 1989), but also relevant applications in areas where hypergraphs are most natural, e.g. data structures in computational geometry like $\epsilon$-nets (Matousek and Wagner 2004), which are a kind of hitting sets, or discrepancy theory (Matousek 2010).

1.1 Previous work

Consider a mimimization problem. For $\rho \ge 1$ we say that a polynomial-time algorithm achieves an $\rho$-approximation or an approximation ratio of $\rho$, if it computes for all instances a solution of value at most $\rho \cdot \mathrm {Opt}$, where $\mathrm {Opt}$ is the value of an optimal solution to the problem.

For the $k$-partial vertex cover problem in graphs it has been an open question for which graphs the well-known $2$-approximation can be improved. For graphs with maximum vertex degree at most a constant $\varDelta$, Gandhi et al. (2004) gave the first algorithm with approximation ratio smaller than 2. Further improvements have been obtained by Halperin and Srinivasan (2002).

For hypergraphs the hitting set and the set cover problem have been investgated intensively in the context of polynomial-time approximations (Chvátal 1979; Hochbaum 1982; Lovász 1975; Duh and Fürer 1997; Halperin 2000; Krivelevich 1997) as well as non-approximability (Alon et al. 2006; Feige 1998; Lund and Yannakakis 1994; Raz and Safra 1997).

For the hitting set problem in $l$-uniform hypergraphs with constant $l$ an approximation with a ratio strictly smaller than $l$ cannot be achieved in polynomial time under the unique games conjecture (UGC) (Khot and Regev 2008). Since the hitting set problem in hypergraphs is a special case of the $k$-vertex cover problem in hypergraphs, namely with $k = m$, this hardness of approximation holds also for the $k$-vertex cover problem in hypergraphs. On the other hand, for the $k$-partial vertex cover problem in hypergraphs with edge size at most $l$ ($l$ not necessarily constant) Gandhi et al. (2004) gave a polynomial time $l$-approximation based on the primal/dual approach.

Thus polynomial-time approximations below the $l$-ratio for significant classes of hypergraphs are complexity-theoretic and algorithmically interesting and would extend the approximation theory for the $k$-partial vertex cover problem from graphs to hypergraphs. Our work is a contribution to this specific task, and to an approximation theory for problems in hypergraphs.

1.2 Our contribution

We give a randomized algorithm of hybrid type, combining linear programming (LP) based randomized rounding and afterwards greedy repairing to ensure the feasibility of the randomized solution. While the algorithm is a straightforward generalization of the algorithm of Gandhi et al. (2004) from graphs to hypergraphs, the main challenge is its analysis in different hypergraph settings. In general, the analysis of hybrid randomized algorithms is a difficult task, as the probabilistic analysis has to combine different dependent subroutines (e.g. maximum graph bisection Frieze and Jerrum (1997), maximum graph partitioning Feige and Langberg (2001); Jäger and Srivastav (2005) and vertex cover and partial vertex cover problem for graphsGandhi et al. (2004); Halperin (2000)). Similar problems appear also in our proofs.

We show the following approximation results: If both $\varDelta$ and $l$ are constant, $2\le l\le 4\varDelta$, we prove for a $l$-uniform hypergraph with maximum vertex degree $\varDelta$ an approximation ratio of $l\left( 1-\frac{l-1}{4\varDelta }\right)$. This ratio tends to the optimal ratio 1 as $l$ is at least 3 and tends to $4\varDelta$. Thus for hypergraphs with large $l$ the approximability is much better than for graphs, matching our intuition that large hyperedges may cause many intersections and thus a few vertices might be sufficient to get a $k$-partial vertex cover. The analysis is based on variance computation and the Chebyshev–Cantelli bound. For the larger class of hypergraphs, where $l, l \ge 3$, is not constant, the above mentioned approach does not work. Among this class we consider hypergraphs with a constant maximum edge degree $D$ and show an approximation ratio of $l(1-1/6D)$. Here again variance computation and the Chebyshev–Cantelli bound are invoked, but more work is needed to minimize the probability of an infeasible $k$-partial vertex cover. Finally for hypergraphs with non-constant $l, l \ge 3$, but constant $\varDelta$, a similar analysis as above can be carried out, but with the severe restriction $l \le 2$, which does not reveal any new insight. Interestingly, we can overcome this restriction with the bounded difference inequality (based on the Azuma–Hoeffding bound) and prove for any $l, l \ge 3$ and $k\ge m/4$ a ratio of $l (1- \frac{2 - \sqrt{3}}{\varDelta })$.

An open problem for hypergraphs arising from our work is the question whether for a hypergraph with maximum vertex degree $\varDelta$, $\varDelta$ a constant, but arbitrary edge size $l$, an approximation ratio of $l (1- \frac{c}{\varDelta })$, $c > 0$ a constant, can be shown for any $k$, in particular for $k< m/4$.

Note that the approach to lift the analysis in Gandhi et al. (2004) from the $k$-vertex cover problem in graphs to hypergraphs fails. Among the reasons are the different hypergraphs settings with different hypergraph parameters (e.g. $l$, $D$ and $\varDelta$) requiring a situation adapted application of different concentration results in combination with combinatorial arguments.

1.3 Outline of the paper

The paper is organised as follows: In Sect. 2 we give the necessary definitions and state some probabilistic tools. In Sect. 3 we present the randomized algorithm for the $k$-partial vertex cover for hypergraphs and state estimations for the expectation and the variance of the random variables under consideration. In Sect. 4 we analyse the algorithm for $l$-uniform hypergraphs where $l$ and $\varDelta$ are constants. In Sect. 5 resp. 6 we analyse the approximation ratio for hypergraphs with constant $D$ resp. $\varDelta$.

2 Preliminaries and definitions

2.1 Graph-theoretical notions

For a natural number $n$ let $[n]$ denote the set $\{1, \ldots , n\}$. Let $\mathcal{H}=(V,\mathcal{E})$ be a (finite) hypergraph, where $V$ is a finite set, called the set of vertices, and $\mathcal{E}$ is the set of hyperedges (or simply edges) consisting of subsets of $V$. For $v \in V$ we define the degree of a vertex $v$ by $d(v) := |\{E \in \mathcal{E}; v \in E \}|$ and the maximum vertex degree by $\varDelta :=\max \{ d(v);\, v\in V \}$. For a set $X\subseteq V$ we denote by $\mathcal {E}/X :=\{F\in \mathcal {E}\,;\, X\cap F\ne \emptyset \}$ the set of edges incident to $X$. For an edge $E \in \mathcal{E}$ let $\text {deg}(E) := |\mathcal {E}/E|$ be the (edge-)degree of $E$ and $D :=\max _{E \in \mathcal{E}}\, \text {deg}(E)$ is the maximum edge degree. Note that $\varDelta \le D \le l \varDelta$. For $l \in \mathbb {N}$ we call the hypergraph $\mathcal{H}$ $l$-uniform resp. $l$-bounded, if $|E|=l$ resp. $|E|\le l$ for all $E\in \mathcal{E}$. In this notion $l$ is not assumed to be a constant. If $l$ is assumed to be constant, we will make it explicitly clear. Otherwise, we will say that $l$ is non-constant. It is convenient to order the vertices and hyperedges, $V=\{v_1,\ldots ,v_n\}$ and $\mathcal{E}=\{ E_1,\ldots ,E_m\},$ and to identify vertices and edges with their indices. This is an useful abbreviation of the notation especially when we model the optimization problem under consideration as an integer linear program and look at its linear programming relaxation.

2.2 Concentration inequalities

We will frequently use the Chebychev–Cantelli inequality:

Theorem 1

(see Motwani and Raghavan (1995), p 64) Let $X$ be a non-negative random variable with finite mean $\mathbb {E}(X)$ and variance Var$(X)$. Then for any $a>0$ we have

$$\begin{aligned} \Pr (X\ge \mathbb {E}(X)+a)&\le \frac{\mathrm{Var} (X)}{\mathrm{Var}(X)+a^2}\end{aligned}$$

(1)

$$\begin{aligned} \Pr (X\le \mathbb {E}(X)-a)&\le \frac{\mathrm{Var} (X)}{\mathrm{Var}(X)+a^2}\cdot \end{aligned}$$

(2)

A further useful concentration result used in this paper is the bounded differences inequality:

Theorem 2

(see McDiarmid (1989), p 216) Let $X= (X_{1},X_{2},\ldots ,X_{n})$ be a family of independent random variables with $X_{k}$ taking values in a set $A_{k}$ for each $k$. Suppose that the real-valued function $f$ defined on ${A}_{1}\times A_{2}\cdots \times A_{n}$ satisfies $|f(x)-f(x')|\le c_{k}$ for all pairs of vectors $x$ and $x'$ from ${A}_{1}\times A_{2}\cdots \times A_{n}$ that differ only in the k-$th$ coordinate, $k=1,\ldots ,n$. Then for any $t > 0$ it holds

$$\begin{aligned} \Pr \left[ f(X)\le \mathbb {E}(f(X))-t\right] \le \exp {\left( \frac{-2t^{2}}{\sum _{k=1}^{n} c_{k}^{2}}\right) }. \end{aligned}$$

Let $X$ be the sum of finitely many $0/1$ random variables, i.e. $X=X_1+\cdots +X_n$. For a pair $i,j\in \{1,\ldots ,n\}$ we say that $i$ and $j$ are dependent, if $X_i$ and $X_j$ are not independent. Let $\varGamma$ be the set of all unordered dependent pairs $i,j$, i.e. $2$-element sets $\{i,j\}$, and let $\gamma = \sum _{\{i,j\}\in \varGamma } \mathbb {E}(X_iX_j),$ The following estimate on the variance of such a sum of dependent random variables can be proved as in the book of Alon and Spencer (2000), p 41:

Lemma 1

We have $\mathrm {Var} (X)\le \mathbb {E}(X)+2\gamma$.

For a sum of independent random variables we will use the large deviation inequalities due to Angluin and Valiant (1979):

Theorem 3

(see McDiarmid (1989), p 200) Let $X_1,\ldots , X_n$ be independent 0/1-random variables and $\mathbb {E}(X_i)=p_i$ for all $i=1,\ldots , n$. Let $X= \sum _{i=1}^n X_i$ with $\mu = \mathbb {E}(X)$. For any $\beta >0$ it holds

$$\begin{aligned} \Pr (X\ge (1+\beta )\cdot \mu )\le \exp {\left( -\frac{\beta ^2 \mu }{3}\right) }. \end{aligned}$$

3 The algorithm and estimation of mean and variance

The input is a $l$-bounded hypergraph $\mathcal{H}$, $l \ge 2$. At the moment we do not assume $D$ or $\varDelta$ to be constants. Before we proceed to the randomized algorithm, let us rule out trivial cases of the problem solvable to optimality in polynomial time (not optimizing the time complexity here).

Proposition 1

Let $\mathcal{H}$ be a hypergraph with $n$ vertices and $m$ hyperedges. If $k$ is a constant, then the $k$-partial vertex cover can be solved to optimality in $O(kmn^k)$-time.

Proof

Since an optimal $k$-partial vertex cover has cardinality at most $k$, we can find such a cover by examining all sets of vertices of cardinality $r$, $r\le k$. Their number is $\sum _{r = 1}^k {n \atopwithdelims ()r} \le O(kn^k)$. The test whether or not such a $r$-set is a $k$-partial vertex cover requires the test of at most all the $m$ edges, so the total complexity is at most $O(kmn^k)$. $\square$

As already said, we will identify the vertices and edges of $\mathcal{H}$ by their indices. An integer linear programming formulation of the $k$-partial vertex cover in $\mathcal{H}$ is the following:

$$\begin{aligned}&\min \sum _{j=1}^n x_j\\ (\mathrm{ILP}\!-\!k\!-\!\mathrm{VC})\qquad \qquad \qquad&\sum _{j=1}^n a_{ij}x_j\ge z_i \quad \text{ for } \text{ all } i \in [m]:= \{1,\ldots , m\}\\&\sum _{i=1}^m z_i\ge k\\&x_j, z_i \in \{0,1\}\quad \text{ for } \text{ all } i\in [m], j \in [n]. \end{aligned}$$

Its linear programming (LP) relaxation LP-$k$-VC is given by relaxing the integrality constraints to $x_j, z_i\in [0,1] \; \forall i \in [m], j\in [n]$. Let $\mathrm {Opt}$ resp. $\mathrm {Opt}^{*}$ be the value of an optimal solution to ILP-$k$-VC resp. to LP-$k$-VC. Let $x^{*} \in [0,1]^n$ and $z^{*} \in [0,1]^m$ be an optimal solution of LP-$k$-VC for the variables $x_j, z_i$, $j\in \{0,1\}$ and $i\in \{0,1\}$. Note that an optimal solution of a linear program can be computed in polynomial time, for example with the ellipsoid method of Khachian (1979) or more efficiently with the interior-point method of Karmarkar (1984).

3.1 The Algorithm

The algorithm extends the randomized algorithm of Gandhi, Khuller and Srinivasan Gandhi et al. (2004) from graphs to hypergraphs. While the extension is quite natural, the analysis needs efforts beyond Gandhi et al. (2004) as already mentioned in the introduction.

3.2 Computation of expection and variance

We give some basic estimates. Note that at this moment we have not to comment on the randomized rounding parameter $\epsilon$ as the proofs in this section work for any $\epsilon \in (0,1)$. But the choice of $\epsilon$ will become a crucial point when we apply the algorithm to the different hypergraph families in later sections.

Let $X_{1},\ldots ,X_{n}$ be $\{0,1\}$-random variables defined as follows. For $j \in [n]$ let

$$\begin{aligned} X_j= {\left\{ \begin{array}{ll} 1 &{} \quad \text {if vertex}\, v_j \, \text {was picked by randomized rounding or if } v_j \in S_1 \cup S_{\ge } \\ 0 &{} \quad \text {otherwise}. \end{array}\right. }\nonumber \\ \end{aligned}$$

(3)

Note that the random variables $X_{1},\ldots ,X_{n}$ are independent and

$$\begin{aligned} Y:=\sum _{j=1}^nX_j \end{aligned}$$

(4)

is the cardinality of the set $C$ after randomized rounding. For all $i\in [m]$ we define the $\{0,1\}$- random variables $Z_{i}$ as follows:

$$\begin{aligned} Z_{i}= {\left\{ \begin{array}{ll} 1 &{} \quad \text {if the the hyperedge}\, E_{i} \, \text {is covered after the rounding step}\qquad \quad \\ 0 &{} \quad \text {otherwise}. \end{array}\right. } \end{aligned}$$

(5)

The sum of the $Z_{i}$’s

$$\begin{aligned} W:=\sum _{j=1}^{m}Z_{j} \end{aligned}$$

(6)

is the number of covered hyperedges before entering the repairing step. Note that in this step at most $k- W$ further vertices are added to $C$. Hence, for the expected size of the final cover $C$ returned by the algorithm we have

Proposition 2

$$\begin{aligned} \mathbb {E}(|C|)\le \mathbb {E}(Y)+\mathbb {E}(\max \{k-W,0\}). \end{aligned}$$

(7)

For the computation of the expectation of $W$ we need the following lemma that gives the exact solution of a constrained optimization problem (Lemma 2.2, Peleg et al. (1997)).

Lemma 2

For all $n\in \mathbb {N}$, $\alpha >0$ and $x_1,\ldots ,x_n, z\in [0,1]$ with $\sum _{i=1}^nx_i\ge z$ and $\alpha x_i<1$ for all $i\in \mathbb {N}$, we have $\prod _{i=1}^n(1-\alpha x_i)\le (1-\alpha \frac{z}{n})^n$, and this bound is the tight maximum.

For the expectation and the variance the following lemma will serve as a technical backbone.

Lemma 3

Let $D$ and $\varDelta$ be as above, not assumed to be constants, and let $\epsilon \in (0,1)$.

• (i) $(1-(1-\epsilon )x)^2\le 1-x(1-\epsilon ^2)$ for all $x\in [0,1]$.

• (ii) $\mathbb {E}(W)\ge (1-\epsilon ^{2})k$.

• (iii) (1)   $\mathrm{Var}(W)\le (D+1)\mathbb {E}(W)$,    (2)   $\mathrm{Var}(|C|)\le l\varDelta \mathbb {E}(|C|)$.

• (iv) $\mathrm {Opt}^{*}\ge \frac{k}{\varDelta }\ge \frac{k}{D}$.

• (v) For $\lambda \ge 1$, $\mathrm {Opt}^{*}\le \mathbb {E}(Y)\le \lambda \mathrm {Opt}^{*}$.

• (vi) $\sum _{v\in V}d(v)^{2}\le \varDelta lm$.

Proof

(i) Straightforward calculations show that assertion (i) is equivalent to

$$\begin{aligned} x(1+\epsilon ^2-2\epsilon )\le 1+\epsilon ^2-2\epsilon . \end{aligned}$$

But this is true for any $x\in [0,1]$.

(ii) Let $i\in [m]$ and $|E_{i}|=r_{i}$. If there is a $j\in E_{i}$ with $\lambda x^*_{j}\ge 1$, then $j \in S_{1}\cup S_{\ge }$. Thus $j$ belongs to the cover $C$, $Z_i = 1$, and trivially $\Pr (Z_{i}=0)=0$. Otherwise, if $\lambda x^*_{j} < 1$ for all $j \in E_{i}$, we have

$$\begin{aligned} P(Z_i=0)&=\prod _{j\in E_i }(1-\lambda x_j^{*}) \underset{\text {Lem2}}{\le }\left( 1-\frac{\lambda z_i^{*}}{r_{i}}\right) ^{r_{i}}\\&\le \left( 1-\frac{\lambda z_i^{*}}{l}\right) ^{r_{i}} =(1-(1-\epsilon ) z^*_i )^{r_{i}}\\&\le (1-(1-\epsilon ) z_i^{*} )^2 \underset{\text {Lem3}(i)}{\le } 1- z_i^{*}(1-\epsilon ^2), \end{aligned}$$

so $P(Z_i=0) \le 1- z_i^{*}(1-\epsilon ^2)$, and we get

$$\begin{aligned} \mathbb {E}(W)&=\sum _{i=1}^m\Pr (Z_i=1)= \sum _{i=1}^m(1-\Pr (Z_i=0))\\&\ge \sum _{i=1}^m(1-(1- z_i^{*}(1-\epsilon ^2))=\sum _{i=1}^m z_i^{*}(1-\epsilon ^2)= (1-\epsilon ^2)\underbrace{\sum _{i=1}^m z_i^{*}}_{\ge k}\\&\ge (1-\epsilon ^2)k. \end{aligned}$$

(iii) Part (1) According to the notation of Lemma 1, let $\varGamma = \{\{i,j\}; i,j \in [m] \text{ are } \text{ dependent } \}$ and put $\gamma = \sum _{\{i,j\} \in \varGamma }\mathbb {E}(Z_{i}Z_{j})$. Since the $Z_{i}$’s are functions of the random variables $X_{k},~ k\in E_{i}$, for every $E_{i},E_{j}\in \mathcal {E}$ the random variables $Z_{i}, Z_{j}$ are not independent iff the hyperedges $E_{i}$ and $E_{j}$ have a non-empty intersection. Thus, for a fixed $E_{i}$, there are at the most $D$ random variables $Z_{j}$ possibly depending on $Z_{i}$. For every $E_{i}, E_{j}\in \mathcal {E}$ we have

$$\begin{aligned} \mathbb {E}(Z_{i}Z_{j})&= \Pr (Z_{i}=1\wedge Z_{j}=1)\\&\le \min \{\Pr (Z_{i}=1),\Pr ( Z_{j}=1)\}\\&\le \frac{\Pr (Z_{i}=1)+\Pr ( Z_{j}=1)}{2}. \end{aligned}$$

So

$$\begin{aligned} \gamma&=\sum _{\{i,j\}\in \varGamma }\mathbb {E}(Z_{i}Z_{j})\\&\le \sum _{\{i,j\}\in \varGamma }\frac{\Pr (Z_{i}=1)+\Pr ( Z_{j}=1)}{2}\\&\le \sum _{i=1}^m\frac{D}{2}\Pr (Z_{i}=1)= \frac{D}{2}\mathbb {E}(W). \end{aligned}$$

With Lemma 1 we conclude

$$\begin{aligned} \mathrm{Var}(W)\le \mathbb {E}(W) + 2\gamma \le \mathbb {E}(W) + D\mathbb {E}(W)=(D+1)\mathbb {E}(W). \end{aligned}$$

(iii) Part (2) We modify the proof of (iii) part (1). Let $U_j$ be the 0/1 random variable, which is 1 iff the vertex $j$ is contained in the final cover $C$ after repairing. According to the notation of Lemma 1, let $\varGamma = \{\{i,j\}; i,j \in [n] \text{ are } \text{ dependent } \}$ and let $\gamma = \sum _{\{i,j\} \in \varGamma }\mathbb {E}(U_{i}U_{j})$. Furthermore for every pair $U_{i},U_{j}\in \mathcal {E}$, $U_{i},U_{j}$ are not independent, if the selection of vertex $i$ into the final cover depends on the selection of vertex $j$ into the final cover, and vice versa. We have

$$\begin{aligned} \mathbb {E}(U_{i}U_{j})&= \Pr (U_{i}=1\wedge U_{j}=1)\\&\le \min \{\Pr (U_{i}=1), \Pr ( U_{j}=1)\}\\&\le \frac{\Pr (U_{i}=1)+\Pr ( U_{j}=1)}{2}. \end{aligned}$$

So

$$\begin{aligned} \gamma&=\sum _{\{i,j\}\in \varGamma }\mathbb {E}(U_{i}U_{j})\\ {}&\le \sum _{\{i,j\}\in \varGamma }\frac{\Pr (U_{i}=1)+\Pr ( U_{j}=1)}{2}\\&\le \sum _{i=1}^n\frac{\varDelta (l-1)}{2}\Pr (U_{i}=1)=\frac{\varDelta (l-1)}{2}\mathbb {E}(|C|). \end{aligned}$$

The last inequality is based on the following argument: for every pair $U_{i},U_{j}\in \mathcal {E}$, $U_{i},U_{j}$ are not independent, if the selection of vertex $i$ into $C$ depends on the selection of vertex $j$, and vice versa. The selection of vertex $i$ can be affected by vertices contained in edges incident in $i$ and these are at most $\varDelta (l - 1)$.

With Lemma 1 we conclude

$$\begin{aligned} \mathrm{Var}(|C|)\!\le \! \mathbb {E}(|C|) \!+\! 2\gamma \le \mathbb {E}(|C|) \!+\! \varDelta (l\!-\!1)\mathbb {E}(|C|)\!=\!(\varDelta (l-1)\!+\!1)\mathbb {E}(|C|)\le l\varDelta \mathbb {E}(|C|). \end{aligned}$$

(iv) Since $x^*$ and $z^*$ are optimal solutions of LP-$k$-VC, we have

$$\begin{aligned} k\le \sum _{i=1}^{m}z^{*}_{i}\le \sum _{i=1}^{m}\sum _{j\in E_{i}}x^{*}_{j}= \sum _{j=1}^{n}d(v_{j})x^{*}_{j} \le \varDelta \sum _{j=1}^{n}x_{j}^{*}=\varDelta \cdot \mathrm {Opt}^{*}\le D\cdot \mathrm {Opt}^{*}. \end{aligned}$$

(v) For a set $X \subset V$, we define $\mathrm {Opt}^{*}(X) := \sum _{j\in X}^{n}x^{*}_{j}$. By using the LP relaxation and the definition of the sets $S_{1},\, S_{\ge }$ and $S_{<}$, and since $\lambda \ge 1$, we get

$$\begin{aligned} \mathrm {Opt}^{*} \le \underbrace{|S_{1}| + |S_{\ge }|+ \lambda \mathrm {Opt}^{*}(S_{<})}_{=\mathbb {E}(Y)} \le \underbrace{|S_{1}|}_{\le \lambda \mathrm {Opt}^{*}(S_{1})}+ \underbrace{|S_{\ge }|}_{\le \lambda \mathrm {Opt}^{*}(S_{\ge })}+ \, \lambda \mathrm {Opt}^{*}(S_{<}) \le \lambda \mathrm {Opt}^{*}. \end{aligned}$$

(vi) Let $r_{j}$ the size of the hyperedge $E_{j}$, $j \in [m]$. Then trivially $\sum _{v\in V}d(v)^{2}\le \varDelta \sum _{v\in V}d(v).$ From $\sum _{v\in V}d(v)=\sum _{j=1}^{m}r_{j}$, and $l=\max _{j\in [m]}r_{j}$ the assertion (vi) follows. $\square$

4 Hypergraphs with constant $l$ and $\varDelta$

We consider in this section a $l$-uniform hypergraph with maximum vertex degree $\varDelta$, where $l, \varDelta$ are constants. Let $A$ be the set of vertices added by randomized rounding to $C$, and $B$ be set of vertices added by the repairing step to $C$. Let $Y, W$ be the random variables as defined in (4) resp. (6). Then, obviously

$$\begin{aligned} C = S_1 \cup S_{\ge } \cup A \cup B \, \text{ and } \, |C| = Y + |B| \le Y + k - W. \end{aligned}$$

(8)

To run the algorithm $k$-VC($\mathcal{H}$) we have to choose $\epsilon$. We define

$$\begin{aligned} \epsilon := l\text{ Opt }^*/2k \end{aligned}$$

(9)

It must be ensured that $\epsilon \in (0,1)$:

Proposition 3

If $\epsilon > 1/2$, then a simple polynomial-time algorithm returns a $k$-partial vertex cover which is an approximation with ratio strictly smaller than $l$, without any further assumption on the degree $D$ and $\varDelta$, and on $l$.

Proof

If $\epsilon > 1/2$, then $l\mathrm {Opt}^{*} > k$. A $k$-partial vertex cover of cardinality $k$ can be found trivially by selecting $k$ arbitrary hyperedges and picking one vertex out of each of them. This cover approximates the optimum within a ratio strictly smaller than $l$. $\square$

By Proposition 3 we may assume w.l.o.g

$$\begin{aligned} 0 \le \epsilon \le 1/2, \, \text{ and } \text{ thus }\, \lambda \ge 1 \, \text{ for } \text{ any } \, l\ge 2, \end{aligned}$$

(10)

and run the algorithm $k$-VC($\mathcal{H}$) with $\epsilon$ as in (9).

Lemma 4

$\mathbb {E}(|C|)\le l\left( 1-\frac{l}{4\varDelta }\right) \mathrm {Opt}^{*}$

Proof

We have

$\square$

Lemma 4 and Theorem 1 imply the following theorem.

Theorem 4

Let $l, \varDelta$ be constants and let $\mathcal {H}$ be an $l$-uniform hypergraph with maximum vertex degree $\varDelta$. We further assume that $2\le l \le 4\varDelta$. Then the algorithm $k$-VC($\mathcal{H}$) returns a $k$-partial vertex cover $C$ such that

$$\begin{aligned} |C|\le l\left( 1-\frac{l-1}{4\varDelta }\right) \mathrm {Opt}^{*} \, \text{ with } \text{ probability } \text{ at } \text{ least } \quad 2/3 . \end{aligned}$$

Proof

By Proposition 1 we may assume $k\ge 32 \varDelta ^4$ w.l.o.g. We have

By Lemma 3, $\mathrm{Var}(|C|)\le l\varDelta \mathbb {E}(|C|),$ so

Therefore we get $\Pr \left( |C|\ge l\left( 1-\frac{l-1}{4\varDelta }\right) \mathrm {Opt}^{*}\right) \le \frac{1}{1+ 2} = 1/3.$ $\square$

The proof required $l \le 4\varDelta$. As $\varDelta$ is assumed to be constant, so $l$ is constant as well. That is the reason why we cannot transfer this approach to the more general setting, where the maximum edge degree $D$ resp. the maximum vertex degree $\varDelta$ are constant, but $l$ is not constant, see the upcoming Sects. 5 and 6.

5 Analysis for bounded edge degree

In this section we consider hypergraphs with maximum edge size $l \in \mathbb {N}, l \ge 3$, not necessarily assumed to be a constant, but with a constant maximum edge degree $D$. W.l.o.g we may assume that $D \ge 1$, because otherwise we only have isolated edges and the partial vertex cover problem is trivial. We choose

$$\begin{aligned} \epsilon :=\frac{\mathrm {Opt}^{*}(1+\beta )}{k} \quad \text{ where } \quad \beta =\frac{1}{3D}. \end{aligned}$$

(11)

Again we have to ensure that w.l.o.g $\epsilon \in (0,1)$.

Proposition 4

We can assume that

$$\begin{aligned} \epsilon \le \frac{1+\beta }{l-\eta },\quad \text{ with } \quad \eta =\frac{l}{6D}, \end{aligned}$$

(12)

in particular, $\epsilon \le 1/2$.

Proof

Otherwise if $\epsilon > \frac{1+\beta }{l-\eta }$, it follows from the definition of $\epsilon$ in (11) that $\mathrm {Opt}^{*} > \frac{k}{l-\eta }$, hence $l(1-\frac{\eta }{l})\mathrm {Opt}^{*} > k$. Since a partial vertex cover of size $k$ can be trivially found by picking $k$ arbitrary hyperedges and taking one vertex from each of them, pairwise distinct, we get the claimed $l(1-\frac{\eta }{l})$ approximation ratio. $\square$

So (12) and $\epsilon \in (0,1)$ holds w.l.o.g. and we may run the algorithm $k$-VC-($\mathcal {H}$) with this $\epsilon$ and $\lambda =l(1-\epsilon )$. Note that $\lambda \ge 1$ due to $l\ge 3$. The main result of this section is:

Theorem 5

Let $\mathcal {H}$ be a hypergraph with edge size at most $l,\, l\ge 3$, and constant maximum edge degree D. The algorithm $k$-VC-($\mathcal {H}$) with $\epsilon$ defined as in (11) and satisfying (12) returns a $k$-partial vertex cover $C$ such that

$$\begin{aligned} |C|\le l\left( 1-\frac{1}{6D}\right) \mathrm {Opt} \quad \text{ with } \text{ probability } \text{ at } \text{ least } \quad \frac{7}{15}. \end{aligned}$$

Proof

Claim 1

$$\begin{aligned} \Pr \left( W\le k(1-\epsilon ^2)-2\sqrt{kD}\right) \le \frac{1}{3} \end{aligned}$$

Proof of Claim 1 We can assume that $k(1-\epsilon ^2)-2\sqrt{kD}$ is non-negative. Otherwise, since $W\ge 0$ the event ”$W\le k(1-\epsilon ^2)-2\sqrt{kD}$” has probability 0.

Let us consider the function

$$\begin{aligned} f:(D,\infty )\rightarrow \mathbb {R}, f(x)=x-2\sqrt{Dx}, x \in (D, \infty ). \end{aligned}$$

Since $f^{\prime }(x)=1-\sqrt{\frac{D}{x}}>0$, $f$ is strictly monotone increasing. For $k<4D$ it holds

$$\begin{aligned} k(1-\epsilon ^2)-2\sqrt{kD}\le \underbrace{k-2\sqrt{kD}}_{=f(k)}< f(4D)=0, \end{aligned}$$

and because $W\ge 0$,    $\Pr \left( W\le k(1-\epsilon ^2)-2\sqrt{kD}\right) =0$.

Therefore, we can assume $k\ge 4D$. We set $\mu :=\mathbb {E}(W)$. Using $\epsilon \le \frac{1}{2}$ we get

$$\begin{aligned} k(1-\epsilon ^2) \ge 4D(1-\epsilon ^2)> 4D(1-\frac{1}{4})= 3D>D. \end{aligned}$$

By Lemma 3(ii), $k(1-\epsilon ^2) \le \mu$, and as $f$ is monotone increasing, $f(k(1-\epsilon ^2))\le f(\mu )$. We continue

This concludes the proof of Claim 1.

Claim 2 For $\beta = \frac{1}{3D}$ it holds $\Pr \left( Y\ge l\cdot \mathrm {Opt}^{*}(1-\epsilon )(1+\beta )\right) < \frac{1}{5}$.

Proof of Claim 2 According to Proposition 1 we may assume that

$$\begin{aligned} k\ge 16 D^{5}. \end{aligned}$$

(13)

The random variables $X_{1},\ldots ,X_{n}$ defined as in (3) are independent and an application of the Angulin-Valiant bound, Theorem 3, shows

Note that

$$\begin{aligned} \frac{\mathbb {E}(Y)\beta ^2}{3}\underset{\text {Lem 3}(v)}{\ge }\frac{ \mathrm {Opt}^{*}}{27D^2}\underset{\text {Lem 3}(iv)}{\ge } \frac{k}{27D^3} \ge \frac{16D^2}{27} . \end{aligned}$$

Using $D \ge 2$ we continue

$$\begin{aligned} \Pr \left( Y\ge l(1-\epsilon )(1+\beta )\mathrm {Opt}^{*}\right) \le \exp {\left( -\frac{16D^2}{27}\right) } \le \exp {\left( -\frac{64}{27}\right) }\le \exp {(-2)}< \frac{1}{5}. \end{aligned}$$

This concludes the proof of Claim 2.

By Claim 1 and 2 we get for the final partial vertex cover $C$ with probability at least $1-(\frac{1}{5}+\frac{1}{3})=\frac{7}{15}$

$$\begin{aligned} |C|\le \underbrace{l(1-\epsilon )(1+\beta )\mathrm {Opt}^{*}+k\epsilon ^{2}}_{(*)}+ \underbrace{2\sqrt{kD}}_{(**)}. \end{aligned}$$

We estimate the terms (*) and (**) in the right hand side separately.

Using $l\ge 3$ we have

$$\begin{aligned} \frac{(l-1)(1+\beta )^{2}}{lD}-\beta \ge \frac{ 2(1+\beta )^{2}}{3D}-\frac{1}{3D} \ge \frac{1}{3D}, \end{aligned}$$

therefore

$$\begin{aligned} l(1-\epsilon )(1+\beta )\mathrm {Opt}^{*}+k\epsilon ^{2}\le l\left( 1-\frac{1}{3D}\right) \mathrm {Opt}^{*}. \end{aligned}$$

We proceed to the second term (**). By Lemma 3(iv) we have $\mathrm {Opt}^{*}\ge \frac{k}{D}\ge 16 D^{4}$, so

Finally,

holds with probability at least 7/15. $\square$

6 Analysis for constant vertex degree

In this section we consider hypergraphs with edge size at most $l$, $l \ge 3$ non-constant, but with constant maximum vertex degree $\varDelta$. We may assume $\varDelta \ge 2$, because otherwise the hypergraph has only isolated edges and the $k$-partial vertex cover problem is trivial. One may ask if the approach in the last section is transferable to our present situation, just replacing $D$ by $\varDelta$. In fact, everything works, except the proof of Claim 1. There we would get the estimate

$$\begin{aligned} \frac{1}{1+\frac{4\mu \varDelta }{\mathrm{Var}(W)}} \le \frac{1}{1+\frac{4\mu \varDelta }{\mu (D + 1)}}. \end{aligned}$$

(14)

With the (trivial) estimate $D \le l \varDelta$, the last term is at most $\frac{1}{1+\frac{4\varDelta }{l\varDelta + 1}}$ which is smaller than $1/(1 +c)$ for a constant $c > 0$, if $l \le 4/c - 1$, thus $l\le 2$. We are back to graphs, where such an approximation is known Gandhi et al. (2004), and have gained nothing. In the following we will demonstrate, how an involvement of the Hoeffding–Azuma bound in form of the bounded difference inequality can overcome this restriction and can handle hypergraphs with $l \ge 3$. We wish to run the algorithm $k$-VC-($\mathcal {H}$) and choose

$$\begin{aligned} \epsilon :=\frac{\mathrm {Opt}^{*}(1+\beta _{1})}{k} \quad \text{ for } \quad \beta _{1}=\frac{1}{3\varDelta }. \end{aligned}$$

(15)

Again, w.l.o.g. we can assume $\epsilon \le 1/2$:

Proposition 5

We can assume that

$$\begin{aligned} \epsilon \le \frac{1+\beta _{1}}{l-\eta },\quad \text{ with } \quad \eta =\frac{l}{6\varDelta }. \end{aligned}$$

(16)

In particular, $\epsilon \le 1/2$

Proof

Otherwise, if $\epsilon > \frac{1+\beta _1}{l-\eta }$, it follows from the definition of $\epsilon$ in (15) that $\mathrm {Opt}^{*} > \frac{k}{l-\eta }$, hence $l(1-\frac{\eta }{l})\mathrm {Opt}^{*} > k$. Since a partial vertex cover of size $k$ can be trivially found by picking $k$ arbitrary hyperedges and taking one vertex from each of them, pairwise distinct, we get a $l(1-\frac{\eta }{l})$ approximation ratio, which is even better than the ratio in Theorem 6. $\square$

So (16) and $\epsilon \in (0,1)$ hold w.l.o.g. and we may run the algorithm $k$-VC-($\mathcal {H}$) with this $\epsilon$ and $\lambda =l(1-\epsilon )$. Note that $\lambda \ge 1$ due to $l\ge 3$. Its analysis gives

Theorem 6

Let $\mathcal {H}$ be a hypergraph with edge size at most $l$, $l\ge 3$ non-constant, and bounded vertex degree $\varDelta$. For $k\ge \frac{m}{4}$ the algorithm $k$-VC($\mathcal {H}$) returns a $k$-partial vertex cover $C$ such that

$$\begin{aligned} |C|\le l\left( 1-\frac{2 - \sqrt{3}}{6\varDelta }\right) \mathrm {Opt} \quad \text{ with } \text{ probability } \text{ at } \text{ least }\quad \frac{3}{5}. \end{aligned}$$

This is an improvement over Theorem 5 because in general $\varDelta \le D$.

.

Proof of Theorem 6

We need the following claim and shall prove it with the bounded difference inequality, Theorem 2.

Claim 4

$$\begin{aligned} \Pr \left( W\le k(1-\epsilon ^2)-2\sqrt{kl\varDelta }\right) \le \frac{1}{5}. \end{aligned}$$

Proof of Claim 4 Because $W\ge 0$, we can assume that the upper bound on $W$ in Claim 4 is non-negative. $W$ itself is a function

$$\begin{aligned} W: \{0, 1\}^n \longrightarrow \mathbb {N}\quad , W(X_{1},\ldots ,X_{n})=\sum _{j=1}^{m}Z_{j}. \end{aligned}$$

$W$ is component-wise Lipschitz bounded: Let $k \in [n]$, $X \!=\! (X_{1},\ldots ,X_{k-1}, X_{k},X_{k+1},\ldots ,X_{n})$ and

$X^{'} = (X_{1},\ldots ,X_{k-1}, X^{'}_{k},X_{k+1},\ldots ,X_{n})$. Then

$$\begin{aligned} |W(X)-W(X^{'})| \le d(v_{k})\, \text{ for } \text{ all } \,k. \end{aligned}$$

This is true, because as $X_k, X^{'}_k$ differ, the two associated covers $C$ resp. $C^{'}$ differ by the vertex $v_{k}$. But then the edges hit by $C$ resp. $C^{'}$ differ by at most $d(v_k)$ edges. By Theorem 2 we get for any $t > 0$,

$$\begin{aligned} \Pr (W-\mathbb {E}(W)\le -t)\le \exp \left( \frac{-2t^{2}}{\sum _{v\in V}d(v)^{2}}\right) . \end{aligned}$$

(17)

We choose $t=2\sqrt{\varDelta lk}$.

and Claim 4 is proved.

Claim 5 For $\beta _{1} = \frac{1}{3\varDelta }$ it holds $\Pr \left( Y\ge l\cdot \mathrm {Opt}^{*}(1-\epsilon )(1+\beta _{1})\right) < \frac{1}{5}$.

Proof of Claim 5 Again, Proposition 1 allows to assume w.l.o.g

$$\begin{aligned} k\ge 16 \varDelta ^{5}. \end{aligned}$$

(18)

The Angulin-Valiant inequality yields

With Lemma 3 (iv) resp. (v), $k\ge 16 \varDelta ^{5}$ and $\varDelta \ge 2$ we get

$$\begin{aligned} \frac{\mathbb {E}(Y)\beta _{1}^2}{3}\ge \frac{k}{27\varDelta ^3} \ge \frac{16\varDelta ^2}{27} \ge \frac{64}{27} \ge 2. \end{aligned}$$

So

$$\begin{aligned} \Pr \left( Y\ge l(1-\epsilon )(1+\beta _{1})\mathrm {Opt}^{*}\right)&\le \exp {(-2)}< \frac{1}{5}. \end{aligned}$$

This concludes the proof of Claim 5.

By Claim 4 and 5 we get an upper bound for the final cover with probability at least $1-(\frac{1}{5}+ \frac{1}{5})\ge \frac{3}{5}$:

$$\begin{aligned} |C|\le \underbrace{l(1-\epsilon )(1+\beta _{1})\mathrm {Opt}^{*}+k\epsilon ^{2}}_{(*)}+ \underbrace{2\sqrt{kl\varDelta }}_{(**)}. \end{aligned}$$

As in the proof of Theorem 5 we can show

$$\begin{aligned} (*)=l(1-\epsilon )(1+\beta _{1})\mathrm {Opt}^{*}+k\epsilon ^{2}\le l\left( 1-\frac{1}{3\varDelta }\right) \mathrm {Opt}^{*}. \end{aligned}$$

By Lemma 3(iv) and (18) it holds:

$$\begin{aligned} \mathrm {Opt}^{*}\ge \frac{k}{\varDelta }\ge 16 \varDelta ^{4}, \end{aligned}$$

so

Finally the sum of $(*)$ and $(**)$ is

$$\begin{aligned} (*) + (**)&\le l\mathrm {Opt}^{*}\left( 1-\frac{1}{3\varDelta }\right) + l\mathrm {Opt}^{*}\frac{2}{\varDelta \sqrt{48} } \\&\le l\left( 1-\frac{1}{3\varDelta }+ \frac{2}{\varDelta \sqrt{48} }\right) \mathrm {Opt}^{*}\\&= l\left( 1-\frac{2-\sqrt{3}}{6\varDelta }\right) \mathrm {Opt}^{*}, \end{aligned}$$

and this holds with probability at least 3/5.$\square$

This result shows again a hypergraph characteristic. An approximation ratio of the form $l\left( 1-\frac{c}{\varDelta }\right)$ for some constant $c > 0$ is valid for hypergraphs and the $k$-partial vertex cover problem with $k\ge m/4$, while in graphs it is valid for any $k$. By examining our probabilistic arguments, there seems to be no obvious way to release the restriction on $k$. We leave it as an open problem to prove or to disprove an approximation ratio of the form $l\left( 1-\frac{c}{\varDelta }\right)$ for constant $\varDelta$ and $k < m/4$. In view of Theorem 4, the first interesting hypergraph for the investigation of this problem would be a $\varDelta$-regular and $(4\varDelta + 1)$-uniform hypergraph. For such hypergraphs, none of our results apply, if we consider $k < m/4$.

7 Further work

We find it interesting to give better approximations for hypergraphs with other kind of sparseness conditions, like uncrowdedness or small VC-dimension. Another challenge is the derandomization of this and other hybrid algorithms combining randomized rounding and greedy heuristic in order to obtain feasible solutions.