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