Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The Fastest Way yet to Color Graphs

quantamagazine.org

Post reply on HN
Print view View original

11–17 of 17 posts

Re: The Fastest Way yet to Color Graphs

#11

Post by Syzygies »

mauricioc wrote: post #9
tonyarkles wrote: post #7

Earlier quoted context omitted.

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 c…

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.

Re: The Fastest Way yet to Color Graphs

#12

Post by DannyBee »

phkahler wrote: post #4

Is this going to lead to faster compile times? Faster register allocation...

No.

In SSA, the graphs are chordal, so were already easily colorable (relatively).

Outside of SSA, this is not true, but the coloring is still not the hard part, it's the easy part.

Re: The Fastest Way yet to Color Graphs

#13

Post by JohnKemeny »

Syzygies wrote: post #11
mauricioc wrote: post #9

Earlier quoted context omitted.

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 c…

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 "nee…

Not really. Coloring a graph is almost always talking about proper coloring, meaning that things that objects that are related receive different colors.

If you read the introduction, you'll also read that the goal is to "color each of your lines and require that for every point, no two lines connected to it have the same color."

Ps. "How many colors a graph needs" is a very well established term in computer science and graph theory.

Re: The Fastest Way yet to Color Graphs

#14

Post by mockerell »

JohnKemeny wrote: post #13
Syzygies wrote: post #11

Earlier quoted context omitted.

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 "nee…

Not really. Coloring a graph is almost always talking about proper coloring, meaning that things that objects that are related receive different colors. If you read the introduction, you'll also read that the goal is to "color each of your lines and require that for every point, no two lines connected to it have the same color." Ps. "How many colors a graph needs" is a very well established term in computer science a…

I think the comment referred to the phrase „a graph needs X (colors or whatever)“. For me, this can be read two ways: 1. „a graph always needs at least X colors“ or 2. „a graph always needs at most X colors“.

Personally, I would interpret this as option 1 (and so did the comment above I assume). In that case, the statement is wrong. But I’d prefer to specify „at most/ at least“ anyways.

Or even better, use actual vocabulary. „For every graph there exists a coloring with X colors.“ or „any graph can be coloured using X colors“.

PS: I also agree with the sentiment about quanta magazine. It’s hard to get some actual information from their articles if you know the topic.

Re: The Fastest Way yet to Color Graphs

#15

Post by JohnKemeny »

mockerell wrote: post #14
JohnKemeny wrote: post #13

Earlier quoted context omitted.

Not really. Coloring a graph is almost always talking about proper coloring, meaning that things that objects that are related receive different colors. If you read the introduction, you'll also read that the goal is to "color each of your lines and require that for every point, no two lines connected to it have the same color." Ps. "How many colors a graph needs" is a very well established term in computer science a…

I think the comment referred to the phrase „a graph needs X (colors or whatever)“. For me, this can be read two ways: 1. „a graph always needs at least X colors“ or 2. „a graph always needs at most X colors“. Personally, I would interpret this as option 1 (and so did the comment above I assume). In that case, the statement is wrong. But I’d prefer to specify „at most/ at least“ anyways. Or even better, use actual voc…

What about this statement:

No matter how large a car is, it is easy to figure out how much money you'll need to buy it. Simply look at the price tag.

(From: 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 ...)

Re: The Fastest Way yet to Color Graphs

#16

Post by erikvanoosten »

meindnoch wrote: post #6
erikvanoosten wrote: post #3

Earlier quoted context omitted.

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.

Indeed. Thanks, I stand corrected.

Re: The Fastest Way yet to Color Graphs

#17

Post by mauricioc »

JohnKemeny wrote: post #15
mockerell wrote: post #14

Earlier quoted context omitted.

I think the comment referred to the phrase „a graph needs X (colors or whatever)“. For me, this can be read two ways: 1. „a graph always needs at least X colors“ or 2. „a graph always needs at most X colors“. Personally, I would interpret this as option 1 (and so did the comment above I assume). In that case, the statement is wrong. But I’d prefer to specify „at most/ at least“ anyways. Or even better, use actual voc…

What about this statement: No matter how large a car is, it is easy to figure out how much money you'll need to buy it. Simply look at the price tag. (From: 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 ...)

Parent's point is that sometimes (but not always) the store is perfectly fine selling you a car for $1 less than what the "price tag" of Delta(G)+1 dollars asks for, so "need" is a bit inaccurate.
Post reply on HN