Adrian Kuegel wrote:
Hint: Think about how you can find a lower bound for the minimum number of nodes in the vertex cover (it turns out, if you find the right lower bound, that it is in fact the solution).
I guess, that the algorithm is also mentioned in some books about graph theory.
thx for the reply. But i m getting WA again and WA. did u mean Greedy approach ??
pls post some critical data.
Hint: Think about how you can find a lower bound for the minimum number of nodes in the vertex cover (it turns out, if you find the right lower bound, that it is in fact the solution).
Another Hint: In a bipartite graph, the size of the minimum vertex cover can be found in polynomial time. We can then check to see if the size of the minimum vertex cover matches with the size of the independent set.
little joey wrote:
You can do that by hand: {1,2,5} is a max. ind. set, and the complement, {3,4,6,7}, is a min. vert. cover.
Oh, I misunderstood the problem definition. Sorry, I thought that vertex cover is a set C such that for every vertex in V\C there is an edge that connect it with C. Thats why I thought answer should be {3,4,6}.
If you can color all vertexes of a graph with at most two colors then it is bipartite. Moreover, color of a particular vertex defines to which part it belongs to.
Here is my reasoning for "why if the graph is not bipartite, it is "Impossible" to find a maximum independent set which is also a minimum vertex cover":
We use the following Lemmas:
1. (Lemma 1) A graph is bipartite (bi-colorable) if and only if it has no odd cycles. (You can find this in almost ever graph theory and discrete mathematics book. If you need its proof, please tell me)
2. (Lemma 2) If It is "impossible" to find a max. independent se minimum vertex cover for a subgraph G' of graph G, then it is also "impossible" for graph G.
Then, we show that for a odd-cycle which is a sub-graph of a non-bipartite graph, it is "impossible" :
We have a graph which is and odd cycle. we number its vertices like this : from 1 to n where i is connected to i+1 , and n is odd (n % 2 = 1)
Now, we want to get a maximum indepedent set. We assume that we first mark vertex 1 without loss of generality.
We mark vertex 1. We cannot mark vertex 2 considering the definition for "maximum independent set". then we mark vertex 3 ... there are two possiblities:
1. We continue this method until the end. it means we will mark every vertex i for which i = 2k+1 for some k. then, we should also mark vertex n which also of form 2k+1. but we cannot do this since there is an edge between it and vertex 1, and vertex 1 is already marked. then, the edge between vertex n-1 and n has no end-points which is marked, so it is not "covered", so this cannot be a "Minimum vertex cover"!
2. We skip some i = 2k+1 somewhere in our method. then, i-1 is not marked, and i is not marked. then, the edge {i, i-1} is not covered. then, this cannot be a "Minimum Vertex Cover"!
Since we couldn't accomplish finding a "Maxmimum independent set minimum vertex cover" for a sugraph of our un-bipartite graph, according to Lemma 2, we cannot find a "Maximum independet set minimum vertex cover" for our graph.
So, It is "impossible" for a non-bipartite graph to find a such subset of vertices.
This was my method for proofing this. I haven't seen this proof anywhere, so it may contain some errors. If you find any please tell me. and If anyone has a more-structured and a better proof, please post it to the board.
Thanks.
Suppose we have some independent set C which is also a vertex cover.
Then
1. There are no edges in C (it is independent)
2. There are no edges in V\C (C is a vertex cover)
So all edges have one endpoint in C and other in V\C i.e. graph is bipartite
we can't assume the existence of some independent set C which is also a vertex cover since they don't need to be the same set of vertices, only the size need to be the same. We need to show that is not the case.
