11065 - A Gentlemen's Agreement

lukasP · Post by **lukasP** » Sat Aug 12, 2006 11:01 pm

Hello,
this is maximum independent set problem, which is NP-complete. So how can it be solved in 15 seconds?

mf · Post by mf » Sat Aug 12, 2006 11:09 pm

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.

Martin Macko · Post by **Martin Macko** » Sun Aug 13, 2006 1:09 am

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.

shanto86 · Post by **shanto86** » Sun Aug 13, 2006 2:05 am

well... cant it be solved by maximum matching? i mean node-# of maximum matching in the general graph is the answer isnt it?

mf · Post by mf » Sun Aug 13, 2006 2:10 am

No, that works only for bipartite graphs.

chrismoh · Post by **chrismoh** » Sun Aug 13, 2006 2:11 am

Max matching only works for bipartite graphs.

shanto86 · Post by **shanto86** » Sun Aug 13, 2006 2:18 am

well... there is max matching in general graph algorithm.

but r u meaning that, such vertex cover theorem is applicable only for BP graph?

chrismoh · Post by **chrismoh** » Sun Aug 13, 2006 2:22 am

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.

shanto86 · Post by **shanto86** » Sun Aug 13, 2006 3:03 am

so how to solve it with backtrack? any special heuristic?

krijger · Post by **krijger** » Sun Aug 13, 2006 6:08 pm

Take a look at problem 11069. Part of it can also be used for this problem.

Towhid · Post by **Towhid** » Fri Aug 18, 2006 3:03 pm

I have used Backtracking and got WA. Can anybody send come I/O please.....

Towhid · Post by **Towhid** » Fri Aug 18, 2006 3:06 pm

I have used Backtracking and got WA. Can anybody send come I/O please.....

Towhid · Post by **Towhid** » Sat Aug 19, 2006 8:54 am

Well........ I have found my mistake. A silly one. Got Ac in 6.6 secs.......

shanto86 · Post by **shanto86** » Mon Aug 21, 2006 2:54 am

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?

Towhid · Post by **Towhid** » Mon Aug 21, 2006 12:20 pm

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?