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

How to check whether an arbitrary graph is 3-colorable in time O(2^N)?
Автор Sayakiss, 13 лет назад, По-английски

n is the number of vertex and Bruteforce is O(3^n)..Thanks in advance. 

(it's a additional exercise of SRM487D1_550pt)

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

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

UPD: Never mind, seems I played an idiot again. ;-)


I am sorry for what I am saying (since I may be wrong), but it looks that 2^n or 3^n are too much for coloring of the graph (or may be I misunderstood your problem?)

I suppose that proper page of wikipedia could give few hints on the topic. The problem seems to be of DP type and I guess it could be done in polynomial time.

(Sorry for being not exact - I did not read the article in wikipedia myself still because I want to try to invent solution myself before reading any hints)

→ Ответить
13 лет назад, # |
  Проголосовать: нравится -19 Проголосовать: не нравится
Ok, I am twice an idiot, since I wrote previous comment in wrong language. It was wrong comment I think anyway.

Second attempt:

Is it correct, that if graph is not 3-colorable, it necessarily have such 4 vertexes, that have all 6 edges between them?

If true, than we could check C(n,4) combinations of vertexes of the graph and for all of them check this property. It would give O(n^4) but I think I am missing something important.
→ Ответить
13 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится
Just fix vertexes which are colored in first color and check that others can be colored into 2 colors. O(2n(n + m)) complexity
→ Ответить