Maximum Vertex Cover

Question

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.

Answer 1

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 2

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''.

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}$.