Road Coloring Problem Solved

ArieKremen writes "Israeli Avraham Trakhtman, a Russian immigrant mathematician who had been employed as a night watchman, has solved the Road Coloring problem. First posed in 1970 by Benjamin Weiss and Roy Adler, the problem posits that given a finite number of roads, one should be able to draw a map, coded in various colors, that leads to a certain destination regardless of the point of origin. The 63-year-old Trakhtman jotted down the solution in pencil in 8 pages. The problem has real-world implementation in message and traffic routing."

Comments

The writeup is misleading

[karl marx is my hero]

The guy is actually a mathematician who had to work as a security guard right after he immigrated to Israel, which is common for most immigrants. This guy had lots of formal training solving equations like this.

Re:XKCD

[Anonymous Coward]

No, today's XKCD is about the traveling salesman problem. They are very different.

Link to the solution

[wiredog]

Since the one in the write-up is borken. Here it is.

Re:Night Watchman?

[DirePickle]

He's in Israel, not the US, dude. Save your diatribe for another time.

wikipedia

[ZiggyM]

from Wikipedia: In the real world, this phenomenon would be as if you called a friend to ask for directions to his house, and he gave you a set of directions that worked no matter where you started from. http://en.wikipedia.org/wiki/Road_Coloring_Conjecture/

Re:wikipedia

[Stephan202]

Drop the trailing slash: http://en.wikipedia.org/wiki/Road_Coloring_Conjecture

Re:wikipedia

[Jasin Natael]

The problem is more constrained than that. Think about it more like this: You're in a town that's been planned very carefully. At any intersection, the possible roads away from that intersection are labeled with colors. I'll assume three colors, and that each intersection has exactly three roads leading away from it (the number of roads that lead into the intersection doesn't matter).

Your friend tells you that his address is "Red-Blue-Blue". This means that, no matter which intersection you start from, by repeatedly following these directions, you WILL end up at his house.

A Subquadratic Algorithm for Road Coloring

[Frans Faase]

Apart from the referenced paper being some months old, the author has an extended paper with an efficient algorithm. See A Subquadratic Algorithm for Road Coloring.

HE'S NOT A WATCHMAN

[mcmonkey]

If you RTFA (yes, I must be new here) he worked as a night watchman when he first moved to Isreal. He's been working in mathematics for over a decade.

Originally from Yekaterinburg, Russia, Trahtman was an accomplished mathematician when he came to Israel in 1992, at age 48. But like many immigrants in the wave that followed the breakup of the Soviet Union, he struggled to find work in the Jewish state and was forced into stints working maintenance and security before landing a teaching position at Bar Ilan in 1995.

You might as well say the 2002 Nobel prize in economics went to a lieutenant in the army. It's just a minor detail that he was a lieutenant 50 years before winning the prize.

Re:Applications?

[MightyYar]

Egads, please no! This only guarantees that you will arrive at a destination from an arbitrary start point. Even if you could somehow use it for Google directions, your route would be crazy. You could start out next door to your destination and it may take you a day-and-a-half of travel to finally wind up there as you tour all over the city. I can see this being interesting to networking, though. A guaranteed route somewhere from any start point sounds pretty cool, even if a bit inefficient.