Consider the following randomized approximation algorithm of vertex cover:

  • Input: A graph G = (V, E).
  • Output: A set $C_G \subseteq V$ a vertex cover of $G$.

The algorithm:

  1. Set $C_G := \emptyset$.
  2. For each edge $e$, in some arbitrary order:
    1. If $e$ is covered, skip it and continue to the next iteration of the loop.
    2. Let $e=\{u,v\}$. Choose an endpoint $w \in \{u, v\}$ uniformly at random.
    3. Add $w$ to $C_G$.

Let $C_G$ be the solution computed by this algorithm for a given graph $G$, and $\operatorname{OPT}_G$ an optimal solution. I found a proof (see link), that $$\mathbb{E}[|C_G|] \leq 2 \mathbb{E}[|\operatorname{OPT}_G|].$$

I have been trying however, to find a way to compute $\mathbb{E}[|C_G|]$ for a given graph $G = (V, E)$. The best I could come up with, is a dynamic programming solution over all subsets of the vertices, i.e. for each $S \subseteq 2^V$, we have to computed $C_{G[S]}$. This solution has $O^*(2^n)$ space and time complexity.

Is it possible to compute the expected value of $|C_G|$ in polynomial time or is it possible to prove that it is NP-hard to compute $\mathbb{E}[|C_G|]$?

  • 1
    $\begingroup$ Just a quick note that the proof you linked to has a technical error (a gap). See comments on cs.stackexchange.com/questions/119065/… for more details. $\endgroup$
    – Neal Young
    Jan 2, 2020 at 18:07
  • 2
    $\begingroup$ One possible approach: numerical precision. Show that (for arbitrarily large n) there is a graph with n vertices where the expectation requires exponentially many bits to represent exactly. $\endgroup$
    – Neal Young
    Jan 3, 2020 at 17:40
  • $\begingroup$ @NealYoung thanks, this seems to answer my question. I was wondering however, about the question in this link. It seems that a machine that outputs the expectation rounded up to the next integer suffices for this specific case cs.stackexchange.com/questions/119065/… $\endgroup$ Jan 3, 2020 at 19:04
  • 1
    $\begingroup$ That's an interesting observation. Note: I don't know whether the suggestion in my other comment works or not, it was just a possible line of attack. $\endgroup$
    – Neal Young
    Jan 3, 2020 at 20:00


Your Answer

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