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

Re:Night Watchman?

[Anonymous Coward]

And knowing the stupidity and exclusiveness in the USA about academics.....

He will stay a night watchman, because he does not have a USA degree and therefore shunned by the snooty upper educational society we have here.

It's pure bullshit how the USA punishes the educated that emigrate here that obviously are highly educated, but because they did not go to a "blessed" institution, you get to cook doughnuts instead of using that 12 year education in genetics. I know asian guys that have a background in education that makes most american educated PHD's I know look like 6th grade dropouts. but they cant get a job using their knowledge because "you were not educated in the USA".....

So they end up night watchmen, Grocery store clerks, or bank tellers. While back in their country they were educated as Doctors, Physicists, and scientists.

Old news?

[amplt1337]

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.

Re:Night Watchman?

[Anonymous Coward]

Come on AC, your premise is patently false. I'm at one of the finer educational institutes in the US, and we have people from all over the world who earned their Ph.D.s from all over the world. If you came from one of the highly respected universities throughout the world, and are brilliant, you will get a job. If you have your Ph.D. from the University of Lower Slobobia, of course its going to be difficult. The quality of education in places in Asia, India, and even Russia varies wildly from their best Universities to their worst. To put it into perspective, its kind of like getting your Ph.D. from the least respected institution here. You probably still won't have a job. At least not a good one.

Also, to suggest that the quality of medical education is similar between 2nd and 3rd world countries is utterly ridiculous. Their degree is still good provided they can pass the boards and certifications. Not many do.

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

[gomiam]

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.

Sign of a true Genius.

[Lumpy]

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

[Anonymous Coward]

"Unless you're suggesting that if a person born in Japan came to the U.S. and became a citizen they are somehow^H^H^H^H^H^H^H^H legally no longer j^H^H Japanese."

Fixed it for you.

Re:Old news?

[calebt3]

No, just consider every two-way street parallel one-way streets. Each half has it's own color.

It's a theorem

[pikine]

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.

Re:Night Watchman?

[Anonymous Coward]

Which makes a better headline?

Jewish Mathematics Professor Solves Road Coloring Problem.
-or-
Russian Immigrant Night Watchman Solves Road Coloring Problem.