Bipartite Graph (undirected)

Question

I am taking an input, e.g. 4 1 3 1 2 2 4

First line is number of nodes, lines after that are the edges. I have to attempt to color the graph, and if I can't, I need to list a cycle in the graph that is causing the error.

This is fine so far, except one of the graphs contains 1,000,000 nodes. Everytime I try to use it I get a Stack Overflow error, even though I streamlined it more, and raised the max heap size of eclipse to 1024m.

I'm not asking for code, just asking if I am doing something blatantly wrong to keep getting errors.

Answer 1

Well, this IS an NP complete problem (longest cycle), so this sort of thing IS likely to happen.

I'd probably just bump the heap again, and let it run...

EDIT: Never mind. got my reduction backwards.

Answer 2

Maybe you could optimize your cycle detection algorithm. This might help you: http://en.wikipedia.org/wiki/Cycle_detection

Other than that, a million nodes plus adjacency matrix might as well be too much to handle at once, so perhaps there's a way to just load parts of the graph at a time.

Answer 3

If it's a bipartite graph you can always colour it with only two colours (e.g. colour the first partition white, and the second partition black).

Usually when one thinks of colouring a graph he should specify the number of colours. You can always colour a graph by assigning to each node a different colour. Another example: for planar graphs only four colour are required. However, for most graphs the [chromatic number] of a graph is [NP].

[NP] http://en.wikipedia.org/wiki/Karp%27s_21_NP-complete_problems

[chromatic number] http://en.wikipedia.org/wiki/Graph_coloring