Become a fan of Slashdot on Facebook

 


Forgot your password?
Close
typodupeerror
×
Math Science

Road Coloring Problem Solved 202

Posted by kdawson from the hard-but-not-complicated dept.
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."
This discussion has been archived. No new comments can be posted.

Road Coloring Problem Solved More

Road Coloring Problem Solved

Comments Filter:

  • The writeup is misleading (Score:5, Informative)

    by karl marx is my hero ( 1222496 ) on Friday March 21, 2008 @08:42AM (#22818422)
    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.
    • and Albert Einstien worked in a patent office.

      Where one works isn't always a sign of ones abilities.
      • The point being made here is that him working as a security guard is in no way relevant.
        He's been teaching at the Bar-Ilan university since 1995.
        The summary makes it sound like he was a security guard doing math in his spare time.

    • The parent is misleading (Score:4, Informative)

      by PDAllen ( 709106 ) on Friday March 21, 2008 @03:41PM (#22823518)
      The road colouring problem is not 'an equation'.

      'deterministic automaton' basically means: computer program which doesn't have any form of randomness involved. If you're in this particular state in the program and you do this particular thing then always the same thing happens.

      The road colouring problem amounts to: For any program, I claim that there is one single sequence of actions so that if you do this sequence of actions, from whatever start point, when you finish you will be in a specific state (`target', say) of the program.

      If you take any real normal program, it's `obvious' what to do: for example if you're looking at 'edit' and you want a typed copy of Shakespeare in Times 12pt, you hit backspace as many times as edit can have characters (lots, but it's a finite number) then you go through the menus by keypress and set each style to the correct thing, then you start typing in the works of Shakespeare which eventually gives you the target state. And it doesn't matter if the monitor was off, you know that this method definitely works, whatever state edit was in when you got there, whether it was in the blank just loaded state, or whether it was editing font size in War and Peace, whatever.

      It is not so easy to prove that in fact for any program you can find such a sequence.

      In fact, it isn't even true. A really simple example is the program which every time you press a key changes the screen between red and blue. Now you're supposed to give a sequence of actions - keystrokes - which are guaranteed to end up with the screen blue (target state). But really what the keystrokes are is irrelevant. This program doesn't care if you press 'a' or 'ESC', it just changes screen colour every stroke. So really your sequence of actions comes down to 'press keys however many times'. How many times? Well, if the screen starts red (and remember the monitor is off, so you don't know if that's true) then you'd need to press keys an odd number of times to get it to end up blue. So you have to do that. But then what happens if the screen started blue? It ends up red. This sequence of actions doesn't always reach the target state - and there cannot be any sequence of actions which does.

      So you have to impose a condition to make the result true. In the example I gave, the program has two states and it loops between them. It's a program with exactly one loop, of length two, and the greatest common divisor (GCD) of these loops is of course 2. Basically, having the ability to loop between states like this (or in a loop of length 3, or 4, or whatever) is the only 'obvious' barrier to having a sequence of actions which goes to a target state. So you impose a condition: the GCD of all the loops is 1 (this doesn't mean there are no loops, but the guy proves it means you can find a way out of all the loops). If you don't have that, then you can find automatons (programs) which work like the example and you cannot possibly have the sequence of actions you need. If you do have it, there is no 'obvious' barrier to the sequence of actions existing. And what this paper shows is that there isn't any hidden catch: once you get rid of the 'obvious' barrier then you can find a sequence of actions which definitely puts the program you're looking at into the target state.

  • Comment removed (Score:4, Interesting)

    by account_deleted ( 4530225 ) on Friday March 21, 2008 @08:44AM (#22818464)
    Comment removed based on user account deletion

    • Re:Applications? (Score:5, Informative)

      by MightyYar ( 622222 ) on Friday March 21, 2008 @10:05AM (#22819430)
      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.

      • Re: (Score:2)

        by Hatta ( 162192 )
        How is that not obvious then? A finite number of paths gives you a finite number of routes, then just brute force them all.
        • The example in Wikipedia [wikipedia.org] does a far better job than I can.

          Basically, if you called me up on the phone I could give you directions without knowing where you started from:
          1. Take the blue road.
          2. Take the red road.
          3. Take the next red road.

          Now, if you started in the node next to mine, this is not an efficient route - but it sure does simplify directions. I could see how it could also help routing if one of the paths is damaged... if you get to a broken "road", just start over from the first instruction and yo

          • Re: (Score:2)

            by Hatta ( 162192 )
            I'm not surprised that it can be done, I'm surprised it wasn't trivial to prove. Again, if there are a finite number of paths, there must be a finite number of routes (combinations of paths). So just try them all.

            • . Again, if there are a finite number of paths, there must be a finite number of routes (combinations of paths). So just try them all.

              Again, I'll refer you to the Wikipedia article. It's not quite that simplistic. The real meat of the (is it still a conjecture?) is:

              Every finite strongly-connected aperiodic directed graph of uniform out-degree has a synchronizing coloring.

              So it describes the exact conditions that a system must meet in order for this behavior to be described. Not just any collection of connected points will have such a solution - so no, it's not obvious :)

              Then again, I'm in waaaaay over my head here - I am but a bachelors

    • Re: (Score:2)

      by Zakabog ( 603757 )
      I hope never, I don't want to potentially drive through my destination 20 times to get to it. This doesn't create an efficient route, it just creates a guaranteed route. The instructions might be, turn left, turn right, turn left. Now repeat 40 times and you're guaranteed to get to New York from wherever you started.
    • Never.

      The whole point of having a GPS unit is so that you know your starting location.

      If the result apply to 3D spaces, I would say it'll probably have some implication for biotech or nanotech assembley as guidance clues for stem cells or nannites. I'd say it's more likely to be nanotech though, since we already have better ways to guide cells.
    • The classic maze solution treats the maze as a graph of degree-out 2 decision points (left,right). The classic formulation is to keep your hand on the right hand wall. This fails, of course, when you are inside of a loop. However, this theorem says that while the instruction (right) may fail for such mazes, there exists some longer instruction, say (left,right,left) that will exit the maze regardless of starting point. Some classic myths can now be updated. Instead of our hero relying on a ball of stri

    • It's a theorem (Score:4, Insightful)

      by pikine ( 771084 ) on Friday March 21, 2008 @10:52AM (#22820078) Journal

      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. (Score:5, Funny)

    by Rob T Firefly ( 844560 ) on Friday March 21, 2008 @08:51AM (#22818552) Homepage Journal
    Unfortunately for him, a cheap, safe, mass-market flying car was announced an hour later.

  • Link to the solution (Score:5, Informative)

    by wiredog ( 43288 ) on Friday March 21, 2008 @08:51AM (#22818554) Journal
    Since the one in the write-up is borken. Here [arxiv.org] it is.

  • wikipedia (Score:5, Informative)

    by ZiggyM ( 238243 ) on Friday March 21, 2008 @08:58AM (#22818638)
    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]

  • A Subquadratic Algorithm for Road Coloring (Score:5, Informative)

    by Frans Faase ( 648933 ) on Friday March 21, 2008 @09:03AM (#22818694) Homepage
    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? (Score:5, Insightful)

    by amplt1337 ( 707922 ) on Friday March 21, 2008 @09:04AM (#22818704) Journal
    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: (Score:3, Funny)

      by huckamania ( 533052 )
      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.

      No, they're just applying the normal slashdot skepticism. The guy was a security guard for crying out loud. And he's old. Really old. No way he could have used his brain to solve something involving math. Besides, he's probably only trying to get seed money so he can start a pyramid scheme selling perpertual motion.
    • From the description and picture listed on Wikipedia it seems to me that this method is only possible if every single road is a one-way street. This is hardly a realistic situation except in downtown parts of the largest cities.

      • Re: (Score:2, Insightful)

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

        • Re: (Score:3, Funny)

          by Reason58 ( 775044 )
          But when you get to that point, it loses all meaning. R on Lincoln L on 1st St L on R Ave R on Prescott How is that any harder than saying: Orange Burnt Amber Sanguine Desire Ghost Egg White Not to mention the more complicated the street system the more colors you would need and that would cause extreme confusion as people try and tell shades apart.

    • Re: (Score:2)

      by sconeu ( 64226 )
      From the "what-have-they-ever-done-for-us" department:

      In other words, the Romans were right, and "All roads lead to Rome"?

  • Actually (Score:3, Interesting)

    by The MAZZTer ( 911996 ) <megazztNO@SPAMgmail.com> on Friday March 21, 2008 @09:09AM (#22818752) Homepage
    He did it in 6.5 pages, the rest is references, whitespace at the very end, and the abstract and title.

  • Sign of a true Genius. (Score:5, Insightful)

    by Lumpy ( 12016 ) on Friday March 21, 2008 @09:10AM (#22818756) Homepage
    "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. (Score:4, Funny)

      by Jamil Karim ( 931849 ) on Friday March 21, 2008 @10:59AM (#22820166)

      The man is a True Genius.
      Real Men of Genius!
      Today, we salute you, Mr. former-nightwatchman-turned-mathmetician!
      • Actually he was Jew in Soviet Union, and somewhat managed to have a scientific career, suffered the implosion of the USSR, flewd to Israel, and it took him a lot of time to find a job as a professor there, so in the meanwhile he had to work as a security guard to put food on his table. But at the time he wrote the proof he already had gotten a job.

        Of course, his acchievements prove that he is not a loser like those bastards who can't even RTFA before posting.

  • HIRED! (Score:3, Funny)

    by TheGreatOrangePeel ( 618581 ) on Friday March 21, 2008 @09:18AM (#22818856) Homepage
    Well, SOMEONE is about to be hired by google... ...you suppose it's too late to learn Russian, and become his friend?

  • The conjecture essentially assumed it's possible to create a "universal map" that can direct people to arrive at a certain destination, at the same time, regardless of starting point. Experts say the proposition could have real-life applications in mapping and computer science.

    If a thousand people arrive at a shopping mall, at the same time, isn't that called a flash mob [wikipedia.org]? Then I guess this conjecture has already been solved online, and it is called Slashdot.

  • Given this graph [wikipedia.org], what about the 'traps' that exist for directions 'rrr' and 'bbb'? If you number the nodes top to bottom, left to right as 1-8, nodes 1, 2, and 4 all are destinations for 'rrr' depending on your starting point. Similarly, nodes 6, 7, and 8 are all destinations for 'bbb' depending on where you start. Does the problem definition say you must follow the whole direction, i.e. you must always traverse 3 arcs, or is it 'legal' to stop when you've reached your destination (assuming you know where

    • Re: (Score:2)

      by njh ( 24312 )
      Yes, I was puzzling over that too. It seems that you must have some other way to know where you are to distinguish those rrr and bbb cases. So the colours do not give an index, only a route that will eventually pass through the destination. Can it be fixed by adding more colours (obvious choice is to use the same encoding twice, but I can't see how to couch that in terms of single colours)?

  • Washington - RNC ??? (Score:3, Funny)

    by zappepcs ( 820751 ) on Friday March 21, 2008 @09:45AM (#22819178) Journal

    "Say you've lost an e-mail and you want to get it back -- it would be guaranteed," he said. "Let's say you are lost in a town you have never been in before and you have to get to a friend's house and there are no street signs -- the directions will work no matter what."
    I wonder if this can be retroactively applied to certain email servers in Washington?
    • I have derived an interesting algorithm to achieve this; unfortunately, this post is too small to contain it, and it involves an infinite number of monkeys trained to use word processors.

  • so.. (Score:2, Funny)

    by g0dsp33d ( 849253 )
    That means my screensaver could be an Internet network diagram?

  • What is road-coloring (and why we should care) (Score:5, Interesting)

    by kevinatilusa ( 620125 ) on Friday March 21, 2008 @10:47AM (#22820004)
    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! (Score:5, Funny)

    by Teilo ( 91279 ) on Friday March 21, 2008 @11:46AM (#22820892) Homepage
    Proof at last, that that guy who kept saying, "You can't get there from here" is a bloody liar.

  • and the evil professor says ... (Score:3, Funny)

    by B3ryllium ( 571199 ) on Friday March 21, 2008 @12:44PM (#22821732) Homepage
    Now adjust the algorithm for colour-blindness! :)

    Show your work.
  • I clearly remember my parents getting Triptick maps from AAA for our annual sojourn to Florida. Those multipage maps had roads colored in nicely, and you just followed them to your destination.

    Have mathematicians scraped the bottom of the barrel for unsolved puzzles? Oh, damn. I think I just created something for mathematicians to ponder for the next few decades...

  • In related news .... (Score:4, Funny)

    by PPH ( 736903 ) on Friday March 21, 2008 @01:17PM (#22822054)
    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.
  • Isn't that just amazing. Some of the best gems are often found in the rough. A genius working to make a living solves a problem that will help all humanity in some way. Good for him.

Slashdot Top Deals

Life is a game. Money is how we keep score. -- Ted Turner

Close