<p>Recall that <span class="math-container">$L=\max_{S\subseteq V : |S|=k} \sum_{v\in S} d(v) / 2$</span>, where <span class="math-container">$d(v)$</span> is the degree of vertex <span class="math-container">$v$</span>, and that, as observed in the post,
any set of <span class="math-container">$k$</span> vertices covers at most <span class="math-container">$2L$</span> edges.</p>
<p><strong>Theorem 1.</strong> <em>The greedy algorithm covers at least <span class="math-container">$L$</span> edges
(so greedy gives a 2-approximation).</em></p>
<p><em>Proof of Theorem 1.</em>
Following the post, let <span class="math-container">$x_1, x_2, \ldots, x_k$</span> be the sequence of <span class="math-container">$k$</span> vertices chosen by greedy.
For <span class="math-container">$t\in[k]$</span> let <span class="math-container">$X_t = \{x_1, x_2, \ldots, x_t\}$</span> denote the first <span class="math-container">$t$</span> vertices chosen by greedy.
Let <span class="math-container">$S=\{s_1, s_2, \ldots, s_k\}$</span> be a set achieving the maximum in the definition of <span class="math-container">$L$</span>, ordered so that, for each <span class="math-container">$t\in[k]$</span>, at the start of greedy's <span class="math-container">$t$</span>th iteration, it has not yet chosen <span class="math-container">$s_t$</span> (that is, <span class="math-container">$s_t\not\in X_{t-1}$</span>).</p>
<p>At the start of that iteration, the number of edges out of <span class="math-container">$s_t$</span> that are not yet covered by greedy (i.e. by <span class="math-container">$X_{t-1}$</span>) is
<span class="math-container">$\textstyle d(s_t) - d(s_t, X_{t-1}).$</span>
By the greedy choice of <span class="math-container">$x_t$</span>, then, the number of edges that greedy covers by choosing <span class="math-container">$x_t$</span> in iteration <span class="math-container">$t$</span> is at least this, that is,
<span class="math-container">$$d(x_t, V\setminus X_{t-1}\})
\ge d(s_t) - d(s_t, X_{t-1}).$$</span></p>
<p>Rearranging and summing over <span class="math-container">$t\in[k]$</span>,
<span class="math-container">$$\begin{align}
2L = \sum_{t=1}^k d(s_t) &amp;{}\le \sum_{t=1}^k d(x_t, V\setminus X_{t-1}) + \sum_{t=1}^k d(s_t, X_{t-1}) \\
&amp; = \Big(\sum_{t=1}^k d(x_t, V\setminus X_{t-1})\Big) + |\{(x_i, s_j) \in E : i &lt; j\}|
\\
&amp; = \sum_{t=1}^k \Big(d(x_t, V\setminus X_{t-1}) + d(x_t, \{s_{t+1}, \ldots s_k\})\Big)
\\
&amp; \le \sum_{t=1}^k 2\, d(x_t, V\setminus X_{t-1}).
\end{align}
$$</span>
The last step follows from <span class="math-container">$\{s_{t+1}, \ldots, s_k\}\subseteq V\setminus X_{t-1}$</span> (which follows from the ordering of <span class="math-container">$S$</span>).</p>
<p>The right-hand side above is twice the number of edges covered by the greedy algorithm.<span class="math-container">$~~~~\Box$</span></p>

