# Compute the expected size of an approximation of vertex cover

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|]$$?

• 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. – Neal Young Jan 2 '20 at 18:07
• 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. – Neal Young Jan 3 '20 at 17:40
• @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/… – narek Bojikian Jan 3 '20 at 19:04
• 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. – Neal Young Jan 3 '20 at 20:00