Hi all :')
I've recently solved 2017 Baltic BOI Day 1 #1 Political Development (D here
The algorithm to find the max clique here is as follows:
while (graph not empty):
pick any vertex with min degree
if the vertex and some subset of neighbors of it form a clique, check if it's larger than the ones we found so far
remove the vertex
But I propose an alternate solution to finding max clique:
while (graph not empty):
pick any vertex with min degree
if the vertex and all neighbors of it form a clique, check if it's larger than the ones we found so far
remove the vertex
I know it's wrong (because it's a polynomial time), but every time I try to find a counterexample, I can never do so.
Can someone provide a counterexample for my 2nd algorithm to the max clique problem (or prove it, then we have P=NP!)
Thanks,
minimario
jk
I guess the correct answer was 5, right? I've just implemented some brute force, generator and the approach itself to see whether I can crack it or not. It seems that running your test with my code generates the answer 4, which indeed fails.
Is it really? I thought the actual answer was 4.
I couldn't run my brute force on that test (it was too big). But I thought the answer is 5 (clique 2-6 or so), but now I'm starting to think it was 4 indeed:)). Anyway, I've run my brute force and generator a little more. I've tested all the tests with N = 6 and none of them failed. However, if I set N = 7, it can easily find a counterexample. Here is what it printed:
So, indeed, the approach is wrong. This is one of the smallest tests that fail (with N = 7, as I said all tests with N = 6 work properly)
Could you tell me the order of removing to make it fail?
I tried multiple removals, all of which succeeded.
Edit: Never mind, I got it. Thanks! Removal of 2 creates symmetric 4-cliqueless figure.