Omnimaga

General Discussion => Other Discussions => Math and Science => Topic started by: harold on October 05, 2014, 11:56:58 am

Title: Graph coloring mini challenge
Post by: harold on October 05, 2014, 11:56:58 am
You've probably heard that a map (with some restrictions: no enclaves, no "bridges", countries meeting at a point are not considered adjacent) can be colored using only four colors.

Graph coloring is a bit more general: given a bunch of "nodes" with "edges" between them, color the nodes such that no two adjacent (ie, have an edge between them) nodes have the same color. A trivial way to do that would be giving every node its own color. A bit better would be to start at the first node, give it color 0, then the second node can have color 0 or 1 (depending on whether it's connected to the first) and so on, and there are tricks you can play here with the order in which you visit the nodes (it matters a lot, and in fact there is an order such that you get an optimal coloring this way, there are many interesting things you can do there).

The challenge is usually to find such a coloring with the fewest possible number of colors, but you could also ask: given a certain number of colors you're allowed to use, can you color the graph? (this is an example of an NP-complete problem)

Anyway for this mini challenge, there are two graphs (I could make more, if necessary), a small one with 50 nodes and 350 edges, and a big one with 500 nodes and 62423 edges. The second one is particularly nasty not so much because it has 500 nodes, but mainly because it has about half as many edges as it could maximally have, which is about the worst case (more edges and it becomes so constrained that there are not many solutions to try, less edges and you won't need as many colours so again there are few solution). But whatever, the point is, there's an easy one and a hard one. The east one is still big enough that you can't blindly try everything though, you have to be at least slightly clever.

50 graph: gc50.txt (https://dl.dropboxusercontent.com/u/27035142/gc50.txt)
500 graph: gc500.txt (https://dl.dropboxusercontent.com/u/27035142/gc500.txt)
Format: first line is [number of nodes] [number of edges]
Other lines are the edges, a pair of nodes that has a link between them.
The last line is empty (so that every line you read can end in \r\n to simplify parsing or whatever), and there are exactly as many edges as advertised (so you can read them in a for loop and not care about end of file).

Challenges (easy):

Challenges (medium):

Challenges (hard):

Challenges (impossible):

Challenges (other):

PM answers to me (don't post colorings please, feel free to post lower bounds), discuss everything (as long as it doesn't violate "don't post colorings"), pretty much anything goes with respect to how you solve this but it will be more interesting for you if you play with the problems yourself instead of just dumping them into open source solvers.
Title: Re: Graph coloring mini challenge
Post by: Xeda112358 on October 28, 2014, 12:37:52 pm
Well, I've been wanting to get back into graph theory, so I guess this will make an excuse to look into some of my books.
Title: Re: Graph coloring mini challenge
Post by: harold on November 06, 2014, 03:00:24 pm
Any progress, xeda?

Other people: come on guys, it's great fun to try it :)