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 = \emptyset$.
  • 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$ not contained in $B_0$, then
    • flip a fair coin deciding which of the endpoints to choose, and add this endpoint to $B_0$.

How can I prove that, for every constant $c \geq 1$, the algorithm might produce a $B_0$ with $|B_0 | \ge c|OPT|$?

  • $\begingroup$ Just take any graph with $\lceil c \rceil$ vertices and no edges. Then your algorithm produces a solution of size $\lceil c\rceil$ but $|OPT|=0$. $\endgroup$ – Neal Young Jan 3 '20 at 20:32
  • $\begingroup$ Discussion of this algorithm continues here: cs.stackexchange.com/questions/119065/… $\endgroup$ – Neal Young Jan 3 '20 at 20:35

Fix a star graph of $c + 1$ vertices. A star graph is a vertex connected to all other vertices in the graph (a universal vertex called the center), and all other vertices are pairwise not adjacent. Here is a visual example. $c$ is the center of the star.

A visual example of a star graph. In red is the center of the graph.

Now an optimal solution is to pack the center of the star. The size of this solution is equal to 1. For each edge, suppose our algorithm packs the other end of the edge (the non-universal vertex), then we need to pack all vertices of the graph except for the center and hence, we need to pack $c$ different vertices. In total we get $|B_0| = C |OPT|$ for any arbitrary but fixed value of $c$.

Note A simple modification of the algorithm yields a derandomized approximation algorithm with answer size at most twice as large as the optimum. It goes as follows: if both endpoints of the edge are not in $B_0$, then add both endpoints to $B_0$ and iterate.

The reason why this works is simple. The edges, who get their endpoints added for a maximal matching and hence, we add twice the number of vertices in a maximal matching to the cover. Note that the size of a matching in a graph is a lower-bound on the size of a minimum vertex cover and hence, we add at most twice many vertices as the size of the minimum vertex cover.

  • 1
    $\begingroup$ Thank you so much! And could you explain me why it would be hard to derive an efficient and deterministic version of this algorithm by using the method of conditional expectation? $\endgroup$ – bruce_springsteen Dec 30 '19 at 15:39
  • $\begingroup$ I am not sure if I understood the question right, but I updated the answer with a not at the end. Does it help? $\endgroup$ – narek Bojikian Dec 30 '19 at 16:22
  • 1
    $\begingroup$ Well yes, that is a deterministic approach , but I want to prove that this, google.com/url?sa=t&source=web&rct=j&url=http://…, applied to my case, gives too a 2-approx. Some help? $\endgroup$ – bruce_springsteen Dec 30 '19 at 17:56
  • $\begingroup$ But in the method of the conditional expectation, you already have a good expected value and you are looking for a derandomized algorithm that always outputs a good value with an increase in the running time. In your algorithm, you did not prove any bound on the expected value in order to use it for a good derandomization. $\endgroup$ – narek Bojikian Dec 30 '19 at 18:33
  • 1
    $\begingroup$ Yes, you're right indees. I forgot to say that I have already proved that the expected value for the algorithm is no greater than twice the optimal value. Given this, how can I apply the method of the conditional expectation and show that it gives the same result? $\endgroup$ – bruce_springsteen Dec 30 '19 at 19:26

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.