## 10984 - Double NP-hard

Moderator: Board moderators

Monsoon
Learning poster
Posts: 66
Joined: Fri Jul 23, 2004 4:42 pm
Location: Poland

### 10984 - Double NP-hard

Hi,

could someone give some test cases, i don't know what i'm doing wrong

thanks

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
Try this:

Code: Select all

2
6 4
1 2
1 3
5 4
5 6
6 5
1 2
1 3
1 5
5 4
5 6
Correct output is: (edited to make it correct)
Case #1: Impossible
Case #2: Impossible
Last edited by Adrian Kuegel on Sun Jan 22, 2006 6:11 pm, edited 2 times in total.

Monsoon
Learning poster
Posts: 66
Joined: Fri Jul 23, 2004 4:42 pm
Location: Poland
hmm, possible i missunderstood something, but second test is something like this:
__3
|
1--2
|
5--4
|
6

so maximum independent set is {2,3,4,6} and minimum vertex cover is {1,5}, so answer is impossible?

Am i rigth? Or simple so stupid that i haven't understood this task?

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
-- Post removed by Observer --
Last edited by Observer on Sun Jan 22, 2006 5:58 pm, edited 1 time in total.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
Actually, it seems my program is wrong.
I agree the largest independant set for the second test case should be {2, 3, 4, 6}, and minimum vertex cover {1,5}.
I wonder why I got Accepted.

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
Hmm... probably the problemsetter has mistaken "maximum" as "maximal" then.. or maybe the test cases are just too simple ?
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
Edit: spoiler removed
Last edited by Adrian Kuegel on Mon Jan 23, 2006 12:25 am, edited 1 time in total.

Monsoon
Learning poster
Posts: 66
Joined: Fri Jul 23, 2004 4:42 pm
Location: Poland
exactly i do the same and i'm sure that this is correct algo

(***cut after acc***)

edit:
almost sure
Last edited by Monsoon on Sun Jan 22, 2006 8:54 pm, edited 1 time in total.

Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:
This problem is wrong. I'll fix it today.

Actually, just so that I don't screw it up again, Adrian or Monsoon, could you send me your solution please? (abednego at gmail)

igor
If only I had as much free time as I did in college...

L I M O N
Learning poster
Posts: 58
Joined: Wed Dec 31, 2003 8:43 am
Contact:
pls anyone give some hits to solve this problem.

Monsoon
Learning poster
Posts: 66
Joined: Fri Jul 23, 2004 4:42 pm
Location: Poland
one hint: think what is when graph is bipartite and what is when it's not

L I M O N
Learning poster
Posts: 58
Joined: Wed Dec 31, 2003 8:43 am
Contact:
Monsoon wrote:one hint: think what is when graph is bipartite and what is when it's not
thx for the hit. i already think that. But if the given graph is bipartite, then it's not sure that there is an answer. am i right ? Now tell me :

1. if the total node is odd, then its "Impossible".
2. if the graph is bipartite and the given graph has an answer, then the output will be left part of the bipartite graph(i.e which part contais 1st node).

Am i right ?

Now tell me abt the minimum vertex cover portion. what's the way to handle this part ? A graph has no answer if not bipartite or it's minimum vetex set size != total node / 2. right ?

hope u get my problem.
pls help.

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
You are right.
For minimum vertex cover, there exists an efficient algorithm if the graph is bipartite (which you can check first). 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.

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
Hmm. 1 Accepted and 34 Presentation Errors. Could it be that the judge has the wrong format? I'm (almost) sure my output is correctly formatted, but it's one of the 34.
No big deal, just want to mention it.
The biggest problem with most problems is not how to solve the problem, but how to not solve what is not the problem.

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm