11065 - A Gentlemen's Agreement

All about problems in Volume 110. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

lukasP
New poster
Posts: 3
Joined: Mon Aug 08, 2005 12:44 pm
Location: Pezinok, Slovakia

11065 - A Gentlemen's Agreement

Post by lukasP »

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

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post 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.

Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post 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.

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm

Post 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?
Self judging is the best judging!

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf »

No, that works only for bipartite graphs.

chrismoh
New poster
Posts: 35
Joined: Mon Dec 10, 2001 2:00 am
Location: Singapore; Cambridge, MA

Post by chrismoh »

Max matching only works for bipartite graphs.

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm

Post 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?
Self judging is the best judging!

chrismoh
New poster
Posts: 35
Joined: Mon Dec 10, 2001 2:00 am
Location: Singapore; Cambridge, MA

Post 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.

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm

Post by shanto86 »

so how to solve it with backtrack? any special heuristic?
Self judging is the best judging!

krijger
New poster
Posts: 39
Joined: Wed Jul 21, 2004 12:35 am

Post by krijger »

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

Towhid
New poster
Posts: 38
Joined: Wed May 28, 2003 5:30 pm
Location: Bangladesh
Contact:

Post by Towhid »

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

Towhid
New poster
Posts: 38
Joined: Wed May 28, 2003 5:30 pm
Location: Bangladesh
Contact:

Post by Towhid »

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

Towhid
New poster
Posts: 38
Joined: Wed May 28, 2003 5:30 pm
Location: Bangladesh
Contact:

Post by Towhid »

Well........ I have found my mistake. A silly one. Got Ac in 6.6 secs....... :D
From 0 to 0

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm

Post 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?
Self judging is the best judging!

Towhid
New poster
Posts: 38
Joined: Wed May 28, 2003 5:30 pm
Location: Bangladesh
Contact:

Post 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?
From 0 to 0

Post Reply

Return to “Volume 110 (11000-11099)”