193 - Graph Coloring

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

epsilon0
Experienced poster
Posts: 112
Joined: Tue Nov 12, 2002 11:15 pm
Location: Paris, France.

Post by epsilon0 » Sun Oct 26, 2003 8:02 pm

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
Location: Bangladesh

I am confused about the input

Post by A Faltoo Fellow » Mon Oct 27, 2003 6:12 am

:oops: I am a new solver.
:x 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

Post by Sajid » Mon Oct 27, 2003 9:33 am

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?

Post by technobug » Sun Nov 23, 2003 10:06 pm

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....

Thanks in advance,

Guilherme Silveira

Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:

Post by Whinii F. » Tue Nov 25, 2003 9:18 pm

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:

Post by technobug » Thu Nov 27, 2003 4:15 pm

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

Post by Per » Fri Nov 28, 2003 7:47 pm

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:

Post by Whinii F. » Sat Nov 29, 2003 7:25 pm

Oh, yes I was stupid again :oops:
These days I'm getting more stupid and stupidier, huh :wink:
JongMan @ Yonsei

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

193 Graph coloring algo

Post by Nick » Sun Dec 14, 2003 6:30 pm

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!!

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

Re: 193 Graph coloring algo

Post by szymcio2001 » Sat Dec 27, 2003 1:08 am

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.

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

the exact algorithm

Post by abishek » Sat Dec 27, 2003 12:07 pm

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??????

Post by NightZ-1 » Wed Mar 31, 2004 1:37 am

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.

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

no match

Post by sohel » Wed Mar 31, 2004 7:55 am

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:

Post by NightZ-1 » Wed Mar 31, 2004 4:07 pm

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

Post by junbin » Thu Apr 01, 2004 5:34 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..

Post Reply

Return to “Volume 1 (100-199)”