Блог пользователя minimario

Автор minimario, история, 7 лет назад, По-английски

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

  • Проголосовать: нравится
  • +32
  • Проголосовать: не нравится

»
7 лет назад, # |
Rev. 3   Проголосовать: нравится +8 Проголосовать: не нравится

jk

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

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

      • »
        »
        »
        »
        7 лет назад, # ^ |
        Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

        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)

        • »
          »
          »
          »
          »
          7 лет назад, # ^ |
          Rev. 3   Проголосовать: нравится +5 Проголосовать: не нравится

          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.