2
$\begingroup$

I have an algorithm that solves the Vertex Cover problem. The algorithm is

Repeat while there is an edge:

Arbitrarily pick an uncovered edge $e = uv$ and add $u$ and $v$ to the solution. Delete $u$ and $v$ from the graph.

I know this strategy is a 2-approximation to Vertex Cover and that its worst example is the complete bipartite graph $K_{n,n}$. In this graph, the algorithm will return a vertex cover of size $2n$ whereas the optimal solution is of size $n$.

Question: Does there exist a graph with Minimum Vertex Cover of size 10 where this strategy finds a minimum vertex cover?

Improve this question
$\endgroup$
4
  • 3
    $\begingroup$ The performance you mention on complete bipartite graphs is at odds with the stated approximation ratio. $\endgroup$
    – Yuval Filmus
    Dec 21, 2018 at 19:13
  • 2
    $\begingroup$ A good example for this algorithm is a matching. $\endgroup$
    – Yuval Filmus
    Dec 21, 2018 at 19:13
  • $\begingroup$ ohhh can you give any worst case example? $\endgroup$
    – Naila Akbar
    Dec 21, 2018 at 19:20
  • 1
    $\begingroup$ @YuvalFilmus If I understand the question as well as your suggestion, your suggestion ($10K_2$) gives a worst case, and not a best case. It seems that OP is looking for examples where the approximation algorithms actually gives the optimum. $\endgroup$
    – Pål GD
    Dec 22, 2018 at 12:40

1 Answer 1

Reset to default
4
$\begingroup$

You ask for a graph where your (nondeterministic) algorithm gives the optimal solution even in the worst case. We're looking for a set of vertices that cover all edges. The difficulty with your algorithm is not only that it could pick the edges in an "inconvenient" order, but also that it adds both vertices belonging to the edge, which is suboptimal in most cases (since adding one of the vertices already covers the edge).

An example where your algorithm does always find the optimal solution of size 10, is the graph below. If you meant the problem the other way around (cover all vertices), the same graph applies.

The graph 5K3---the disjoint union of five triangles

Improve this answer
$\endgroup$
2
  • $\begingroup$ Also known as $5K_3$. $\endgroup$
    – Pål GD
    Dec 22, 2018 at 12:41
  • $\begingroup$ Thank you for you solution. This vertex cover still confuses me.. but thanks for the explanation $\endgroup$
    – Naila Akbar
    Dec 23, 2018 at 20:11

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.