Page 1 of 2
11065 - A Gentlemen's Agreement
Posted: Sat Aug 12, 2006 11:01 pm
by lukasP
Hello,
this is maximum independent set problem, which is NP-complete. So how can it be solved in 15 seconds?
Posted: Sat Aug 12, 2006 11:09 pm
by mf
I guess the test cases in the input aren't too tough.
I've used backtracking with some pruning to generate every independent set, and it got just ~0.6 seconds.
Posted: Sun Aug 13, 2006 1:09 am
by Martin Macko
I'm curious why I'm getting TLEs now, while I've got ACed it in a couple of seconds with the same code during the contest.
Posted: Sun Aug 13, 2006 2:05 am
by shanto86
well... cant it be solved by maximum matching? i mean node-# of maximum matching in the general graph is the answer isnt it?
Posted: Sun Aug 13, 2006 2:10 am
by mf
No, that works only for bipartite graphs.
Posted: Sun Aug 13, 2006 2:11 am
by chrismoh
Max matching only works for bipartite graphs.
Posted: Sun Aug 13, 2006 2:18 am
by shanto86
well... there is max matching in general graph algorithm.
but r u meaning that, such vertex cover theorem is applicable only for BP graph?
Posted: Sun Aug 13, 2006 2:22 am
by chrismoh
Yes, although there are max matching algorithms in general graphs (blossom shrinking and the like), the theorem
Maximum Independent Set = n - MaxMatch
only works in bipartite graphs.
Posted: Sun Aug 13, 2006 3:03 am
by shanto86
so how to solve it with backtrack? any special heuristic?
Posted: Sun Aug 13, 2006 6:08 pm
by krijger
Take a look at problem 11069. Part of it can also be used for this problem.
Posted: Fri Aug 18, 2006 3:03 pm
by Towhid
I have used Backtracking and got WA. Can anybody send come I/O please.....
Posted: Fri Aug 18, 2006 3:06 pm
by Towhid
I have used Backtracking and got WA. Can anybody send come I/O please.....
Posted: Sat Aug 19, 2006 8:54 am
by Towhid
Well........ I have found my mistake. A silly one. Got Ac in 6.6 secs.......
Posted: Mon Aug 21, 2006 2:54 am
by shanto86
well, before coding i want to be sure about the process...
pick a non-visited vertex,
1. color it, make its neighbours uncolored and proceed
2. uncolor it and proceed
by uncolor means it is visited but not colored.
and when the rest + colored < best i will cutoff... is there any other things?
Posted: Mon Aug 21, 2006 12:20 pm
by Towhid
shanto86 wrote:and when the rest + colored < best i will cutoff... is there any other things?
What is best? Is it the number of elements in the largest set? But you also have to count the number of possible sets. How can you cut off?