# Efficient Algorithms for the max k-vertex cover Problem

Federico Della Croce, Vangelis Paschos

► To cite this version:

Federico Della Croce, Vangelis Paschos. Efficient Algorithms for the max k-vertex cover Problem. 7th International Conference on Theoretical Computer Science (TCS), Sep 2012, Amsterdam, Netherlands. pp.295-309, 10.1007/978-3-642-33475-7_21. hal-01511883

HAL Id: hal-01511883

https://hal.science/hal-01511883

Submitted on 4 Jul 2017

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Efficient algorithms for the MAX *k*- VERTEX COVER problem*

Federico Della Croce<fnref n="1" /> and Vangelis Th. Paschos<fnref n="2" />,<fnref n="3" />

**Abstract.** We first devise moderately exponential exact algorithms for MAX *k*- VERTEX COVER, with time-complexity exponential in *n* but with polynomial space-complexity by developing a branch and reduce method based upon the measure-and-conquer technique. We then prove that, there exists an exact algorithm for MAX *k*- VERTEX COVER with complexity bounded above by the maximum among $c^k$ and $\gamma^\tau$, for some $\gamma < 2$, where $\tau$ is the cardinality of a minimum vertex cover of $G$ (note that MAX *k*- VERTEX COVER $\notin$ FPT with respect to parameter *k* unless FPT = W[1]), using polynomial space. We finally study approximation of MAX *k*- VERTEX COVER by moderately exponential algorithms. The general goal of the issue of moderately exponential approximation is to catch-up on polynomial inapproximability, by providing algorithms achieving, with worst-case running times importantly smaller than those needed for exact computation, approximation ratios unachievable in polynomial time.

# 1 Introduction

In the MAX *k*- VERTEX COVER problem a graph $G(V, E)$ with $|V| = n$ vertices $1, \dots, n$ and $|E|$ edges $(i, j)$ is given together with an integer value $k < n$. The goal is to find a subset $K \subset V$ with cardinality $k$, that is $|K| = k$, such that the total number of edges covered by $K$ is maximized. In its decision version, MAX *k*- VERTEX COVER can be defined as follows: “given $G$, $k$ and $\ell$, does $G$ contain $k$ vertices that cover at least $\ell$ edges?”. MAX *k*- VERTEX COVER is NP-hard (it contains the minimum vertex cover problem as particular case), but it is polynomially approximable within approximation ratio 3/4, while it cannot be solved by a polynomial time approximation schema unless $P = NP$. The interested reader can be referred to [18, 30] for more information about approximation issues for this problem.

In the literature, we often find this problem under the name PARTIAL VERTEX COVER problem. It is mainly studied from a parameterized complexity point of

<footnote n="1">¹D.A.I., Politecnico di Torino, Italy, federico.dellacroce@polito.it</footnote>

<footnote n="2">²PSL Research University, Université Paris-Dauphine, LAMSADE, CNRS, UMR 7243, France, paschos@lamsade.dauphine.fr</footnote>

<footnote n="3">³Institut Universitaire de France</footnote>

<footnote>* Research supported by the French Agency for Research under the program TODO, ANR-09-EMER-010 and by a Lagrange fellowship of the Fondazione CRT, Torino, Italy</footnote>
view (see [17] for information on fixed-parameter (in)tractability). A problem is
fixed-parameter tractable with respect to a parameter *t*, if it can be solved (to
optimality) with time-complexity *O*(*f*(*t*)*p*(*n*)) where *f* is a function that depends
on the parameter *t*, and *p* is a polynomial on the size *n* of the instance. In
what follows, when dealing with fixed parameter tractability of MAX *k*- VERTEX
COVER, we shall use notation MAX *k*- VERTEX COVER(*t*) to denote that we speak
about fixed parameter tractability with respect to parameter *t*. Parameterized
complexity issues for MAX *k*- VERTEX COVER are first studied in [3] where it is
proved that PARTIAL VERTEX COVER is fixed-parameter tractable with respect
to parameter *l*, next in [28] where it is proved that it is W[1]-hard with respect
to parameter *k* (another proof of the same result can be found in [9]) and finally
in [31] where the fixed-parameter tractability results of [3] are further improved.
Let us also quote the paper by [24], where it is proved that in apex-minor-free
graphs, PARTIAL VERTEX COVER can be solved with complexity that is
subexponential in *k*.

The seminal Courcelle's Theorem [13] (see also [21, 20] as well as [37] for a
comprehensive study around this theorem) assures that decision problems de-
fined on graphs that are expressible in terms of monadic second-order logic
formulæ are fixed parameter tractable when the treewidth<fnref n="1" /> of the the input-
graph *G*, denoted by *w*, is used as parameter. Courcelle's Theorem can be also
extended to a broad class of optimization problems [1]. As MAX k-VERTEX COVER
belongs to this class, it is fixed parameter tractable with respect to *w*. In most
of cases, "rough" application of this theorem, involves very large functions *f*(*w*)
(see definition of fixed-parameter tractability given above).

