10984 - Double NP-hard

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.

User avatar
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?

Code: Select all

 Cut After AC ...
 
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:

Code: Select all

1
7
5
1 3
2 4
5 6
6 7
7 5

User avatar
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:

Code: Select all

1
7
5
1 3
2 4
5 6
6 7
7 5
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}.

User avatar
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 :wink:

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 bi-color to solve it in bi-partie 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.

User avatar
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 (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. :)

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"

Post Reply

Return to “Volume 109 (10900-10999)”