Hard in theory, easy in practice: Why graph isomorphism algorithms seem to be so effective
This article has been reviewed according to Science X's editorial process and policies. Editors have highlighted the following attributes while ensuring the content's credibility:
Graphs are everywhere. In discrete mathematics, they are structures that show the connections between points, much like a public transportation network. Mathematicians have long sought to develop algorithms that can compare any two graphs.
In practice, many algorithms always seem to work efficiently. But in theory, there is no guarantee. In an arXiv preprint, researchers from the Kwan Group at the Institute of Science and Technology Austria (ISTA) develop a method to understand why.
The difficulty of some mathematical problems lies in not knowing how hard they are. This is the case with an important problem in computer science called "graph isomorphism testing" whereby scientists use algorithms to test whether two graphs are the same.
In theory, it cannot be ruled out that the algorithms might run for longer than the age of the universe. But in practice, many algorithms seem to work just fine. Almost always. Why do these algorithms seem to be so effective?