CC BY-SA 4.0
2022-02-28T14:52:29.413Z
2022-02-28T14:52:29.413Z
Neal Young
<p>Thanks @Neal Young for a nice solution. I already accepted your answer. I just wanted to point out, for future readers, where exactly I ''failed''.</p>
<p>So, what I had already shown (using @Neil's notations) was that:</p>
<p><span class="math-container">$ \displaystyle \begin{equation} 
\sum_{t=1}^k d(x_t,V \setminus X_{t-1}) \geq 2 \cdot L - \sum_{t=1}^k d(s_t,X_{t-1})
\end{equation} $</span></p>
<p>And then I was <em>hoping</em> to prove that:</p>
<p><span class="math-container">$ \displaystyle \begin{equation} \sum_{t=1}^k d(s_t,X_{t-1}) \leq L
\end{equation}$</span></p>
<p>which indeed would finish the proof. I got stuck and the trick to get out of it is to notice the following: it also suffices to show that:</p>
<p><span class="math-container">$ \displaystyle \begin{equation} \sum_{t=1}^k d(s_t,X_{t-1}) \leq \sum_{t=1}^k d(x_t,V \setminus X_{t-1})
\end{equation}$</span></p>
<p>and this is a weaker statement which follows easily. @Neil implicitly proved this, and I reproduce the argument:</p>
<p><span class="math-container">$ \displaystyle \begin{align} \sum_{t=1}^k d(s_t,X_{t-1}) &amp;= |\{ (x_i,s_j) \in E : i &lt; j \}| = \sum_{t=1}^k d(x_t,\{s_{t+1},\dots,s_k\}) \leq \\
&amp;\leq \sum_{t=1}^k d(x_t,V \setminus X_{t-1}),
\end{align}$</span></p>
<p>where indeed the last inequality follows from <span class="math-container">$\{s_{t+1},\dots,s_k\} \subseteq V \setminus X_{t-1}$</span>.</p>

CC BY-SA 4.0
2022-03-01T10:36:48.087Z
2022-03-01T10:36:48.087Z
reservoir
<p>I recently encountered the following exam problem: Given an undirected graph <span class="math-container">$G := (V,E)$</span> and a natural number <span class="math-container">$k \geq 1$</span>, we want to cover as many edges as possible using exactly <span class="math-container">$k$</span> vertices. Consider the following Greedy approach: at each step <span class="math-container">$i \in \{1,\dots,k\}$</span>, add to the partial solution the vertex that covers the most <em>new</em> edges.</p>
<p>To show that this is a 2-approximation, the following hint is given: show that the Greedy solution covers at least <span class="math-container">$ 1/2 \cdot \max_{S \subseteq V, |S| = k} \text{deg}(v)$</span> edges.</p>
<p>I tried to show this, but failed. Here is my approach:</p>
<p>Assume our algorithm added the vertices <span class="math-container">$ x_1, x_2, \dots, x_k \in V $</span> in this order to its solution. Let <span class="math-container">$ s_1, s_2, \dots, s_k \in V $</span> be any <span class="math-container">$ k $</span> vertices. It suffices to show that the cost of our solution covers at least <span class="math-container">$ L := \sum_{i=1}^k \text{deg}(s_i)/2 $</span> vertices.</p>
<p>We can reorder <span class="math-container">$ s_1,\dots,s_k $</span>, such that <span class="math-container">$ s_i \notin \{ x_1,\dots,x_{i-1} \} $</span> for any <span class="math-container">$ i $</span>.</p>
<p>Now note that each <span class="math-container">$x_i$</span> is chosen with the property that:</p>
<p><span class="math-container">$ \begin{equation} \text{deg}(x_i) - |E(\{x_i\},\{x_1,\dots,x_{i-1}\})| \geq \text{deg}(v) - |E(\{v\},\{x_1,\dots,x_{i-1}\})|, \  \\ \forall v \in V \setminus \{x_1,\dots,x_{i-1}\} \end{equation} $</span></p>
<p>By the special ordering we have for <span class="math-container">$ s_1,\dots,s_k $</span>, this implies:</p>
<p><span class="math-container">$ \begin{equation} \text{deg}(x_i) - |E(\{x_i\},\{x_1,\dots,x_{i-1}\})| \geq \text{deg}(s_i) - |E(\{s_i\},\{x_1,\dots,x_{i-1}\})|\end{equation} $</span></p>
<p>We obtain:</p>
<p><span class="math-container">$ \begin{align} 
&amp;\sum_{i=1}^k (\text{deg}(x_i) - |E(\{x_i\},\{x_1,\dots,x_{i-1}\})|) \geq \\ 
&amp;\sum_{i=1}^k (\text{deg}(s_i) - |E(\{s_i\},\{x_1,\dots,x_{i-1}\})|) = \\ 
&amp; 2 \cdot L - \sum_{i=1}^k |E(\{s_i\},\{x_1,\dots,x_{i-1}\})| 
\end{align} $</span></p>
<p>where the LHS is the number of edges covered by the Greedy algorithm. So I'd like to show that:</p>
<p><span class="math-container">$ \begin{equation} \sum_{i=1}^k |E(\{s_i\},\{x_1,\dots,x_{i-1}\})| \leq L \end{equation} $</span></p>
<p>And I'm stuck here.</p>
<p>I am curious how the lower bound of <span class="math-container">$ 1/2 \cdot \max_{S \subseteq V, |S| = k} \text{deg}(v)$</span> can be shown, either by continuing my arguments or by an entirely different approach.</p>

CC BY-SA 4.0
2022-02-26T21:23:06.653Z
I think it's a nice question.   Not sure why you got downvoted.  I suppose some may think homework / exam / study questions are better suited to cs.se, but this one seems challenging enough.
Neal Young
CC BY-SA 4.0
2022-02-26T22:35:37.423Z
Yes, I don't understand the downvotes either. It's not homework and I showed my effort.
reservoir
CC BY-SA 4.0
2022-03-01T16:21:03.980Z
This is known as the partial vertex cover problem and is well-studied in the literature.
Chandra Chekuri
CC BY-SA 4.0
2022-03-07T05:45:44.860Z
Here is the intuition for the factor 2 bound: every edge has 2 endpoints. Greedy covers the maximum number of edge endpoints, but ignores that two edge endpoints can correspond to the same edge. The number of covered endpoints is equal to the number of covered edges up to a factor 2, hence this is a 2-approximation.
daniello
<approximation-algorithms><greedy-algorithms><vertex-cover>
Maximum Vertex Cover
reservoir
# Maximum Vertex Cover

(Asked by: username_0 on 2022-02-26)

I recently encountered the following exam problem: Given an undirected graph $G := (V,E)$ and a natural number $k \geq 1$, we want to cover as many edges as possible using exactly $k$ vertices. Consider the following Greedy approach: at each step $i \in \{1,\dots,k\}$, add to the partial solution the vertex that covers the most *new* edges.

To show that this is a 2-approximation, the following hint is given: show that the Greedy solution covers at least $ 1/2 \cdot \max\_{S \subseteq V, |S| = k} \text{deg}(v)$ edges.

I tried to show this, but failed. Here is my approach:

Assume our algorithm added the vertices $ x\_1, x\_2, \dots, x\_k \in V $ in this order to its solution. Let $ s\_1, s\_2, \dots, s\_k \in V $ be any $ k $ vertices. It suffices to show that the cost of our solution covers at least $ L := \sum\_{i=1}^k \text{deg}(s\_i)/2 $ vertices.

We can reorder $ s\_1,\dots,s\_k $, such that $ s\_i \notin \{ x\_1,\dots,x\_{i-1} \} $ for any $ i $.

Now note that each $x\_i$ is chosen with the property that:

$ \begin{equation} \text{deg}(x\_i) - |E(\{x\_i\},\{x\_1,\dots,x\_{i-1}\})| \geq \text{deg}(v) - |E(\{v\},\{x\_1,\dots,x\_{i-1}\})|, \ \\ \forall v \in V \setminus \{x\_1,\dots,x\_{i-1}\} \end{equation} $

By the special ordering we have for $ s\_1,\dots,s\_k $, this implies:

$ \begin{equation} \text{deg}(x\_i) - |E(\{x\_i\},\{x\_1,\dots,x\_{i-1}\})| \geq \text{deg}(s\_i) - |E(\{s\_i\},\{x\_1,\dots,x\_{i-1}\})|\end{equation} $

We obtain:

$ \begin{align}
&\sum\_{i=1}^k (\text{deg}(x\_i) - |E(\{x\_i\},\{x\_1,\dots,x\_{i-1}\})|) \geq \\
&\sum\_{i=1}^k (\text{deg}(s\_i) - |E(\{s\_i\},\{x\_1,\dots,x\_{i-1}\})|) = \\
& 2 \cdot L - \sum\_{i=1}^k |E(\{s\_i\},\{x\_1,\dots,x\_{i-1}\})|
\end{align} $

where the LHS is the number of edges covered by the Greedy algorithm. So I'd like to show that:

$ \begin{equation} \sum\_{i=1}^k |E(\{s\_i\},\{x\_1,\dots,x\_{i-1}\})| \leq L \end{equation} $

And I'm stuck here.

I am curious how the lower bound of $ 1/2 \cdot \max\_{S \subseteq V, |S| = k} \text{deg}(v)$ can be shown, either by continuing my arguments or by an entirely different approach.

**Tags:** approximation-algorithms, greedy-algorithms, vertex-cover

> **Comments:**
> **username_1**: I think it's a nice question.   Not sure why you got downvoted.  I suppose some may think homework / exam / study questions are better suited to cs.se, but this one seems challenging enough.  
> **username_0**: Yes, I don't understand the downvotes either. It's not homework and I showed my effort.  
> **username_2**: This is known as the partial vertex cover problem and is well-studied in the literature.  
> **username_3**: Here is the intuition for the factor 2 bound: every edge has 2 endpoints. Greedy covers the maximum number of edge endpoints, but ignores that two edge endpoints can correspond to the same edge. The number of covered endpoints is equal to the number of covered edges up to a factor 2, hence this is a 2-approximation.  

---

## 2 answers

### Answer by username_1 on 2022-02-28. Score: 2 | Accepted answer

Recall that $L=\max\_{S\subseteq V : |S|=k} \sum\_{v\in S} d(v) / 2$, where $d(v)$ is the degree of vertex $v$, and that, as observed in the post,
any set of $k$ vertices covers at most $2L$ edges.

**Theorem 1.** *The greedy algorithm covers at least $L$ edges
(so greedy gives a 2-approximation).*

*Proof of Theorem 1.*
Following the post, let $x\_1, x\_2, \ldots, x\_k$ be the sequence of $k$ vertices chosen by greedy.
For $t\in[k]$ let $X\_t = \{x\_1, x\_2, \ldots, x\_t\}$ denote the first $t$ vertices chosen by greedy.
Let $S=\{s\_1, s\_2, \ldots, s\_k\}$ be a set achieving the maximum in the definition of $L$, ordered so that, for each $t\in[k]$, at the start of greedy's $t$th iteration, it has not yet chosen $s\_t$ (that is, $s\_t\not\in X\_{t-1}$).

At the start of that iteration, the number of edges out of $s\_t$ that are not yet covered by greedy (i.e. by $X\_{t-1}$) is
$\textstyle d(s\_t) - d(s\_t, X\_{t-1}).$
By the greedy choice of $x\_t$, then, the number of edges that greedy covers by choosing $x\_t$ in iteration $t$ is at least this, that is,
$$d(x\_t, V\setminus X\_{t-1}\})
\ge d(s\_t) - d(s\_t, X\_{t-1}).$$

