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."

The writeup is misleading

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.

Applications?

How soon can we see this implemented in my Garman GPS unit or Google Maps?

Re:Applications?

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.

It's a theorem

It's a theorem which states that if a graph is strongly connected and aperiodic, then there exists a road coloring. It was conjectured by Weiss and proven by Trahtman 30 years later, which is what the article is about. A graph that is periodic may still have a road coloring, but that's not the scope of the theorem.

Most roads are strongly connected but periodic (not aperiodic), in the sense that you can drive around a block in 4 segments, and drive around 2 blocks in 6. The period in this case is 2. You can't guarantee a computer network to be aperiodic either. These graphs may still have a road coloring, but the theorem doesn't apply. Therefore, this theorem has little application in practice.

I haven't read the paper, but there are generally two ways to prove the theorem: (1) show a coloring algorithm that makes only the assumptions of strong connectivity and aperiodicity, or (2) show the contraposition, that if there is no road coloring, then it implies either the graph is not strongly connected or there is period. Only (1) is useful in practice because you have a method to generate road coloring and instructions to reach all vertices, but it's harder to verify that (1) is correct. (2) is not very useful because although you have a proof, but you don't end up with an algorithm that generates road coloring.

In practice, algorithms get things done. Proofs are only certificates.

Bad timing.

Unfortunately for him, a cheap, safe, mass-market flying car was announced an hour later.

Link to the solution

Since the one in the write-up is borken. Here [arxiv.org] it is.

wikipedia

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/ [wikipedia.org]

Re:wikipedia

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

Re:wikipedia

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

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 [arxiv.org].

Old news?

1. Here's wtf the problem even is [wikipedia.org], for those of us who aren't all up in the "mathematical curiosities" business. Basically the question is, for a specific kind of graph (where you can go from point A to a finite number of points B, C, or D, etc) can you label the possible paths from each point so that, starting from anywhere, you can follow an invariable rule that will get you to a specific destination point. (Check the link, the picture makes much more sense).

2. Apparently his proof was published last September. It's "news" because it's just now hitting the semi-mainstream press. You people fail at nerddom.

Sign of a true Genius.

"Some people think they need to be complicated. I think they need to be nice and simple."

The man is a True Genius. Insight to all of out out there, that is the proper way of thinking.

Re:Sign of a true Genius.

The man is a True Genius.

Real Men of Genius!
Today, we salute you, Mr. former-nightwatchman-turned-mathmetician!

What is road-coloring (and why we should care)

The question behind road coloring is this: Given a directed network with out-degree 2 (from any place you can get to exactly two other places), we want to color the edges leading out of each node red or blue so the following "universal directions" condition exists: For any final destination A, there is a set of directions (e.g. take red three times, then blue twice, then red again) that gets you to A no matter where you started from. It may not be the shortest path, but you'll get there. There is one obvious obstruction and one slightly less obvious obstruction: If your network is disconnected so you can't get to A from your starting point no matter what path you follow, you're clearly stuck. On the other hand, there's also a "periodicity" obstruction if all of the cycles of the graph are multiples of the same number. For example, suppose that you were trying to give universal directions for a square, where the roads in question connected every vertex to its two neighbors. If I want to go from my starting point to an adjacent vertex, I have to take an odd number of steps. If I want to go from my starting point to the opposite vertex, I have to take an even number of steps. This means I can't even know how many steps I have to take (let along which steps) unless I knew where I started. It was conjectured, and Trahtman showed, that these two are the only possible obstructions. In particular, he even gives an algorithm for figuring out how to label the roads quickly. I guess the applications I'd see in this are for algorithms and the design of autonomous systems. The idea here is that, if the robot gets stuck somewhere in a multi-step procedure, you may want it to restart from the beginning. However, this can be difficult if the robot does not know where it is in the procedure, or even where it is physically. Trahtman's algorithm could allow you to exchange some computation at the beginning of the procedure (which can be done before the robot goes out, for example), for this "reset" functionality. I don't know whether this is feasible or not though.

I knew it!

Proof at last, that that guy who kept saying, "You can't get there from here" is a bloody liar.

In related news ....

Based upon his ground-breaking research on the road coloring problem, night watchman Trakhtman has been promoted to the Department of Transportation pavement striping crew.

Re:XKCD

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

Re:Night Watchman?

In Soviet Russia they say that because Americans were so poor mathematicians, they had to invent the computer...

Re:Night Watchman?

It's way better to be good at math, though, if you have to pick one. Sure, computers are quite practical for solving difficult problems, but you don't get nearly as much insight from simulation as you do from deriving an analytical formula for something (assuming such a formula is possible).

True, but the math needed to draw one frame of Doom alone took me a week, and I still haven't finished filling the boxes on my sheet of graph paper.

HE'S NOT A WATCHMAN

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:Night Watchman?

According to Wikipedia [wikipedia.org], he is a mathematician at Bar-Ilan University in Israel. Here is his homepage [biu.ac.il] hosted by the university. Maybe he was a night watchman, but it looks to me like he's a professor now...

Re:Night Watchman?

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

Re:Yeah, yeah, First Post, but...

I am not a mathematician either, but I think being able to provide a pattern that allows you to reach any given point in the graph would allow for faster switching at the nodes (once you reach certain speeds switching becomes the bottleneck). The problem isn't concerned with efficiency but reachability, anyway.

Re:Actually

Actually, if he were to put it on a SD card, it'd take up less than 1 square inch...

Where's my PEDANTIC:-1 option?

Re:OK, but...

Forty-two.