The Fastest Way yet to Color Graphs
quantamagazine.org
The Fastest Way yet to Color Graphs
1–10 of 17 posts
Re: The Fastest Way yet to Color Graphs
#2In case you haven't looked at the article, this is looking specifically at the Edge Coloring problem and not the more commonly known Vertex Coloring problem. Vertex Coloring is NP-complete unfortunately.
Re: The Fastest Way yet to Color Graphs
#3In case you haven't looked at the article, this is looking specifically at the Edge Coloring problem and not the more commonly known Vertex Coloring problem. Vertex Coloring is NP-complete unfortunately.
You can convert edge coloring problems into vertex coloring problems and vice versa through a simple O(n) procedure.
Re: The Fastest Way yet to Color Graphs
#4Is this going to lead to faster compile times? Faster register allocation...
Re: The Fastest Way yet to Color Graphs
#5Is this going to lead to faster compile times? Faster register allocation...
Very few compilers actually use vertex coloring for register allocation
Re: The Fastest Way yet to Color Graphs
#6In case you haven't looked at the article, this is looking specifically at the Edge Coloring problem and not the more commonly known Vertex Coloring problem. Vertex Coloring is NP-complete unfortunately.
You can convert edge coloring problems into vertex coloring problems and vice versa through a simple O(n) procedure.
Wrong. You can convert edge-coloring problems into vertex-coloring problems of the so-called line graph: https://en.m.wikipedia.org/wiki/Line_graph
But the opposite is not true, because not every graph is a line graph of some other graph.
Re: The Fastest Way yet to Color Graphs
#7In case you haven't looked at the article, this is looking specifically at the Edge Coloring problem and not the more commonly known Vertex Coloring problem. Vertex Coloring is NP-complete unfortunately.
You can convert edge coloring problems into vertex coloring problems and vice versa through a simple O(n) procedure.
Hrm... right. It's been a while. And it looks like both Vertex Coloring and Edge Coloring are both NP-complete (because of the O(n) procedure you're talking about and the ability to reduce both problems down to 3-SAT). I've started looking closer at the actual paper to try to figure out what's going on here. Thanks for the reminder, I miss getting to regularly work on this stuff.
Edit: thanks sibling reply for pointing out that it's not a bidirectional transform.
Re: The Fastest Way yet to Color Graphs
#8Is this going to lead to faster compile times? Faster register allocation...
Very few compilers actually use vertex coloring for register allocation
Totally. The hard part isn't coloring (you can use simple heuristics to get a decent register assignment), rather, it's figuring out which registers to spill (don't spill registers in hot loops! and a million other things!).
Re: The Fastest Way yet to Color Graphs
#9Earlier quoted context omitted.
You can convert edge coloring problems into vertex coloring problems and vice versa through a simple O(n) procedure.
Hrm... right. It's been a while. And it looks like both Vertex Coloring and Edge Coloring are both NP-complete (because of the O(n) procedure you're talking about and the ability to reduce both problems down to 3-SAT). I've started looking closer at the actual paper to try to figure out what's going on here. Thanks for the reminder, I miss getting to regularly work on this stuff. Edit: thanks sibling reply for pointi…
For the edge-coloring problem, the optimal number of colors needed to properly color the edges of G is always either Delta(G) (the maximum degree of G) or Delta(G) + 1, but deciding which one is the true optimum is an NP-complete problem.
Nevertheless, you can always properly edge-color a graph with Delta(G) + 1 colors. Finding such a coloring could in principle be slow, though: the original proof that Delta(G) + 1 colors is always doable amounted to a O(e(G) * v(G)) algorithm, where e(G) and v(G) denote the number of edges and vertices of G, respectively. This is polynomial, but nowhere near linear. What the paper in question shows is how, given any graph G, to find an edge coloring using Delta(G) + 1 colors in O(e(G) * log(Delta(G))) time, which is linear time if the maximum degree is a constant.