## 11065 - A Gentlemen's Agreement

Moderator: Board moderators

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

### 11065 - A Gentlemen's Agreement

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:
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)
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
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:
No, that works only for bipartite graphs.

chrismoh
New poster
Posts: 35
Joined: Mon Dec 10, 2001 2:00 am
Location: Singapore; Cambridge, MA
Max matching only works for bipartite graphs.

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm
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
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
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
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
Contact:
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
Contact:
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
Contact:
Well........ I have found my mistake. A silly one. Got Ac in 6.6 secs.......
From 0 to 0

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm
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