8
$\begingroup$

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

Improve this question
$\endgroup$
4
  • 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$
    – Narek Bojikian
    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

0

Reset to default

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.