0
$\begingroup$

Question: Show that for each even n, there exists a graph with n vertices, such that the ALG(algorithm) returns a vertex cover which is exactly twice the size of minimum vertex cover.

Define ALG: simple 2-approximation deterministic algorithm for the vertex cover problem in an unweighted graph. Output of ALG: vertex cover which is at most twice the size of minimum vertex cover.

How will we show that?

My struggle: I tried to solve this in the following way(below), BUT I'm not sure that my proof is correct, meaning that, will there always exist a bipartite graph when n is even?

How I will approach the proof: We’ll show that maximum matching in a graph is equal to the size of minimum vertex cover, and then we’ll show that the output of ALG is exactly twice the size of maximum matching, and thus is twice the size of minimum vertex cover. And thus, there always exists a bi-partite graph which is divided to two distinct sets of size n/2 which contains a minimum vertex cover that is exactly half the vertex cover.

My proof:

Step 1: There always exists a graph, which is bipartite, that maximum matching in it is equal to the size of minimum vertex cover, in that graph. Proof: Kőnig's theorem states that, in any bipartite graph, the number of edges in a maximum matching is equal to the number of vertices in a minimum vertex cover.

Step 2: A matching in graph G is a set of edges such that no two edges share a common vertex. A maximal matching M is a matching such that we cannot add any of the remaining edge into M while maintaining the matching constraint, in other word, if we add any of the edge then M will not be a valid matching anymore. Note that maximal matching is different with maximum matching. Maximum matching deals with the largest possible matching set. So, maximum matching is a maximal matching, but the converse is not necessarily true (see figure below for clarity). enter image description here

Figure 4 corresponds to a maximum matching (we cannot do better than 3), but both Figure 4 and Figure 5 are valid maximal matchings (we cannot add any of the remaining edge to the set while not violating the matching condition).

We can conclude that is it’s maximum matching is ALWAYS maximal matching. (vice versa not always true).

Define C: the output of ALG – which is the vertex cover set of the “2-approx for minimum vertex cover problem”.

Let’s add also the ALG algorithm for more clarity:

1: C = Ø
2: while there is uncovered edge (u,v)
3:   add vertex u into C
4:   add vertex v into C
5: return C

That’s it! For all uncovered edges (in any order), we only need to add both endpoints into the cover set (line 3 and 4). In other words,

Define: If a graph has a minimum vertex set of size C*, then the algorithm will always provide a solution of cost C such that C <= 2C*.

Proof:

  • Claim: The approximation ratio of the algorithm is 2.

  • Let S* be a vertex cover of optimal size |S*| = C*.

  • Let E# be the set of edges picked by the algorithm.

  • Every edge in E# has at least one vertex in S*.

  • Every edge in E# has 2 vertices in S.

  • There are no other vertices in S.

  • Thus, the size of S is at most twice the size of S*.

  • C/C* <= 2

Step 3:

Lemma: The proposed algorithm ALG produce a maximal matching. Every pair added into C in the algorithm is unique, it will not add edge (u,v) and (u,w) because when it encounters edge (u,v), it will add both vertex u and v, hence edge (u,w) will be covered by vertex u. Therefore, the algorithm will produce a matching in G, and it is maximal because it iterates until there is no uncovered edges.

Define: M – maximal matching.

Step 4:

From the algorithm and Lemma, we can conclude that the algorithm produce a vertex cover with size 2|M| (for each matching, we pick both vertices). Thus,because of step 4 and step 1, the algorithm produce a vertex cover with size 2 * number of vertices in a minimum vertex cover. And because n is even, the graph that will exist is bipartite with distinct sets of size n/2.

Q.E.D

$\endgroup$
  • 1
    $\begingroup$ Yes, for every $n$ there exists a bipartite graph having $n$ vertices. Some examples include the empty graph, a cycle, any forest, and so on. For some of these graphs (for example, the empty graph) the maximum matching algorithm is optimal, so I don't think that your proof works (without reading it). $\endgroup$ – Yuval Filmus Mar 15 at 20:43
  • 1
    $\begingroup$ Can you focus your question? Nobody is going to read your proof attempt. Do you have a specific step you are not sure of, or perhaps a gap you are not sure how to fill? $\endgroup$ – Yuval Filmus Mar 15 at 20:44
  • 1
    $\begingroup$ @IlanAizelmanWS Yes, there always is such a graph, and this is precisely what the question is asking you to prove. Indeed, there is always a bipartite example. But you're not constructing any particular graph in your proof attempt, so I doubt that you are able to show it. Instead, most of your proof seems to just reprove the fact that your algorithm gives a 2-approximation. We already know that. Now we want an example showing that the analysis is tight – that there are some cases in which the approximation ratio is indeed 2. $\endgroup$ – Yuval Filmus Mar 16 at 11:57
  • 2
    $\begingroup$ You can't say that there always exists a graph without explaining why such a graph should always exist. Perhaps the algorithm is actually a 1.5-approximation, but all we could prove is that it is a 2-approximation? How can we know? Only by giving explicit examples (or proving that ones exist) in which the algorithm actually gives a solution which is twice the optimum (or, more generally, $2-\epsilon$ times the optimum, for arbitrary $\epsilon>0$). Now that you know what you have to do, I suggest spending a few more hours on the question. $\endgroup$ – Yuval Filmus Mar 16 at 12:05
  • 1
    $\begingroup$ We already know that the size of the vertex cover produced by the algorithm is at most twice the optimum. You can't conclude from that there there is a graph for which the factor 2 is tight. If I prove $a \leq b$, I cannot conclude $a = b$, no matter how many times I reiterate the proof of $a \leq b$. $\endgroup$ – Yuval Filmus Mar 16 at 13:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.