## 193 - Graph Coloring

Moderator: Board moderators

epsilon0
Experienced poster
Posts: 112
Joined: Tue Nov 12, 2002 11:15 pm
Location: Paris, France.
this problem is a bit harder than it seems.

you have a test different possibilities (not all though)

it might be a good idea to first color nodes that have a lot of connections.

i found the following:

1) if a node is connected to a black node, it has to be white.

otherwise:

2) if a node is connected to 0 or 1 univisited nodes, you might assume that this node is black

3) if a node is connected to 2 or more univisited nodes, you can't assume anything, you have to test both black and white colors.

good luck
We never perform a computation ourselves, we just hitch a ride on the great Computation that is going on already. --Tomasso Toffoli

A Faltoo Fellow
New poster
Posts: 3
Joined: Thu Jul 03, 2003 2:30 pm

### I am confused about the input

I am a new solver.
I am being confused whether the graph will be connected or not.

Sajid
Learning poster
Posts: 94
Joined: Sat Oct 05, 2002 5:34 pm
Location: CS - AIUB, Dhaka, Bangladesh.
Contact:

### Re: I am confused about the input

A Faltoo Fellow wrote: I am being confused whether the graph will be connected or not.
There is no problem whether the graph is connect or not. If the node is not connected with any other node, it must be colored black. get it ?

epsilon0,
ya, I get u. now, i m considering your case. not done yet. Thanx a lot.
Sajid Online: www.sajidonline.com

technobug
Learning poster
Posts: 88
Joined: Sat Nov 15, 2003 6:41 pm
Location: Brasilien
Contact:

### 193 Graph Coloring Algorithm - Dynamic programming?

I tried a greedy algorithm (that I took out from my mind...) and got WA.... so I am gonna try the brute force + dynamic programming.... but just to check if there is another solution....

I used something like:
1. Get the vertex with less connections
2. Paint it black
3. Paint every vertex connected white
4. Remove those vertex's from the graph (the black one is only connected to the white ones so its ok. the white ones wont influence the other ones which are still in the graph so its ok)
5. Go back to 1 and get the new vertex (which might have changed as we removed some connections)

It worked with most graphs I tried but did not pass the test so I know its not ok....
Anyone knows the "right" way of doing this? I dont want to get AC with a "dumb" brute force - dynamic programming one....

Guilherme Silveira

Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:
I can't think of a P time class solution, for graph coloring is a well-known NP problem. (Of course this problem is not the exact instance of it) My solution is backtracking and it runs in 0.037.

So, if you have discovered any DP algorithm other than 2^N, it will be no dumb but really great
JongMan @ Yonsei

technobug
Learning poster
Posts: 88
Joined: Sat Nov 15, 2003 6:41 pm
Location: Brasilien
Contact:
Ne... i did not get it
I got it right when i did the whole backtracking system (with some nice purges, of course)

I am not a real big academic guy... im just starting reading so i saw its a basic algo..... anyhow, this exercice is not really the actual coloring as it allows WHITE-WHITE..... as u said..;.

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden
The problem is actually Maximal Independent Set. But of course, that's NP-complete as well.

Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:
Oh, yes I was stupid again
These days I'm getting more stupid and stupidier, huh
JongMan @ Yonsei

Nick
Learning poster
Posts: 53
Joined: Sun Jan 12, 2003 4:49 am

### 193 Graph coloring algo

okay I have no idea about NP-complete problems nor any algo to solve them. Can anyone share something to help me especially on this problem?

Is there any way besides backtracking? thx!!

szymcio2001
New poster
Posts: 38
Joined: Mon Dec 09, 2002 1:53 pm
Location: Poznan, Poland

### Re: 193 Graph coloring algo

Nick wrote:okay I have no idea about NP-complete problems nor any algo to solve them. Can anyone share something to help me especially on this problem?

Is there any way besides backtracking? thx!!
In this problem you should write some "simulation" algorithm. Simply write a program that randomly choose nodes (choose random node and delete all connected with him, choose another, etc. while there are some nodes), do it several times (I did it 200 times) and choose the maximum result. It isn't very good way for NP problems but in this task it works.

