https://www.quantamagazine.org/the-fastest-way-yet-to-color-graphs-20250512/ * Physics * Mathematics * Biology * Computer Science * Topics * Archive * Blog * Columns * Interviews * Podcasts * Puzzles * Multimedia * Videos * About Quanta An editorially independent publication supported by the Simons Foundation. Follow Quanta Newsletter Get the latest news delivered to your inbox. Email [ ] [ ] Subscribe Recent newsletters Gift Store Shop Quanta gear * Physics * Mathematics * Biology * Computer Science * Topics * Archive * Saved Articles Create a reading list by clicking the Read Later icon next to the articles you wish to save. See all saved articles * Log out ----------------------------------------------------------------- Change password * * Type search term(s) and press enter [ ] What are you looking for? Popular Searches * Mathematics * Physics * Black Holes * Evolution Home The Fastest Way Yet to Color Graphs Read Later Share Copied! * Comments * Read Later Read Later algorithms The Fastest Way Yet to Color Graphs By Steve Nadis May 12, 2025 Researchers have devised a scheme for painting the edges of a graph that's almost as speedy as possible. Read Later [VizingsTheorem-crKristinaArmitage-Lede-scaled] Kristina Armitage/Quanta Magazine Introduction [nadis-1654x1720] By Steve Nadis Contributing Writer --------------------------------------------------------------------- May 12, 2025 --------------------------------------------------------------------- View PDF/Print Mode algorithms computer science graph theory randomness All topics [JoY-Ads-2024_Article] Here's a scary scenario: You've been put in charge of air traffic control at Newark airport near New York. You need to make sure every plane can taxi between the runway and its gate without hitting any other planes. Let's bring the power of mathematics to bear on your problem. First, create a big, abstract map of your airport. For each runway, taxiway and gate, mark a point. Then, for each airplane, draw a line connecting these points: If a plane has to go from runway 4L down taxiway K to gate C80, draw a line that connects the points for runway 4L, taxiway K and gate C80. Now for the most important part: avoiding collisions. You'll notice that every physical location has a lot of planes coming in and out of it -- a lot of lines connected to every point on your map, which researchers call a graph. To ensure that no two planes are in the same place at the same time, you can color each of your lines and require that for every point, no two lines connected to it have the same color. The colors represent times; by requiring all the colors converging at a single point to be different, you're preventing the planes from being at the same location at the same time. Now all you need to do is fill in the colors. In the case of an airport, it might be possible to do so by hand, even for a large airport such as Newark. But researchers commonly analyze graphs with billions or more connections. And so they've developed algorithms that assign colors for them. These algorithms, however, are slow and had been "stuck more or less the same for the last 40 years," said Sepehr Assadi, a computer scientist at the University of Waterloo in Canada. Sepehr Assadi in a blue sweater stands in front of a chalkboard explaining Vizing's theorem. Sepehr Assadi showed how to color certain graphs much faster than the previous fastest algorithm. Joe Petrik Then, in 2024, over the space of a few days, two different groups of researchers came out with new algorithms that were significantly faster than the old standard. Now a paper to be presented in June at the 2025 Symposium on Theory of Computing goes even further. It describes a nearly optimal algorithm -- one that's practically as fast as possible. Astonishingly, this new algorithm doesn't depend at all on the number of points in your graph, only on the number of lines. It no longer matters how large your airport is, only the number of paths taken by the planes. This new paper "almost completely solved the problem" said Anton Bernshteyn, a mathematician at the University of California, Los Angeles. It's "a milestone few would have predicted even a couple of years ago." Living on the Edge In 1964, a mathematician named Vadim Vizing proved a shocking result: No matter how large a graph is, it's easy to figure out how many colors you'll need to color it. Simply look for the maximum number of lines (or edges) connected to a single point (or vertex), and add 1. The problem of how to fill in those colors, however, proved to be a different beast. Vizing came up with his own coloring algorithm, but it was slow. He started by looking at the time it would take to color just one remaining edge of an otherwise fully colored graph. Coloring that edge could mean changing the colors of the edges adjacent to it, and changing the colors of the edges adjacent to them, and so on down the line. Vizing calculated that coloring a single edge could take -- at most -- an amount of time proportional to the total number of vertices, which he labeled n. If there are m edges overall, Vizing's algorithm yields a time for coloring the entire graph that's proportional to the product of m times n. That value held for about 20 years until work in the 1980s brought down the edge coloring time. The new value was proportional to m times the square root of n. But the techniques behind these improvements didn't lead to additional advances. Other researchers were unable to improve upon them any further, and progress stalled. : Martin Costa in a black shirt stands outside in front of green trees Martin Costa was part of a team that lowered the runtime of a graph coloring algorithm several times. Facundo Costa Then, in May 2024, Assadi posted a paper to the scientific preprint site arxiv.org that showed how to color a graph on the order of n^2 time -- a factor that depends only on the number of vertices. For certain graphs, where the number of vertices is much smaller than the number of edges, this is a huge improvement. Around the same time, a team unconnected to Assadi posted their own result that reduced the edge coloring time to the order of m times the cube root of n. They did it by finding a slightly faster way of coloring a single edge. In a follow-up paper, the team made a further refinement, leading to an overall runtime proportional to m times the fourth root of n. Over the summer, the group began to collaborate with Assadi and a new team member, Soheil Behnezhad of Northeastern University. But rather than striving for incremental improvements, they sought a more fundamental gain. "Once we found a way past that [old result]," Assadi said, "we didn't see any fundamental barriers ahead." The newly formed group decided to aim for the ultimate goal: the theoretical minimum time. The fastest you can go through the entire graph and just see what it looks like -- to note that this edge is red, the next one is blue and so forth -- is just m, the number of edges. Since you can't color edges faster than you can read them, that "linear time" m is the fastest possible coloring time as well. But to reach this speed, they couldn't rely on the same tactics they'd used in the previous papers. "We were aware that the techniques we'd introduced so far were useful to get some kind of improvement, but none of them actually had enough power to get the algorithm down to near-linear time," said Martin Costa, a doctoral student at the University of Warwick and the coauthor of several papers on edge coloring, including last year's advances. If they were to have any hopes of realizing that goal, Costa added, "we actually had to take a completely different approach." A Painting Primer The team realized that, from the 2024 papers back to Vizing himself, all the strategies suffered from the same bottleneck. Recall that Vizing assumed the worst-case scenario -- coloring the last possible edge in a graph and then having to change the colors of every other edge connected to it. "The previous work focused on trying to color that one last edge faster," Assadi said. "So instead, we used another way." Rather than trying to color one edge faster, they wanted to see how quickly multiple edges could be colored at virtually the same time. Soheil Behnezhad in a black tshirt stands in front of brown trees Soheil Behnezhad, together with Costa, Assadi and others, devised an algorithm that colors a graph nearly as fast as possible. Zlata Rezanova To do that, the team borrowed a concept from an unlikely source: home improvement. If you're going to repaint your walls, you first put down a coat of primer to bring them back to neutral. In the same way, the researchers tried to "prime" the graph -- to bring it into a new state that made it easier to color. They used randomization techniques to do this, essentially relying on the outcomes of numerous coin tosses to color most of the graph while leaving certain edges strategically uncolored. After the priming, these last areas could be painted simply and almost simultaneously. The team's speedy new algorithm can color a graph "near-linearly" -- on the order of m times the logarithm of m. "It's a breakthrough -- an amazing result," said Robert Tarjan, a computer scientist at Princeton University and a winner of the Turing Award, considered the field's highest honor. The team's strategy of priming the graph has proved groundbreaking. "This one new idea kind of changed everything," Tarjan said. David Wajc, a computer scientist at the Technion in Haifa, Israel, finds the result "inspirational" -- the culmination of decades of research dating back to the 1960s. Beyond Near Perfection Although theorists may be celebrating, it's not yet clear if this result will translate into any real-life speedups. While theorists generally don't care about constant factors, "in practice, they do matter," Behnezhad noted. The runtime that they achieved is proportional to m log m or, equivalently, a constant times m log m. "In this algorithm, that constant seems to be very small," he said. "That's one indication that this algorithm might be practical." Related: --------------------------------------------------------------------- 1. Computer Scientists Establish the Best Way to Traverse a Graph 2. Researchers Achieve 'Absurdly Fast' Algorithm for Network Flow 3. How Randomness Improves Algorithms 4. New Proof Settles Decades-Old Bet About Connected Networks In the meantime, the group is considering how to push their result even further. The researchers would like to see if they can achieve near-linear time without relying on any randomness. "It's theoretically interesting, and it also would be nice to know that your algorithm will always run in exactly this time, and there's no chance that it could ever be slow," Costa said. In addition, the team would like to see whether it's possible to remove that extra logarithmic term from their runtime in order to make the result not just nearly linear but exactly linear. "That is the difference between what we get and the best one can hope for," Assadi said, "but there are very few graph problems where we can actually remove that term." For Tarjan, eliminating randomization and the logarithmic term would certainly be interesting, "but those are both huge challenges," he said. "I think this result is going to be the state of the art for the foreseeable future." Share this article Copied! --------------------------------------------------------------------- Newsletter Get Quanta Magazine delivered to your inbox Subscribe now Recent newsletters [nadis-1654x1720] By Steve Nadis Contributing Writer --------------------------------------------------------------------- May 12, 2025 --------------------------------------------------------------------- View PDF/Print Mode algorithms computer science graph theory randomness All topics [JoY-Ads-2024_Article] Share this article Copied! --------------------------------------------------------------------- Newsletter Get Quanta Magazine delivered to your inbox Subscribe now Recent newsletters The Quanta Newsletter Get highlights of the most important news delivered to your email inbox Email [ ] [ ] Subscribe Recent newsletters Also in Computer Science Will AI Ever Understand Language Like Humans? A brain represented by neural networks The Joy of Why Will AI Ever Understand Language Like Humans? By Janna Levin +1 authors Steven Strogatz May 1, 2025 Read Later Science, Promise and Peril in the Age of AI Particles and lines converging artificial intelligence Science, Promise and Peril in the Age of AI By Michael Moyer +8 authors Ben Brubaker John Pavlus Mark Belan Jordana Cepelewicz Yasemin Saplakoglu Gregory Barber Elise Cutts Emily Buder April 30, 2025 Read Later Where Do Scientists Think This Is All Going? [AIWhereIsItGoing-crSallyCaulwell-Default] many worlds Where Do Scientists Think This Is All Going? By Michael Moyer April 30, 2025 Read Later Comment on this article Quanta Magazine moderates comments to facilitate an informed, substantive, civil conversation. Abusive, profane, self-promotional, misleading, incoherent or off-topic comments will be rejected. Moderators are staffed during regular business hours (New York time) and can only accept comments written in English. Show comments [SidneyNagel-cr] Next article Finding Beauty and Truth in Mundane Occurrences * About Quanta * Archive * Contact Us * Terms & Conditions * Privacy Policy --------------------------------------------------------------------- All Rights Reserved (c) 2025 An editorially independent publication supported by the Simons Foundation. Simons Foundation Log in to Quanta Use your social network Connect with Facebook Connect with Google or [ ] email [ ] password [*] Remember me [Log in] Forgot your password ? Don't have an account yet? Sign up Forgot your password? We'll email you instructions to reset your password [ ] email [Send] Change your password Enter your new password [ ] Password [ ] Retype new password [Send] Sign Up [ ] First Name [ ] Last Name [ ] Email [ ] Password [ ] Retype Password [Create an account] Creating an account means you accept Quanta Magazine's Terms & Conditions and Privacy Policy We care about your data, and we'd like to use cookies to give you a smooth browsing experience. Please agree and read more about our privacy policy.AGREEDISMISS