4
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – Neal Young
    Feb 26 at 21:23
  • $\begingroup$ Yes, I don't understand the downvotes either. It's not homework and I showed my effort. $\endgroup$
    – reservoir
    Feb 26 at 22:35
  • 2
    $\begingroup$ This is known as the partial vertex cover problem and is well-studied in the literature. $\endgroup$ Mar 1 at 16:21
  • $\begingroup$ 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. $\endgroup$
    – daniello
    Mar 7 at 5:45

2 Answers 2

2
$\begingroup$

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$

$\endgroup$
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.