1
$\begingroup$

I have the following randomized-algorithm for the vertex cover problem. Let $B_0$ be the output set:

Fix some order $e_1, e_2,...,e_m$ over all edges in the edge set E of G, and set $B_0=∅$.

Add to $B_0$ all isolated vertices, i.e. the ones without any incident edges.

For every edge $e$ in $e_1,e_2,...,e_m$ if both endpoints of e are not contained in $B_0$, then flip a fair coin deciding which of the endpoints to choose, and add this endpoint to $B_0$.

I have already proved that this algorithm has $E[|B_0|] \le 2|OPT|$.

Now I don't know how to apply the method of conditional expectations (defined here) to derandomize the algorithm in order to show that we can't obtain an efficient deterministic version and that gives the same result of the expected value found previously. Can you show me to do this?

Improve this question
$\endgroup$
8
  • $\begingroup$ Sorry but I didn't understand your first point. For the second one, yes, I meant that $\endgroup$
    – bruce_springsteen
    Jan 1, 2020 at 16:56
  • $\begingroup$ (i) Don't add isolated vertices. (If the graph has no edges, OPT=0 as the empty set is a vertex cover.) (ii) Rather than "if both endpoints of e are not contained in $B_0$", do you mean "if neither endpoint of e is contained in $B_0$"? (iii) With those changes, the alg. is a special case of Alg. 3 in this paper. A linear-time deterministic variant is the standard 2-approx alg (which adds both endpoints of $e$ if neither is in $B_0$). $\endgroup$
    – Neal Young
    Jan 1, 2020 at 16:58
  • $\begingroup$ Can you add a sketch of your proof that $E[|B_0|] \le 2 |OPT|$, so we can check it? Also applying the method of conditional probabilities requires knowing the particulars of the proof. $\endgroup$
    – Neal Young
    Jan 1, 2020 at 17:35
  • $\begingroup$ Here it is comp.nus.edu.sg/~stevenha/cs4234/lectures/01.VertexCover.pdf I want to apply the method of conditional expectations to show that it gives the same result but it has less efficiency than randomized one $\endgroup$
    – bruce_springsteen
    Jan 1, 2020 at 17:59
  • 2
    $\begingroup$ That proof in the notes linked to in the comment (Section 5.2) has a technical problem (a gap). $E'$ is itself a random variable, but the top of page 11 writes $E[\sum_{e\in E'} X_e] = \sum_{e\in E'} E[X_e]$. But the sum on the right is a random variable, since $E'$ is, so this equation makes a category error. Also note that $E'$ is not independent of the $X_e$'s, so some care is needed. The proof should probably use something like Wald's equation (or a more careful accounting of conditioning) to fix the issue. $\endgroup$
    – Neal Young
    Jan 2, 2020 at 1:11

1 Answer 1

Reset to default
1
$\begingroup$

First, let us repeat the analysis of the algorithm.

Fix some optimal vertex cover OPT, with cost $O$.

Let $S$ be the cost of the vertex cover produced by the algorithm.

Let $A_e$ be the indicator for the event "when edge $e$ was considered, the algorithm added a vertex belonging to OPT", and let $A = \sum_e A_e$.

Let $B_e$ be the indicator for the event "when edge $e$ was considered, the algorithm added a vertex not belonging to OPT", and let $B = \sum_e B_e$.

Thus $S = A+B$ and $A \leq O$.

The idea of the analysis is that $\Pr[B_e] \leq \Pr[A_e]$. To see this, consider what happens when vertex $e$ is considered. If $e$ is already covered by vertices already chosen, then $A_e = B_e = 0$. If both endpoints of $e$ belong to OPT, then $A_e = 1$ and $B_e = 0$. Otherwise, $\Pr[A_e] = \Pr[B_e] = 1/2$. In all cases, $\Pr[B_e] \leq \Pr[A_e]$.

Since $\Pr[B_e] \leq \Pr[A_e]$, we have $\mathbb{E}[B] \leq \mathbb{E}[A]$. Therefore $$ \mathbb{E}[S] = \mathbb{E}[A+B] \leq 2\mathbb{E}[A] \leq 2O. $$

How would we apply the method of conditional expectations? Here are two options:

  1. Given the choice of which endpoint is taken, compute the expected value of $S$. If $z \in \{x,y\}$ was chosen, then we remove all edges adjacent to $z$, and then run the algorithm as usual. This reduces the problem to computing $\mathbb{E}[S]$, which is the expected number of edges which are not covered when their time comes. It's not so clear how to compute $\mathbb{E}[S]$.

  2. The same, but instead of computed $\mathbb{E}[S]$ exactly, compute an approximation which is good enough to obtain a 2-approximation. Let $O_z$ be the optimum solution after removing all edges adjacent to $z$. Then $$ \mathbb{E}[S \mid x] \leq 1 + 2O_x, \quad \mathbb{E}[S \mid y] \leq 1 + 2O_y. $$ If $x$ belongs to OPT then $O_x = O-1$, and otherwise $O_x \leq O$. Thus the average of both bounds is at most $$ \frac{1+2(O-1)+1+2O}{2} = 2O, $$ since at least one of $x,y$ belongs to OPT. Therefore, if we choose the vertex that minimizes $O_x,O_y$, then the resulting algorithm will produce a 2-approximation. Unfortunately, it's not clear how to compute $O_x,O_y$ (indeed, this ought to be hard).

In summary, it's not so clear how to apply the method of conditional expectations.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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