Sayakiss's blog

How to check whether an arbitrary graph is 3-colorable in time O(2^N)?
By Sayakiss, 15 years ago, In English

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

(it's a additional exercise of SRM487D1_550pt)

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

Comments Comments (2)
| Write comment?
15 years ago, hide # |
 
Vote: I like it -19 Vote: I do not like it
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.
→ Reply
15 years ago, hide # |
 
Vote: I like it +14 Vote: I do not like it
Just fix vertexes which are colored in first color and check that others can be colored into 2 colors. O(2n(n + m)) complexity
→ Reply