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 = \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|$?

Improve this question
$\endgroup$
2
  • $\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, 2020 at 20:32
  • $\begingroup$ Discussion of this algorithm continues here: cs.stackexchange.com/questions/119065/… $\endgroup$
    – Neal Young
    Jan 3, 2020 at 20:35

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • 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, 2019 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, 2019 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, 2019 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, 2019 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, 2019 at 19:26

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.