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

Yeah, yeah, First Post, but...

[Emor dNilapasi]

1) Frist Psot!

2) I read the linked-to blurb(s)* and promptly got confused. I'm sure this is indeed some sort of breakthrough, but could some of the more mathematically-literate Slashdotters out there translate this into an explanation that the rest of us could understand? I'd particularly like to see exactly how this finding applies to real-world applications. Thanks in advance...

* - Why yes, I am new here - how did you know?

Comment removed

[account_deleted]

Comment removed based on user account deletion

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

[Anonymous Coward]

It probably isn't the best way to get from one point to another... but it *is* useful to go from an unknown starting point to a destination, which is the point of the problem. I could see that having applications - probably not in real-world navigation since we're not actually going to paint all the roads, but in (as the summary notes) internet routing.

Actually

[The MAZZTer]

He did it in 6.5 pages, the rest is references, whitespace at the very end, and the abstract and title.

Re:Night Watchman?

[reset_button]

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:HE'S NOT A WATCHMAN

[BattleApple]

It's just like the "psychologist" that entered the Netflix contest
http://developers.slashdot.org/article.pl?sid=08/03/04/2348257 [slashdot.org]

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

[kevinatilusa]

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.