10984 - Double NP-hard

Monsoon · Post by **Monsoon** » Sun Jan 22, 2006 5:09 pm

Hi,

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

thanks

Adrian Kuegel · Post by **Adrian Kuegel** » Sun Jan 22, 2006 5:22 pm

Try this:

Correct output is: (edited to make it correct)
Case #1: Impossible
Case #2: Impossible

Monsoon · Post by **Monsoon** » Sun Jan 22, 2006 5:38 pm

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 · Post by **Observer** » Sun Jan 22, 2006 5:42 pm

-- Post removed by Observer --

Adrian Kuegel · Post by **Adrian Kuegel** » Sun Jan 22, 2006 5:53 pm

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 · Post by **Observer** » Sun Jan 22, 2006 5:57 pm

Hmm... probably the problemsetter has mistaken "maximum" as "maximal" then.. or maybe the test cases are just too simple ?

Adrian Kuegel · Post by **Adrian Kuegel** » Sun Jan 22, 2006 6:07 pm

Edit: spoiler removed

Monsoon · Post by **Monsoon** » Sun Jan 22, 2006 6:15 pm

exactly i do the same

and i'm sure that this is correct algo

(***cut after acc***)

edit:
almost sure

Abednego · Post by **Abednego** » Sun Jan 22, 2006 6:34 pm

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

L I M O N · Post by **L I M O N** » Thu Jan 26, 2006 10:21 am

pls anyone give some hits to solve this problem.

Monsoon · Post by **Monsoon** » Thu Jan 26, 2006 3:00 pm

one hint: think what is when graph is bipartite and what is when it's not

L I M O N · Post by **L I M O N** » Fri Jan 27, 2006 4:31 pm

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.

Adrian Kuegel · Post by **Adrian Kuegel** » Fri Jan 27, 2006 4:49 pm

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 · Post by **little joey** » Fri Jan 27, 2006 6:52 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.

sclo · Post by **sclo** » Fri Jan 27, 2006 10:51 pm

I had the same problem with presentation error, I don't know what's wrong, but definitely there's some problem with the judge's output format. I'm sure mine is correct.