Rearranging and summing over $t\in[k]$,
$$\begin{align}
2L = \sum\_{t=1}^k d(s\_t) &{}\le \sum\_{t=1}^k d(x\_t, V\setminus X\_{t-1}) + \sum\_{t=1}^k d(s\_t, X\_{t-1}) \\
& = \Big(\sum\_{t=1}^k d(x\_t, V\setminus X\_{t-1})\Big) + |\{(x\_i, s\_j) \in E : i < j\}|
\\
& = \sum\_{t=1}^k \Big(d(x\_t, V\setminus X\_{t-1}) + d(x\_t, \{s\_{t+1}, \ldots s\_k\})\Big)
\\
& \le \sum\_{t=1}^k 2\, d(x\_t, V\setminus X\_{t-1}).
\end{align}
$$
The last step follows from $\{s\_{t+1}, \ldots, s\_k\}\subseteq V\setminus X\_{t-1}$ (which follows from the ordering of $S$).

The right-hand side above is twice the number of edges covered by the greedy algorithm.$~~~~\Box$


---

### Answer by username_0 on 2022-03-01. Score: 2

Thanks @username_1 for a nice solution. I already accepted your answer. I just wanted to point out, for future readers, where exactly I ''failed''.

So, what I had already shown (using @Neil's notations) was that:

$ \displaystyle \begin{equation}
\sum\_{t=1}^k d(x\_t,V \setminus X\_{t-1}) \geq 2 \cdot L - \sum\_{t=1}^k d(s\_t,X\_{t-1})
\end{equation} $

And then I was *hoping* to prove that:

$ \displaystyle \begin{equation} \sum\_{t=1}^k d(s\_t,X\_{t-1}) \leq L
\end{equation}$

which indeed would finish the proof. I got stuck and the trick to get out of it is to notice the following: it also suffices to show that:

$ \displaystyle \begin{equation} \sum\_{t=1}^k d(s\_t,X\_{t-1}) \leq \sum\_{t=1}^k d(x\_t,V \setminus X\_{t-1})
\end{equation}$

and this is a weaker statement which follows easily. @Neil implicitly proved this, and I reproduce the argument:

$ \displaystyle \begin{align} \sum\_{t=1}^k d(s\_t,X\_{t-1}) &= |\{ (x\_i,s\_j) \in E : i < j \}| = \sum\_{t=1}^k d(x\_t,\{s\_{t+1},\dots,s\_k\}) \leq \\
&\leq \sum\_{t=1}^k d(x\_t,V \setminus X\_{t-1}),
\end{align}$

where indeed the last inequality follows from $\{s\_{t+1},\dots,s\_k\} \subseteq V \setminus X\_{t-1}$.


---

