I am struggling to solve the following problem
http://uva.onlinejudge.org/external/1/193.html
However Im not able to get a fast solution.
And as seen by the times of others, there should be a solution of maximum n^2 complexity
Can I get some help?
A:
It is solving the problem called maximum clique, also called maximum independent set or maximum stable set. It is NP-Complete. Fastest code I know for small graphs is Cliquer: http://users.tkk.fi/pat/cliquer.html
If you are writing your own for educational purposes it is probably most efficient to do a depth first search coloring nodes black one at a time and retreating up the DFS if two black nodes are touching.
The easiest to code solution is implementing a binary counter and trying all 2^n possibilities.
Chad Brewbaker
2010-06-11 07:34:28
All 2^n possibilies? - 2^100 will hurt pretty hard:)
Petar Minchev
2010-06-11 07:35:26
what will be the complexity of the dfs??
copperhead
2010-06-11 07:35:30
@copperhead - it will also be `O(2^n)` in theory, but it will work much faster in practice because you'll be able to eliminate a lot of invalid solutions very fast. If you do it like that you'll surely get AC.
IVlad
2010-06-11 08:21:19
@|V|ad - Can u briefly describe what kind of algo do u have in mind??
copperhead
2010-06-11 08:25:26
@Chad: To nitpick. Maximum clique and Maximum independent set are different problems. For instance finding maximum independent set in a planar graph is NP-Complete, which is not the case for maximum clique for planar graphs. For general graphs, yes, finding max ind set in G is same as finding the max clique in the complement of G, but they are different problems.
Moron
2010-06-11 13:32:49
@Moron: I was mentioning alternate keywords to search on. Of course you would have to take the complement of the graph to use one algorithm as an oracle for the other.@copperhead, @Petar Yes. 2^n is nasty :p Cliquer and similar algorithms do an intelligent DFS that prunes off partial solutions when a more optimal one is already found. The keyword is "branch and bound".
Chad Brewbaker
2010-06-14 07:19:44
A:
I have solved a similar problem on FaceBook puzzles, I used the B-K algo for that.
zengr
2010-06-11 07:43:24
I found a sample code (ruby): http://kanwei.com/code/2009/03/26/facebook-peaktraffic.html
zengr
2010-06-11 08:02:40
well, I don't understand Ruby, so do u mind explaining the algo used??
copperhead
2010-06-11 08:35:52
+1
A:
You can only solve this in exponential complexity, but that's not as bad as it sounds, because in practice you'll be able to avoid a lot of bad decisions and thus reduce the running time of the algorithm significantly.
In short, you have to run a DF search from a node and try to color as many nodes black as you can. If you're at a node that has neighboring black nodes, that node can only be white. Keep doing this for every possibility of coloring a specific node.
If you can't figure it out, then check these two code snippets I found by googling for the problem name: one and two. The authors say they get AC, but I haven't tested them. They look correct however.
IVlad
2010-06-11 09:15:53