minimario's blog

Baltic BOI 2017 #1: Political Development
By minimario, history, 7 years ago, In English

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

  • Vote: I like it
  • +32
  • Vote: I do not like it

»
7 years ago, # |
← Rev. 3   Vote: I like it +8 Vote: I do not like it

jk

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Is it really? I thought the actual answer was 4.

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
        ← Rev. 3   Vote: I like it 0 Vote: I do not like it

        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:

        counter example:   3 instead of 4
1 2
1 3
1 4
1 5
1 7
2 3
2 6
2 7
3 5
3 6
3 7
4 5
4 6
4 7
5 6
6 7

        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)

        → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
          ← Rev. 3   Vote: I like it +5 Vote: I do not like it

          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.

          → Reply