Baltic BOI 2017 #1: Political Development

Revision en3, by minimario, 2017-06-15 22:44:21

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

Tags baltic boi, sad!

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English minimario 2017-06-15 22:44:21 14
en2 English minimario 2017-06-15 22:43:23 2 Tiny change: ' clique:\n~~~~~\nw' -> ' clique:\n\n~~~~~\nw'
en1 English minimario 2017-06-15 22:39:41 1025 Initial revision (published)