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). 
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
