[HN Gopher] The Fastest Way yet to Color Graphs
___________________________________________________________________
The Fastest Way yet to Color Graphs
Author : GavCo
Score : 38 points
Date : 2025-05-13 08:29 UTC (2 days ago)
(HTM) web link (www.quantamagazine.org)
(TXT) w3m dump (www.quantamagazine.org)
| tonyarkles wrote:
| In 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.
| erikvanoosten wrote:
| You can convert edge coloring problems into vertex coloring
| problems and vice versa through a simple O(n) procedure.
| meindnoch wrote:
| 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.
| tonyarkles wrote:
| 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.
| mauricioc wrote:
| 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.
| Syzygies wrote:
| Yes. The article ran through this point as follows:
|
| "In 1964, a mathematician named Vadim Vizing proved a
| shocking result: No matter how large a graph is, it's
| easy to figure out how many colors you'll need to color
| it. Simply look for the maximum number of lines (or
| edges) connected to a single point (or vertex), and add
| 1."
|
| I keep wondering why I ever read Quanta Magazine. It
| takes a pretty generous reading of "need" to make this a
| correct statement.
| phkahler wrote:
| Is this going to lead to faster compile times? Faster register
| allocation...
| john-h-k wrote:
| Very few compilers actually use vertex coloring for register
| allocation
| isaacimagine wrote:
| 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!).
| NooneAtAll3 wrote:
| and this post isn't even about vertex coloring
___________________________________________________________________
(page generated 2025-05-15 23:01 UTC)