In [34], it is proved that *given a nice tree decomposition, there exists a fixed-parameter algorithm (based upon dynamic programming), with respect to parameter *w* that solves MAX *k*- VERTEX COVER in time* O(*2*^*w*·k(*w*^2 + *k*)·|*I*|), where |*I*| is the number of nodes of the nice tree decomposition and in exponential space.
In other words, MAX *k*- VERTEX COVER(*w*) ∈ **FPT**, but the fixed-parameter algorithm of [34] uses exponential space. Let us note that in any graph *G*, denoting by τ the size of a minimum vertex cover of *G*, it holds that *w* ≤ τ. So, MAX *k*- VERTEX COVER(*τ*) ∈ **FPT** too, but through the use of exponential space (recall that, as adopted above, MAX *k*- VERTEX COVER(*τ*) denotes the MAX *k*- VERTEX COVER problem parameterized by the size τ of a minimum vertex cover.

Very frequently, a serious problem about fixed-parameter tractability with
respect to *w* is that it takes too much time to compute the “nice tree decomposi-
tion” that also derives the value of *w*. More precisely, this takes time *O*(1.7549ⁿ)
(notation *O**(·) ignores polynomial factors) by making use of exponential space

<footnote n="1">¹ A tree decomposition of a graph *G*(*V*, *E*) is a pair (*X*, *T*) where *T* is a tree on vertex set *V*(*T*) the vertices of which we call nodes and *X* = {*X*ᵢ : *i* ∈ *V*(*T*)} is a collection of subsets of *V* such that: (i) ⋃ᵢ∈*V*(*T*) *X*ᵢ = *V*, (ii) for each edge (*v*, *w*) ∈ *E*, there exist an *i* ∈ *V*(*T*) such that {*v*, *w*} ∈ *X*ᵢ, and (iii) for each *v* ∈ *V*, the set of nodes {*i* : *v* ∈ *X*ᵢ} forms a subtree of *T*. The width of a tree decomposition ({*X*ᵢ : *i* ∈ *V*(*T*)}, *T*) equals maxᵢ∈*V*(*T*){|*X*ᵢ| - 1}. The treewidth of a graph *G* is the minimum width over all tree decompositions of *G*.</footnote>
## 2 An $O^*(2^{\frac{\Delta-1}{\Delta+1}n})$-time polynomial space algorithm in general graphs

In what follows, we denote by $\alpha_j$ the total number of vertices adjacent to $j$ that have been discarded in the previous levels of the search tree. We denote by $d_j$ the degree of vertex $j$ and by $N(j)$ the set of vertices adjacent to $j$, that is the neighborhood of $j$. Notice that, whenever a branch on a vertex $j$ occurs, for each $l \in N(j)$, if $j$ is selected then $d_l$ is decreased by one unit as edge $(j, l)$ is already covered by $j$. Alternatively, $j$ is discarded: correspondingly $d_l$ is not modified and $\alpha_l$ is increased by one unit. We propose in this section a branch and reduce approach based on the measure-and-conquer paradigm (see for instance [22]). Consider a classical binary branching scheme on some vertex $j$ where $j$ is either selected or discarded. Contrarily to the classical branch-and-reduce paradigm where for each level of the search tree we define as fixed those vertices that have already been selected or discarded, while we define as free the other vertices, when using measure-and-conquer, we do not count in the measure the fixed vertices, namely the vertices that have been either selected or discarded at an earlier stage of the search tree and we count with a weight $w_h$ the free vertices $h$. The vertex $j$ to be selected is the one with largest coefficient $c_j = d_j - \alpha_j$. Let $c_{max}$ denote such a coefficient, hence $c_{max} \le \Delta$. Then, each free vertex $h$ is assigned a weight $w_h = w_{[1]}$ with $i = c_i = d_h - \alpha_h$ and we impose $w_{[0]} \le w_{[1]} \le w_{[2]} \le w_{[3]} \le \dots \le w_{[c_{max}]} = 1$ that is the weights of the vertices are strictly increasing in their $c_j$ coefficients.

We so get recurrences on the time $T(p)$ required to solve instances of size $p$, where the size of an instance is the sum of the weights of its vertices. Since initially $p = n$, the overall running time is expressed as a function of $n$. This is valid since when $p = 0$, there are only vertices with weight $w_{[0]}$ in the graph and, in this case, the problem is immediately solved by selecting the $k - \gamma$ vertices with largest $\alpha_j$ (if $\gamma < k$ vertices have been selected so far). Correspondingly free vertices $j$ with no adjacent free vertices receive weight $w_{[0]} = 0$.

We claim that MAX $k$- VERTEX COVER can be solved with running time $O^*(2^{\frac{\Delta-1}{\Delta+1}n})$ by the following algorithm called MAXKVC:

Select $j$ such that $c_j$ is maximum and branch according to the following exhaustive cases:

1. if $c_j \ge 3$, then branch on $j$ and either select or discard $j$;

2. else, $c_j \le 2$ and MAXKVC is polynomially solvable.

**Theorem 1.** *Algorithm MAXKVC solves MAX $k$- VERTEX COVER with running time $O^*(2^{\frac{\Delta-1}{\Delta+1}n})$ using polynomial space.*

*Proof.* To prove the above statement, we first show that the branch in step 1 can be solved with complexity $O^*(2^{\frac{\Delta-1}{\Delta+1}n})$ and then we show that step 2 is polynomially solvable. Consider step 1. We always branch on the vertex $j$ with largest $c_j = c_{max} \le \Delta$ where $c_j \ge 3$ and either we select or discard $j$. If we select $j$, vertex $j$ is fixed and $c_{max}$ vertices (the neighbors of $j$) decrease their degree (and
correspondingly their coefficient) by one unit. Similarly, if we discard j, vertex j is fixed and c<sub>max</sub> vertices (the neighbors of j) decrease their coefficient as their degree remains unchanged but their α parameter is increased by one unit. Hence, the recurrence becomes:

$$
T(p) \le 2T \left( p - w_{[c_{\max}]} - \sum_{h \in N(j)} (w_{[c_h]} - w_{[c_{h-1}]}) \right)
$$

By constraining the weights to satisfy the inequality:

$$
w_{[j]} - w_{[j-1]} \le w_{[j-1]} - w_{[j-2]} \quad \forall j = 2, \dots, c_{\max}
$$

the previous recurrence becomes in the worst-case:

$$
T(p) \le 2T (p - w_{[c_{\max}]} - c_{\max} (w_{[c_{\max}]} - w_{[c_{\max}-1]}))
$$

As c<sub>max</sub> &le; &Delta;, where the equality occurs when &alpha;<sub>j</sub> = 0, the above recurrence becomes, in the worst-case, T(p) &le; 2T (p &minus; w<sub>[&Delta;]</sub> &minus; &Delta; (w<sub>[&Delta;]</sub> &minus; w<sub>[&Delta;&minus;1]</sub>)).

Summarizing, to handle graphs with maximum degree Δ, we need to guar-
antee that the recurrences T(p) ≤ 2T(p − w<sub>[i]</sub> − i(w<sub>[i]</sub> − w<sub>[i−1]</sub>)), ∀i ∈ 3, . . . , Δ
(as c<sub>j</sub> ≥ 3), and the constraints:

$$
\begin{align*}
w_{[i]} - w_{[i-1]} &\le w_{[i-1]} - w_{[i-2]} \quad \forall i = 2, \dots, \Delta \\
0 &= w_{[0]} \le w_{[1]} \le w_{[2]} \le w_{[3]} \le \dots \le w_{[\Delta-1]} \le w_{[\Delta]} = 1
\end{align*}
$$

are satisfied simultaneously. This corresponds to a non linear optimization prob-
lem of the form:

min α

$$
\alpha^{(w[i] + i(w[i] - w[i-1]))} \ge 2 \quad \forall i = 3, \dots, \Delta \quad (1)
$$

$$
w_{[i]} - w_{[i-1]} \le w_{[i-1]} - w_{[i-2]} \quad \forall i = 2, \dots, \Delta \quad (2)
$$

$$
0 = w_{[0]} \le w_{[1]} \le w_{[2]} \le w_{[3]} \le \dots \le w_{[\Delta-1]} \le w_{[\Delta]} = 1 \quad (3)
$$

We so get performances 1.4142ⁿ, for Δ = 3, 1.5157ⁿ, for Δ = 4, 1.5866ⁿ, for
Δ = 5, 1.6405ⁿ, for Δ = 6, 1.6817ⁿ, for Δ = 7, or 1.7143ⁿ, for Δ = 8.

Interestingly enough, for all these values of Δ, the complexity corresponds
to $O^*(2^{\frac{\Delta-1}{\Delta+1}n})$. Indeed, this is not accidental. By setting:

$$
w_{[i]} = \frac{(i-1)(\Delta+1)}{(i+1)(\Delta-1)} \quad \forall i = 2, \dots, \Delta \qquad (4)
$$

$$
w_{[1]} = \frac{1}{2} w_{[2]} \tag{5}
$$

$$
w_{[0]} = 0 \tag{6}
$$

we can see that constraints (2) and (3) are satisfied. To see that inequalities (2)
are satisfied, notice that:

$$
w_{[3]} - w_{[2]} = w_{[2]} - w_{[1]} = \frac{1}{3} w_{[3]} \\
w_{[2]} - w_{[1]} = w_{[1]} - w_{[0]} = w_{[1]}
$$

$$
w_{[2]} - w_{[1]} = w_{[1]} - w_{[0]} = w_{[1]}
$$
For the general recursion with $i \ge 4$, we have to show that $w_{[i]} - w_{[i-1]} \le w_{[i-1]} - w_{[i-2]}$, i.e., that $w_{[i]} - 2w_{[i-1]} + w_{[i-2]} \le 0$. This corresponds to:

$$ 
\begin{aligned}
& \left( \frac{i-1}{i+1} - 2\frac{i-2}{i} + \frac{i-3}{i-1} \right) \left( \frac{\Delta+1}{\Delta-1} \right) \le 0 \\
\Rightarrow & \frac{i-1}{i+1} - 2\frac{i-2}{i} + \frac{i-3}{i-1} \le 0 \\
\iff & i(i-1)^2 - 2(i-2)(i^2-1) + i(i-3)i + 1 \le 0 \\
\iff & i^3 - 2i^2 + i - 2i^3 + 4i^2 + 2i - 4 + i^3 - 2i^2 - 3i = -4 \le 0, \quad \forall i
\end{aligned}
$$

Also, to see that inequalities (3) are satisfied, notice that equations (4) imply:

$$ 
\begin{aligned}
w_{[\Delta]} &= 1 \\
w_{[i]} &> 0 \quad \forall i = 2, \dots, \Delta \\
w_{[i]} &> w_{[i-1]} \quad \forall i = 3, \dots, \Delta
\end{aligned}
$$

while equations (5) and (6) imply $w_{[2]} > w_{[1]} > w_{[0]} = 0$.

Finally, notice that such values of $w_{[j]}$s satisfy constraints (1) that now correspond to $\Delta - 2$ copies of the inequality $\alpha^{\frac{\Delta+1}{\Delta-1}} \ge 2$ where the minimum value of $\alpha$ is obviously given by $2^{\frac{\Delta-1}{\Delta+1}n}$. Consequently, the overall complexity of step 1 is $O^*(2^{\frac{\Delta-1}{\Delta+1}n})$.

We consider now step 2. For $c_j = c_{\max} \le 2$, $\max k$- VERTEX COVER can be seen as a maximum weighted k-vertex cover problem in an undirected graph $G$ where each vertex $j$ has a weight $\alpha_j$ and a degree $d_j = c_j$ and the maximum vertex degree is 2. But this problem has been shown to be solvable in $O(n)$ time by dynamic programming in [36]. ♦

### 3 MAX k- VERTEX COVER and fixed-parameter tractability

Denote by $(a - \bar{b} - c)$, a branch of the search tree where vertices $a$ and $c$ are selected and vertex $b$ is discarded. Consider the vertex $j$ with maximum degree $\Delta$ and neighbors $l_1, \dots, l_\Delta$. As $j$ has maximum degree, we may assume that if there exists an optimal solution of the problem where all neighbors of $j$ are discarded, then there exists at least one optimal solution where $j$ is selected. Hence, a branching scheme (called basic branching scheme) on $j$ of type:

$$ [l_1, (\overline{l_1} - l_2), \dots, (\overline{l_1} - \overline{l_2} - \dots - \overline{l_{\Delta-1}} - l_\Delta), (\overline{l_1} - \overline{l_2} - \dots - \overline{l_\Delta} - j)] $$

can be applied. Hence, the following easy but interesting result holds.

**Proposition 1.** The $\max k$- VERTEX COVER problem can be solved to optimality in $O^*(\Delta^k)$.

*Proof.* Consider vertex $j$ with maximum degree $\Delta$ and neighbors $l_1, \dots, l_\Delta$ where the basic branching scheme of type $[l_1, (\overline{l_1} - l_2), (\overline{l_1} - \overline{l_2} - l_3), \dots, (\overline{l_1} - \overline{l_2} - \dots -}$
$\overline{l_{\Delta-1} - l_{\Delta})}, (\overline{l_1 - l_2 - \dots - \overline{l_{\Delta-1} - j})}$ can be applied. Then, the last two branches can be substituted by the branch $(\overline{l_1 - l_2 - \dots - \overline{l_{\Delta-1} - j})$ as, if all neighbors of $j$ but one are not selected, any solution including the last neighbor $l_{\Delta}$ but not including $j$ is not better than the solution that selects $j$.

Now, one can see that the basic branching scheme generates $\Delta$ nodes. On the other hand, we know that in each branch of the basic branching scheme at least one vertex is selected. As, at most $k$ nodes can be selected, the overall complexity cannot be superior to $O^*(\Delta^k)$. ♦

**Corollary 1.** *MAX k- VERTEX COVER(k) in bounded degree graphs is in FPT.*

Note that Corollary 1 can also be proved without reference to Proposition 1. Indeed, in any graph of maximum degree $\Delta$, denoting by $\ell$ the value of an optimal solution for MAX k- VERTEX COVER, $\ell \le k\Delta$. Then, taking ito account that MAX k- VERTEX COVER($\ell$) $\in$ FPT, immediately derives Corollary 1.

Now, let $V' \subset V$ be a minimum vertex cover of $G$ and let $\tau$ be the size of $V'$ that is $\tau = |V'|$. Correspondingly, let $I = V \setminus V'$ be a maximum independent set of $G$ and set $\alpha = |I|$. Notice that $V'$ can be computed, for instance, in $O^*(1.2738^\tau)$ time by means of the fixed-parameter algorithm of [12], and using polynomial space. Let us note that we can assume $k \le \tau$. Otherwise, the optimal value $\ell$ for MAX k- VERTEX COVER would be equal to $|E|$ and one could compute a minimum vertex cover $V'$ in $G$ and then one could arbitrarily add $k - \tau$ vertices without changing the value of the optimal solution.

**Theorem 2.** *The following two assertions hold for MAX k- VERTEX COVER:*

1. there exists an $O^*(2^\tau)$-time algorithm that uses polynomial space;

2. there exists an algorithm running in time $O^*(\max\{\gamma^\tau, c^k\})$, for two constants $\gamma < 2$ and $c > 4$, and needing polynomial space.

*Proof.* For proving item 1, fix some minimum vertex cover $V'$ of $G$ and consider some solution $K$ for MAX k- VERTEX COVER, i.e., some set of $k$ vertices of $G$. Any such set is distributed over $V'$ and its associated independent set $I = V \setminus V'$. Fix now an optimal solution $K^*$ of MAX k- VERTEX COVER and denote by $S'$ the subset of $V'$ that belongs to $K^*$ ($S'$ can be eventually the empty set) and by $I'$ the part of $K^*$ belonging to $I$. In other words, the following hold:

$$ 
\begin{align*} 
K^* &= S' \cup I' \\ 
S' &\subseteq V' \\ 
I' &\subseteq I = V \setminus V' 
\end{align*} 
$$

Given $S'$ (assume $|S'| = k'$), it can be completed into $K^*$ in polynomial time. Indeed, for each vertex $i$ belonging to $I$ we need simply to compute (in linear time) the total number $e_i$ of edges $(i, j)$ for all $j \in V' \setminus S'$. Then, $I'$ is obtained by selecting the $k - k'$ vertices of $I$ with largest $e_i$ value. So, the following algorithm can be used for MAX k- VERTEX COVER:

1. compute a minimum vertex cover $V'$ (using the algorithm of [11]);
2. for every subset $S' \subseteq V'$ of cardinality at most $k$, take the $k - |S'|$ vertices of $V \setminus V'$ with the largest degrees to $V' \setminus S'$; denote by $I'$ this latter set;

3. return the best among the sets $S' \cup I'$ so-computed (i.e., the set that covers the maximum of edges).

Step 1 takes time $O^*(1.2738^\tau)$, while step 2 has total running time $O^*(\sum_{i=1}^k \binom{\tau}{i})$ that is at most $O^*(2^\tau)$.

Note that, from item 1 of Theorem 2, it can be immediately derived that $\max k$- VERTEX COVER can be solved to optimality in $O^*(2^{\frac{\Delta-1}{\Delta}n})$ time. Indeed if a graph $G$ has maximum degree $\Delta$, then for the maximum independent set we have $\alpha \ge \frac{n}{\Delta}$. Also, we can assume that $G$ is not a clique on $\Delta+1$ vertices (note that $\max k$- VERTEX COVER is polynomial in cliques). In this case, $G$ can be colored with $\Delta$ colors [8]. In such a coloring the cardinality of the largest color is greater than $\frac{n}{\Delta}$ and, a fortiori, so is the cardinality of a maximum independent set (since each color is an independent set). Consequently, $\tau \le \frac{\Delta-1}{\Delta}n$.

In what follows, we improve the analysis of item 1 and prove item 2 that claims, informally, the instances of $\max k$- VERTEX COVER that are not fixed-parameter tractable (with respect to $k$) are those solved with running time better than $O^*(2^\tau)$.

For this observe that the running time of the algorithm in the proof of item 1 is $O^*(\sum_{i=1}^k \binom{\tau}{i})$. As mentioned above, $k$ can be assumed to be smaller than, or equal to, $\tau$. Consider some positive constant $\lambda < 1/2$. We distinguish the following two cases: $\tau > k \ge \lambda\tau$ and $k < \lambda\tau$.

If $\tau > k \ge \lambda\tau$, then $\tau \le k/\lambda$. As $\lambda < 1/2$, $k/\lambda > 2k$ and, since $i \le k$, we get using Stirling's formula:

$$ 
\begin{align} 
\sum_{i=1}^{k} \binom{\tau}{i} &\le \sum_{i=1}^{k} \binom{k/\lambda}{i} \le k \binom{k/\lambda}{k} \sim k \frac{\frac{k}{\lambda}^{\frac{k}{\lambda}}}{k^k \left(\frac{k}{\lambda} - k\right)^{\left(\frac{k}{\lambda} - k\right)}} \nonumber \\
&= k \left( \frac{\frac{1}{\lambda}^{\frac{1}{\lambda}}}{\left(\frac{1}{\lambda} - 1\right)^{\left(\frac{1}{\lambda} - 1\right)}} \right)^k = O^*(c^k) \tag{7}
\end{align} 
$$

for some constant $c$ that depends on $\lambda$ and it is fixed if $\lambda$ is so.

If $k < \lambda\tau$, then, by the hypothesis on $\lambda$, $2k < \tau$ and, since $i \le k$, expression $\sum_{i=1}^k \binom{\tau}{i}$ is bounded above by $k \binom{\tau}{k}$. In all, using also Stirling's formula the following holds:

$$ 
\begin{align} 
\sum_{i=1}^{k} \binom{\tau}{i} &\le k \binom{\tau}{k} \le k \binom{\tau}{\lambda\tau} \sim k \frac{\tau^\tau}{(\lambda\tau)^{(\lambda\tau)} [(1-\lambda)\tau]^{(1-\lambda)\tau}} \nonumber \\
&= k \left( \frac{1}{\lambda^\lambda (1-\lambda)^{(1-\lambda)}} \right)^{\tau} \stackrel{\lambda<1/2}{<} O^*(2^\tau) \tag{8}
\end{align} 
$$

In other words, if $k < \lambda\tau$, then $\max k$- VERTEX COVER can be solved in time at most $O^*(\gamma^\tau)$, for some $\gamma$ that depends on $\lambda$ and is always smaller than 2 for $\lambda < 1/2$.
<table><caption>**Table 1.** The values of *c* and *γ* for some values of *λ*.</caption><thead><tr><th>λ</th><th>0.01</th><th>0.05</th><th>0.1</th><th>0.15</th><th>0.2</th><th>0.25</th><th>0.3</th><th>0.35</th><th>0.40</th><th>0.45</th><th>0.49</th></tr></thead><tbody><tr><td>(1/λ - 1)(1/λ - 1)</td><td>270.47</td><td>53.00</td><td>25.81</td><td>16.74</td><td>12.21</td><td>9.48</td><td>7.66</td><td>6.36</td><td>5.38</td><td>4.61</td><td>4.11</td></tr><tr><td>1/λλ(1-λ)1-λ</td><td>1.06</td><td>1.22</td><td>1.38</td><td>1.53</td><td>1.65</td><td>1.75</td><td>1.84</td><td>1.91</td><td>1.96</td><td>1.99</td><td>1.9996</td></tr></tbody></table>

Expressions (7) and (8) derive the claim and conclude the proof. In Table 1 the values of *c* and *γ* are given for some values of *λ*. ♦

Let us note that the technique of item 1 of Theorem 2, that consists of determining a decomposition of the input graph into a minimum vertex cover and a maximum independent set and then of taking a subset *S'* of a minimum vertex cover *V'* of the input-graph and of completing it into an optimal solution can be applied to several other well-known combinatorial NP-hard problems. We sketch here some examples:

- in MIN 3-DOMINATING SET (dominating set in graphs of maximum degree 3), the set *S'* is completed in the following way:

* take all the vertices in $I \setminus \Gamma_I(S')$ (in order to dominate vertices in $V' \setminus S'$);

* if there remain vertices of $V' \setminus S'$ not dominated yet solve a MIN SET COVER problem considering $\Gamma_I(S')$ as the set-system of the latter problem and assuming that a vertex $v \in \Gamma_I(S')$, seen as set, contains its neighbors in $V' \setminus S'$ as elements; since $\Gamma_I(S')$ is the neighborhood of $S'$, the degrees of its vertices to $V' \setminus S'$ are bounded by 2, that induces a polynomial MIN SET COVER problem ([27]);

- in MIN INDEPENDENT DOMINATING SET, $S'$ is completed by the set $I \setminus \Gamma_I(S')$, where $\Gamma_I(S')$ is the set of neighbors of $S'$ that belong to $I$;

- in EXISTING DOMINATING CLIQUE, MIN DOMINATING CLIQUE (if any), MAX DOMINATING CLIQUE (if any) and MAX CLIQUE, $S'$ can eventually be completed by a single vertex of $\Gamma_I(S')$.

**Theorem 3.** MIN INDEPENDENT DOMINATING SET, EXISTING DOMINATING CLIQUE, MIN DOMINATING CLIQUE, MAX DOMINATING CLIQUE, MAX CLIQUE and MIN 3-DOMINATING SET can be solved in time $O*(2^\tau)$ using polynomial space.

## 4 Tailoring measure-and-conquer to graphs with maximum degree 3

Let us note that, as it is proved in [23], for any $\epsilon > 0$, there exists an integer $n_\epsilon$ such that the pathwidth of every (sub)cubic graph of order $n > n_\epsilon$ is at most $(1/6 + \epsilon)n$. Based upon the fact that there exists for MAX k-VERTEX COVER($w$) an $O*(2^w)$-time exponential space algorithm [34], and taking into account that in (sub)cubic graphs $w \le (1/6 + \epsilon)n$, the following corollary is immediately derived.
**Corollary 2.** MAX *k*- VERTEX COVER in graphs with maximum degree 3 can be solved in time $O*(2^{n/6}) = O*(1.123^n)$ using exponential space.

In this section we tailor the measure-and-conquer approach developed in Section 2 to graphs with $\Delta = 3$, in order to get an improved running-time algorithm for this case needing polynomial space. The following remark holds.

*Remark 1.* The graph can be cubic just once. When branching on a vertex *j* of maximum degree 3, we can always assume that it is adjacent to at least one vertex *h* that has already been selected or discarded. That is, either $d_h \le 2$, or $\alpha_h \ge 1$, that is $c_h \le 2$. Indeed, the situation where the graph is 3-regular occurs at most once (even in case of disconnection). Thus, we make only one "bad" branching (where every free vertex of maximum degree 3 is adjacent only to free vertices of degree 3). Such a branching may increase the global running time only by a constant factor.

**Lemma 1.** Any vertex *i* with $d_i \le 1$ and $\alpha_i = 0$ can be discarded w.l.o.g.

*Proof.* If $d_i = \alpha_i = 0$, then *i* can be obviously discarded. If $d_i = 1$ and $\alpha_i = 0$, then *i* is adjacent to another free vertex *h*. But then, if *h* is selected, *i* becomes of degree 0 and can be discarded. Alternatively, *h* is discarded, but then any solution with *i* but not *h* is dominated by that including *h* instead of *i*. ♦

**Lemma 2.** Any vertex *i* with $\alpha_i \ge 2$ and $d_i = 3$ can be selected w.l.o.g.

*Proof.* If $\alpha_i = 3$, then *i* can be obviously selected. If $d_i = 3$ and $\alpha_i = 2$, then *i* is adjacent to another free vertex *h*. But then, if *h* is discarded, we have $\alpha_i = 3$ and *i* can be selected. Alternatively, *h* is selected, but then any solution with *h* but not *i* is dominated by that including *i* instead of *h*. ♦

To solve MAX *k*- VERTEX COVER on graphs with $\Delta = 3$, consider the following algorithm, called MAXKVC-3.

Select *j* such that $c_j$ is maximum and branch according to the following exhaustive cases:

1. if $c_j = 3$, assume, w.l.o.g., that *j* is adjacent to *i*, *l*, *m* free vertices with $c_i \le 2$ (see in [14]) and $c_i \le c_l \le c_m$, and branch on *j* according to the following exhaustive subcases:

(a) $c_i = c_l = c_m = 1$

(b) $c_i = c_l = 1, c_m = 2$

(c) $c_i = c_l = 1, c_m = 3$

(d) $c_i = 1, c_l = c_m = 2$ with *l*, *m* adjacent

(e) $c_i = 1, c_l = c_m = 2$ with *l*, *m* non adjacent

(f) $c_i = 1, c_l = 2, c_m = 3$

(g) $c_i = c_l = 2, c_m = 3$ with *i*, *l* adjacent

(h) $c_i = c_l = 2, c_m = 3$ with *i*, *l* non adjacent

(i) $c_i = 2, c_l = c_m = 3$

2. else $c_j \le 2$ and MAXKVC-3 is polynomially solvable.
The following Theorem 4 holds in graphs with maximum degree 3 (due to space constraints, the proof is omitted; it can be found in [14]).

**Theorem 4.** *Algorithm MAXKVC-3 solves MAX k-VERTEX COVER on graphs with maximum degree 3 with running time $O^*(1.3339^n)$ and using polynomial space.*

# 5 Approximating MAX k-VERTEX COVER by moderately exponential algorithms

We now show how one can get approximation ratios non-achievable in polynomial time using moderately exponential algorithms with worst-case running times better than those required for an exact computation (see [4, 5] for more about this issue). Denote by $\text{opt}(G)$ the cardinality of an optimal solution for MAX k-VERTEX COVER in $G$ and by $m(G)$, the cardinality of an approximate solution. Our goal is to study the approximation ratio $m(G)/\text{opt}(G)$.

In what follows, we denote, as previously, by $K^*$ the optimal solution for MAX $k$- VERTEX COVER. Given a set $K$ of vertices, we denote by $C(K)$, the set of edges covered by $K$ (in other words, the value of a solution $K$ for MAX $k$- VERTEX COVER is $|C(K)|$; also, according to our previous notation, $\text{opt}(G) = |C(K^*)|$). We first prove the following easy lemma that will be used later.

**Lemma 3.** *For any $\lambda \in [0, 1]$, the subset $H^*$ of $\lambda k$ vertices of $K^*$ covering the largest amount of edges covered by $K^*$, covers at least $\lambda \text{opt}(G)$ edges.*

*Proof*. Indeed, if the $\lambda k$ “best” vertices of $K^*$ cover less than $\lambda \text{opt}(G)$ edges, then any disjoint union of $k/\lambda$ subsets of $K^*$, each of cardinality $\lambda k$ covers less than $\text{opt}(G)$ edges, a contradiction. ♦

Now, run the following algorithm, called APPROX in what follows:

1. fix some $\lambda \in [0, 1]$ and optimally solve MAX $\lambda k$- VERTEX COVER in $G$ (as previously, let $H^*$ be the optimal solution built and $C(H^*)$ be the edge-set covered by $H^*$);

2. remove $H^*$ and $C(H^*)$ from $G$ and approximately solve MAX $(1 - \lambda)k$- VERTEX COVER in the surviving graph (by some approximation algorithm); let $K'$ be the obtained solution;

3. output $K = H^* \cup K'$.

It is easy to see that if $T(p, k)$ is the running time of an optimal algorithm for MAX $k$- VERTEX COVER, where $p$ is some parameter of the input-graph $G$ (for instance, $n$, or $\tau$), then the complexity of APPROX is $T(p, \lambda k)$. Furthermore, APPROX requires polynomial space.

**Theorem 5.** *If $T(p, k)$ is the running time of an optimal algorithm for MAX $k$- VERTEX COVER, then, for any $\epsilon > 0$, MAX $k$- VERTEX COVER can be approximated within ratio $1 - \epsilon$ with worst-case running time $T(p, (1 + 2\sqrt{1 - 3\epsilon})k/3)$ and polynomial space.*
*Proof.* Denote by $K^*$ an optimal solution of MAX k- VERTEX COVER in $G$, by $G_2$ the induced subgraph $G[V \setminus H^*]$ of $G$, by $\text{opt}_{(1-\lambda)}(G_2)$, the value of an optimal for MAX $(1-\lambda)k$- VERTEX COVER in $G_2$. Suppose that $E'$ edges are common between $C(H^*)$ and $C(K^*)$. This means that $C(K^*) \setminus E'$ edges of $C(K^*)$ are in $G_2$ and are exclusively covered by the vertex-set $L^* = K^* \setminus H^*$ that belongs to $G_2$. Set $\ell^* = |L^*|$ and note that $\ell^* \le k$ and $\ell^* \ge (1-\lambda)k$.

According to Lemma 3, the $(1-\lambda)k$ “best” vertices of $L^*$ cover more than $(1-\lambda)|C(K^*) \setminus E'| = (1-\lambda)(\text{opt}(G) - |E'|)$ edges in $G_2$ and these vertices constitute a feasible solution for MAX $(1-\lambda)k$- VERTEX COVER in $G_2$. Hence:

$$ \text{opt}_{(1-\lambda)}(G_2) \ge (1-\lambda)(\text{opt}(G) - |E'|) \quad (9) $$

Taking into account (9), the fact that $K'$ in step 2 of APPROX has been computed by, say, a $\rho$-approximation algorithm and the fact that $|E'| \le |C(H^*)|$, we get:

$$ \begin{aligned} m(G) &= C(H^*) + C(K') \ge C(H^*) + \rho(1-\lambda)\text{opt}_{(1-\lambda)}(G_2) \\ &\ge C(H^*) + \rho(1-\lambda)(\text{opt}(G) - |E'|)C(H^*) \\ &\quad + \rho(1-\lambda)(\text{opt}(G) - C(H^*)) \\ &\ge (1-\rho(1-\lambda))C(H^*) + \rho(1-\lambda)\text{opt}(G) \end{aligned} \quad (10) $$

Using once more Lemma 3, $|C(H^*)| \ge \lambda \text{opt}(G)$, and combining it with (10), we get:

$$ \frac{m(G)}{\text{opt}(G)} \ge \rho(1-\lambda) + \lambda(1-\rho(1-\lambda)) \quad (11) $$

Setting $\rho = \frac{3}{4}$ in (11), in order to achieve an approximation ratio $m(G)/\text{opt}(G) = 1-\epsilon$, for some $\epsilon > 0$, we have to choose an $\lambda$ satisfying $\lambda = (1 + 2\sqrt{1-3\epsilon})/3$, that completes the proof of the theorem. ♦

**Corollary 3.** MAX k- VERTEX COVER can be approximated within ratio $1-\epsilon$ and with running time:

$$ \min \left\{ O^* \left( n^{\left(\frac{1+2\sqrt{1-3\epsilon}}{9}\right)} \right), O^* \left( \left(1+2\sqrt{\frac{\tau}{1-3\epsilon}}\right) \frac{k}{3} \right) \right\} $$

and polynomial space.

For Corollary 3, just observe that the running-times claimed for the first two entries are those needed to optimally solve MAX $\lambda k$- VERTEX COVER (the former due to [9] and the latter due to item 1 of Theorem 2). Note that the second term in the min expression in the corollary is an FPT approximation schema (with respect to parameter $\tau$). Observe also that for the cases where the time needed for solving MAX k- VERTEX COVER is given by the $c^k$ expression of item 1 of Theorem 2, this represents an improvement with respect to the FPT approximation schema of [32]. Note finally that the result of Theorem 5 is indeed a kind of reduction between moderately exponential (or parameterized) approximation and exact (or parameterized) computation for MAX k- VERTEX COVER
in the sense that exact solution on some subinstance of the problem derives an approximation for the whole instance.

Finally, let us close this section and the paper by some remarks on what kind of results can be expected in the area of (sub)exponential approximation. All the algorithms given in this section have exponential running time when we seek for a *constant* approximation ratio (unachievable in polynomial time). On the other hand, for several problems that are hard to approximate in polynomial time (like MAX INDEPENDENT SET, MIN COLORING, ...), subexponential time can be easily reached for ratios depending on the input-size (thus tending to $\infty$, for minimization problems, or to 0, for maximization problems). An interesting question is to determine, for these problems, if it is possible to devise a constant approximation algorithm working in subexponential time. An easy argument shows that this is not always the case. For instance, the existence of subexponential approximation algorithms (within ratio better than 4/3) is quite improbable for MIN COLORING since it would imply that 3-COLORING can be solved in subexponential time, contradicting so the "exponential time hypothesis" [29]. We conjecture that this is true for any constant ratio for MIN COLORING. Anyway, the possibility of devising subexponential approximation algorithms for NP-hard problems, achieving ratios forbidden in polynomial time or of showing impossibility of such algorithms is an interesting open question that deserves further investigation.

## References

1. Arnborg, S., Lagergren, J., Seese, D.: Easy problems for tree-decomposable graphs. J. Algorithms 12(2), 308–340 (1991)

2. Björklund, A., Husfeldt, T., Koivisto, M.: Set partitioning via inclusion-exclusion. SIAM J. Comput. 39(2), 546–563 (2009)

3. Bläser, M.: Computing small partial coverings. Inform. Process. Lett. 85(6), 327–331 (2003)

4. Bourgeois, N., Escoffier, B., Paschos, V.T.: Efficient approximation by "low-complexity" exponential algorithms. Cahier du LAMSADE 271, LAMSADE, Université Paris-Dauphine (December 2007), available at http://www.lamsade.dauphine.fr/cahiers/PDF/cahierLamsade271.pdf

5. Bourgeois, N., Escoffier, B., Paschos, V.T.: Efficient approximation of combinatorial problems by moderately exponential algorithms. In: Dehne, F., Gavrilova, M., Sack, J.R., Tóth, C. (eds.) Proc. Algorithms and Data Structures Symposium, WADS’09. Lecture Notes in Computer Science, vol. 5664, pp. 507–518. Springer-Verlag (2009)

6. Bourgeois, N., Escoffier, B., Paschos, V.T.: Efficient approximation of MIN COLORING by moderately exponential algorithms. Inform. Process. Lett. 109(16), 950–954 (2009)

7. Bourgeois, N., Escoffier, B., Paschos, V.T.: Efficient approximation of MIN SET COVER by moderately exponential algorithms. Theoret. Comput. Sci. 410(21-23), 2184–2195 (2009)

8. Brooks, R.L.: On coloring the nodes of a network. Math. Proc. Cambridge Philos. Soc. 37, 194–197 (1941)
9. Cai, L.: Parameter complexity of cardinality constrained optimization problems. The Computer Journal 51, 102–121 (2008)

10. Cai, L., Huang, X.: Fixed-parameter approximation: conceptual framework and approximability results. In: Bodlaender, H.L., Langston, M.A. (eds.) Proc. International Workshop on Parameterized and Exact Computation, IWPEC’06. Lecture Notes in Computer Science, vol. 4169, pp. 96–108. Springer-Verlag (2006)

11. Chen, J., Kanj, I., Jia, W.: Vertex cover: further observations and further improvements. J. Algorithms 41, 280–301 (2001)

12. Chen, J., Kanj, I., Xia, G.: Improved upper bounds for vertex cover. Theoret. Comput. Sci. 411(40-42), 3736–3756 (2010)

13. Courcelle, B.: The monadic second-order logic of graphs. i. recognizable sets of finite graphs. Information and Computation 85, 12–75 (1990)

14. Croce, F.D., Paschos, V.T.: On the MAX K- VERTEX COVER problem. Cahier du LAMSADE 307, LAMSADE, Université Paris-Dauphine (2011)

15. Cygan, M., Kowalik, L., Wykurz, M.: Exponential-time approximation of weighted set cover. Inform. Process. Lett. 109(16), 957–961 (2009)

16. Cygan, M., Pilipczuk, M.: Exact and approximate bandwidth. Theoret. Comput. Sci. 411(40–42), 3701–3713 (2010)

17. Downey, R.G., Fellows, M.R.: Parameterized complexity. Monographs in Computer Science, Springer, New York (1999)

18. Downey, R.G., Fellows, M.R., McCartin, C.: Parameterized approximation problems. In: Bodlaender, H.L., Langston, M.A. (eds.) Proc. International Workshop on Parameterized and Exact Computation, IWPEC’06. Lecture Notes in Computer Science, vol. 4169, pp. 121–129. Springer-Verlag (2006)

19. Feige, U., Langberg, M.: Approximation algorithms for maximization problems arising in graph partitioning. J. Algorithms 41(2), 174–211 (2001)

20. Fellows, M.R.: Towards fully multivariate algorithmics: some new results and directions in parameter ecology. In: Fiala, J., Kratochvíl, J., Miller, M. (eds.) Proc. International Workshop on Combinatorial Algorithms, IWOCA’09. Lecture Notes in Computer Science, vol. 5874, pp. 2–10. Springer-Verlag (2009)

21. Fellows, M.R., Lokshtanov, D., Misra, N., Rosamond, F.A., Saurabh, S.: Graph layout problems parameterized by vertex cover. In: Hong, S.H., Nagamochi, H., Fukunaga, T. (eds.) Proc. International Symposium on Algorithms and Computation, ISAAC’08. Lecture Notes in Computer Science, vol. 5369, pp. 294–305. Springer-Verlag (2008)

22. Fomin, F., Grandoni, F., Kratsch, D.: A measure & conquer approach for the analysis of exact algorithms. J. Assoc. Comput. Mach. 56(5), 1–32 (2009)

23. Fomin, F.V., Høie, K.: Pathwidth of cubic graphs and exact algorithms. Inform. Process. Lett. 97(5), 191–196 (2006)

24. Fomin, F.V., Lokshtanov, D., Raman, V., Saurabh, S.: Subexponential algorithms for partial cover problems. Inform. Process. Lett. 111(16), 814–818 (2011)

25. Fomin, F.V., Villanger, Y.: Treewidth computation and extremal combinatorics. In: Aceto, L., Damgaard, I., Goldberg, L.A., Halldórsson, M.M., Ingolfsdottir, A., Walukiewicz, I. (eds.) Proc. ICALP’08. pp. 210–221. No. 5125 in Lecture Notes in Computer Science, Springer-Verlag (2008)

26. Fürer, M., Gaspers, S., Kasiviswanathan, S.P.: An exponential time 2-approximation algorithm for bandwidth. In: Proc. International Workshop on Parameterized and Exact Computation, IWPEC’09. Lecture Notes in Computer Science, vol. 5917, pp. 173–184. Springer (2009)

27. Garey, M.R., Johnson, D.S.: Computers and intractability. A guide to the theory of NP-completeness. W. H. Freeman, San Francisco (1979)
28. Guo, J., Niedermeier, R., Wernicke, S.: Parameterized complexity of generalized vertex cover problems. In: Dehne, F., López-Ortiz, A., Sack, J. (eds.) Proc. International Workshop on Algorithms and Data Structures, WADS’05. Lecture Notes in Computer Science, vol. 3608, pp. 36–48. Springer-Verlag (2005)

29. Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. System Sci. 63(4), 512–530 (2001)

30. Jäger, G., Srivastav, A.: Improved approximation algorithms for maximum graph partitioning problems. J. Comb. Optim. 10(2), 133–167 (2005)

31. Kneis, J., Langer, A., Rossmanith, P.: Improved upper bounds for partial vertex cover. In: Broersma, H., Erlebach, T., Friedetzky, T., Paulusma, D. (eds.) Proc. International Workshop on Graph Theoretical Concepts in Computer Science, WG’08. Lecture Notes in Computer Science, vol. 5344, pp. 240–251. Springer-Verlag (2008)

32. Marx, D.: Parameterized complexity and approximation algorithms. The Computer Journal 51(1), 60–78 (2008)

33. Marx, D.: Fixed parameter algorithms. Open lectures for PhD students in computer science (January 2010)

34. Moser, H.: Exact algorithms for generalizations of vertex cover. Master’s thesis, Fakultät für Mathematik und Informatik, Friedrich-Schiller-Universität Jena (2005)

35. Nešetřil, J., Poljak, S.: On the complexity of the subgraph problem. Comment. Math. Univ. Carolinae pp. 415–419 (1985)

36. Niedermeier, R., Rossmanith, P.: On efficient fixed-parameter algorithms for weighted vertex cover. J. Algorithms 47(2), 63–77 (2003)

37. Praveen, M.: Logic, Courcelle’s theorem and application. IMPECS School on Parameterized and Exact Computation (December 2010)