All about problems in Volume 109. If there is a thread about your problem, please use it. If not, create one with its number in the subject.
Moderator: Board moderators

L I M O N
 Learning poster
 Posts: 58
 Joined: Wed Dec 31, 2003 8:43 am
 Location: Dhaka, Bangladesh

Contact:
Post
by L I M O N » Sat Jan 28, 2006 6:41 am
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.

sclo
 Guru
 Posts: 519
 Joined: Mon Jan 23, 2006 10:45 pm
 Location: Vancouver, BC, Canada

Contact:
Post
by sclo » Sat Jan 28, 2006 8:08 am
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.

L I M O N
 Learning poster
 Posts: 58
 Joined: Wed Dec 31, 2003 8:43 am
 Location: Dhaka, Bangladesh

Contact:
Post
by L I M O N » Sat Jan 28, 2006 8:24 am
sclo wrote:
Another Hint: In a bipartite graph, the size of the minimum vertex cover can be found in polynomial time.
Here is my problem. I dont know that Algorithm, Only greedy method comes to my Head. pls explain the algorithm in brief.

L I M O N
 Learning poster
 Posts: 58
 Joined: Wed Dec 31, 2003 8:43 am
 Location: Dhaka, Bangladesh

Contact:
Post
by L I M O N » Sat Jan 28, 2006 10:18 am
Finally got Acc(Presentation Error). Thx all to help.

Hadi
 Learning poster
 Posts: 63
 Joined: Mon Aug 29, 2005 8:13 am
 Location: Tebriz

Contact:
Post
by Hadi » Sun Jan 29, 2006 10:03 am
Is my approach wrong?
I get "Wrong Answer"
Last edited by
Hadi on Thu Feb 02, 2006 7:15 am, edited 7 times in total.

kp
 Learning poster
 Posts: 71
 Joined: Tue Apr 26, 2005 1:29 am
 Location: Russia
Post
by kp » Sun Jan 29, 2006 1:09 pm
Can someone who got AC or PE tell me what is the answer for the following test:

little joey
 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm
Post
by little joey » Sun Jan 29, 2006 1:50 pm
kp wrote:Can someone who got AC or PE tell me what is the answer for the following test:
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.
The biggest problem with most problems is not how to solve the problem, but how to not solve what is not the problem.

kp
 Learning poster
 Posts: 71
 Joined: Tue Apr 26, 2005 1:29 am
 Location: Russia
Post
by kp » Sun Jan 29, 2006 2:18 pm
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}.

Hadi
 Learning poster
 Posts: 63
 Joined: Mon Aug 29, 2005 8:13 am
 Location: Tebriz

Contact:
Post
by Hadi » Tue Jan 31, 2006 5:27 pm
I got AC

FAQ
 Learning poster
 Posts: 84
 Joined: Wed Jan 28, 2004 6:23 pm
Post
by FAQ » Wed Feb 01, 2006 6:33 am
Could anyone explain to me, why we should use bicolor to solve it in bipartie graph, please?

kp
 Learning poster
 Posts: 71
 Joined: Tue Apr 26, 2005 1:29 am
 Location: Russia
Post
by kp » Wed Feb 01, 2006 10:32 am
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.

Hadi
 Learning poster
 Posts: 63
 Joined: Mon Aug 29, 2005 8:13 am
 Location: Tebriz

Contact:
Post
by Hadi » Thu Feb 02, 2006 7:13 am
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 (bicolorable) 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 oddcycle which is a subgraph of a nonbipartite 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 n1 and n has no endpoints 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, i1 is not marked, and i is not marked. then, the edge {i, i1} 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 unbipartite graph, according to Lemma 2, we cannot find a "Maximum independet set minimum vertex cover" for our graph.
So, It is "impossible" for a nonbipartite 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 morestructured and a better proof, please post it to the board.
Thanks.

kp
 Learning poster
 Posts: 71
 Joined: Tue Apr 26, 2005 1:29 am
 Location: Russia
Post
by kp » Thu Feb 02, 2006 9:20 am
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

sclo
 Guru
 Posts: 519
 Joined: Mon Jan 23, 2006 10:45 pm
 Location: Vancouver, BC, Canada

Contact:
Post
by sclo » Fri Feb 03, 2006 9:45 am
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.

kp
 Learning poster
 Posts: 71
 Joined: Tue Apr 26, 2005 1:29 am
 Location: Russia
Post
by kp » Fri Feb 03, 2006 11:09 am
I'm afraid I didn't get what you mean...
Problem says:
"Given a graph G, find a subset C of its vertices that is both a minimum vertex cover and a maximum independent set."
I assert if G contains some vertex subset C which is both vertex cover and independent set then G is bipartite.
This is equal to following:
"If G is not bipartite then it doesn't contain such subset C"