193 - Graph Coloring

[epsilon0]

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

[A Faltoo Fellow]

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

[Sajid]

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.

[technobug]

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

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

[technobug]

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]

The problem is actually Maximal Independent Set. But of course, that's NP-complete as well.

[Whinii F.]

Oh, yes I was stupid again
These days I'm getting more stupid and stupidier, huh

[Nick]

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]

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]

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]

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

[sohel]

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]

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]

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