Working with a team of dedicated graduate students, a University of Maryland professor has published a breakthrough paper on a longstanding mathematical challenge in graph design.
Mohammad T. Hajiaghayi, the Jack and Rita G. Minker Professor of Computer Science, led a team that cracked a mathematical quandary that has stumped scientists for more than 35 years. Known as the Steiner Forest problem, it’s based on a network optimization challenge where the goal is to find a minimum-cost subgraph that connects a set of terminal pairs in each graph.
Think of it this way: imagine you want to set up several lights in your living room, but to do so, you need to figure out the best way to connect the lights using electric wire, possibly through some shared junctions (called Steiner points). What if there was a mathematical formula to figure out the minimum amount of wire you needed to buy, so you could avoid a mess of cables while also saving cash?
This is where the Steiner Forest problem comes in. In mathematics and computer science, the use of network optimization algorithms can often determine the shortest way to connecting a set of points in a network. By applying a Steiner Forest solution, you can plan your lighting setup to be cost-effective and clean.
But the Steiner Forest problem has many more applications beyond helping you with home décor. Modern computer and AI chips contain millions of tiny transistors that need to be connected. Hajiaghayi and his team’s new Steiner Forest algorithm can help tech giants like Nvidia and Google design the shortest wiring paths between these components, thereby boosting performance, enhancing efficiency, and slashing costs and energy usage. In the era of artificial intelligence, this can allow these and other companies to create faster models that consume less power.
Despite its significance, the Steiner Forest problem has resisted improvements for years. In 1989, an algorithm was proposed that guaranteed the solution would cost no more than twice the optimal network—named the “2-approximation.”
Since then, scientists have produced solutions that are 60 or 90 times higher than the optimal cost. “But these results were still published because the problem is considered so central—and it was thought that even such solutions could help drive future improvements,” says Hajiaghayi, who has appointments in the University of Maryland Institute for Advanced Computer Studies, the Artificial Intelligence Interdisciplinary Institute at Maryland, and the University of Maryland Center for Machine Learning.
Assisting Hajiaghayi on the project were Ali Ahmadi, Iman Gholami, Mohammad Mahdavi, and Peyman Jabbarzade, all doctoral students in the university’s computer science program.
All four students are International Olympiad in Informatics medalists, a prestigious honor that recognizes secondary school students representing countries worldwide in a programming competition.
Hajiaghayi and his graduate students worked on the Steiner Forest problem for three years. The team faced numerous challenges, including dead-ends and “bad examples” that stalled their progress.
A paper on their work was published in the April 2025 issue of Journal of the ACM.
Their final effort required a 126-page proof, written over the course of four months. “Writing it was horrible,” admits Hajiaghayi. “Every detail had to be triple checked.”
The graduate students worked around the clock to meet a deadline for their work, but the stress was worth it. For Jabbarzade, collaboration was key: “The breakthrough came from working together with my peers—we couldn’t have done it alone.”
It was a risky undertaking—with no guarantee of their efforts coming to fruition. “These students gave up lucrative careers to come work on this problem with me,” says Hajiaghayi. “But now their efforts have paid off.”
Moving forward, the team is now eyeing other similarly tough problems—akin to the famous P versus NP question, the biggest unsolved problem in computer science. But for now, the UMD team is focusing on further refining their Steiner Forest algorithm.
—Story by Aleena Haroon, UMIACS communications group