abishek
Experienced poster
Posts: 131
Joined: Mon Dec 15, 2003 5:41 am

### the exact algorithm

Is this problem exactly the same as finding a maximum stable set of a graph?
Are there any good heuristics as the problem says n <= 100 and the exact solution is exponential on n.

NightZ-1
New poster
Posts: 8
Joined: Sun Feb 01, 2004 11:47 pm
Location: SP, Brazil
Contact:

### 193 WA why? What's wrong in my algorithm??????

Somebody can help me?
Where it can be the error?

Follows mine in/out

My input:
15
6 8
1 2
1 3
2 4
2 5
3 4
3 6
4 6
5 6
10 12
1 2
1 3
1 4
2 3
2 5
3 4
4 6
5 8
6 8
7 8
8 9
9 10
14 21
1 2
1 3
1 4
2 3
2 4
2 5
2 6
3 5
3 10
4 6
4 12
5 7
6 7
7 9
7 8
9 14
8 14
12 13
13 14
14 11
11 10
14 24
1 2
1 3
1 4
2 3
2 4
2 5
2 6
3 5
3 10
4 6
4 12
5 7
5 8
6 7
6 9
7 9
7 8
9 8
9 14
8 14
12 13
13 14
14 11
11 10
1 1
1 1
3 2
1 2
2 3
4 3
1 2
2 3
3 4
5 4
1 2
2 3
3 4
4 5
5 5
1 2
2 3
3 4
4 5
5 1
6 10
1 2
2 3
3 4
4 5
5 1
1 6
2 6
3 6
4 6
5 6
7 11
1 2
2 3
3 4
4 5
5 1
1 6
2 6
3 6
4 6
5 6
1 7
100 2
1 2
2 3
20 19
1 10
2 5
3 4
4 9
5 17
6 4
8 19
9 13
10 11
11 14
12 1
13 6
14 3
15 4
16 5
17 8
18 9
19 15
20 4
11 12
7 5
10 5
1 3
8 5
2 6
4 11
3 5
6 5
11 5
1 4
9 5
1 2
35 40
32 34
33 32
35 32
9 33
32 8
12 16
18 14
13 7
30 33
4 30
2 13
27 26
4 29
6 5
10 6
9 6
32 7
3 1
21 3
12 3
2 1
24 12
12 23
22 12
16 14
19 14
14 15
7 6
6 8
13 14
1 4
27 4
5 4
11 30
31 30
32 30
13 25
25 26
6 11
14 17
My output:
3
1 4 5
5
1 5 6 7 9
7
1 5 6 8 9 10 12
6
1 5 6 10 12 14
1
1
2
1 3
2
1 3
3
1 3 5
2
1 3
2
1 3
3
2 5 7
2
1 3
10
2 4 10 12 13 14 16 17 18 19
7
2 3 4 7 8 9 10
20
2 3 4 7 8 10 11 15 16 17 18 19 22 23 24 25 31 33 34 35
Last edited by NightZ-1 on Tue Apr 06, 2004 5:16 pm, edited 1 time in total.

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

### no match

My AC program gives the following output for your input:

[c]
3
1 4 5
5
1 5 6 7 9
7
1 5 6 8 9 10 12
6
1 5 6 10 12 14
0
1
2
1 3
2
1 3
3
1 3 5
2
1 3
2
1 3
3
2 4 7
99
1 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
11
1 2 3 6 7 8 9 11 15 16 20
7
1 6 7 8 9 10 11
24
1 5 7 8 9 10 11 15 16 17 18 19 20 21 22 23 24 25 27 28 29 31 34 35
[/c]

NightZ-1
New poster
Posts: 8
Joined: Sun Feb 01, 2004 11:47 pm
Location: SP, Brazil
Contact:
Thanks sohel.

I found my error.

I am using BFS, but in this case I think i will have to use Backtracking. Is this correct ?

Do you know any other solution, more simple than that?

junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am
NightZ-1 wrote:Thanks sohel.

I found my error.

I am using BFS, but in this case I think i will have to use Backtracking. Is this correct ?

Do you know any other solution, more simple than that?
Backtracking is the easiest to code for this problem..