Jaroslav Nešetřil: Borůvka's name is perhaps the best-known Czech name in computer science

Prof. RNDr. Jaroslav Nešetřil, DrSc.

Nešetřil works as a professor of mathematics at the Faculty of Mathematics and Physics, Charles University. He specializes primarily in combinatorics, algebra, and theoretical computer science. He is the holder of many prestigious awards and the author of more than 350 academic articles.

This year marks one hundred years since Professor Otakar Borůvka, a prominent Czech mathematician, solved the minimum problem. What kind of task was he dealing with back then?

It was an optimization problem, what we today call discrete optimization and graph theory. The goal is to find connections of the shortest length in situations involving a larger number of locations in space or on a plane.

What was the original reason why Professor Borůvka decided to solve precisely the question of the minimum spanning tree?

Jindřich Saxel, an employee of the West Moravian Power Plants, approached him back then with a question on how to connect a few villages using the shortest possible connections. The electrification of southern Moravia was just beginning.

Borůvka solved the problem around 1925 and found a procedure that is fast and relatively easy to use. Much later, it became an important problem in computer science that is studied to this day. And Borůvka was actually the first in the world to solve the problem.

You mentioned that the problem only became significant much later. What did the discovery mean for the society of that time?

For the society of that time, his discovery probably meant nothing. However, Borůvka correctly suspected that it was an important problem. In its day, electrification was a topic similar to what artificial intelligence is today. Everyone was talking about it, and it was a topical issue.

It is surprising that at a time when Borůvka was a young, employed, and highly successful mathematician with a launching career and upcoming trips to France and Germany, he found the time to solve precisely this problem. He was interested in it, and it testifies, among other things, to his good intuition.

However, he never followed up on his solution again – he went on to pursue other things.

Yet when he solved and published the problem, Vojtěch Jarník – another prominent mathematician living in Prague who also found a simple solution using a different procedure – immediately responded to him.

Otherwise, both of them were thirty years ahead of their time. The problem only became famous with computer science and the further development of the 1950s.

So back then, other mathematicians simply didn't deal with the problem very much?

Yes, not at the time. It was a topic that subsequently emerged gradually among mathematicians and perhaps also other scientific disciplines. They followed up on it in Germany and France as well, where they also dealt with the question.

From a mathematical standpoint, however, it was a relatively exotic question at that time. Scientists only began to study it more intensively in the 1950s.

And from your perspective as an expert in combinatorics and graph theory, how would you describe why Borůvka's work is so pivotal?

It is foundational work that appears in every textbook. There are also various solutions to the problem, sometimes even under different names.

It seems, however, that Borůvka's algorithm is flexible and very well suited for so-called parallel computers. And it remains an open problem how to find the fastest possible algorithm. The problem is not solved to this day; there is no known linear algorithm for it yet. The topic is therefore still very current today.

How much did the solution to the minimum spanning tree problem make Professor Borůvka famous worldwide?

Borůvka's article is highly cited, even though it was published in a marginal journal. Both Kruskal's and Prim's work, which are among the first papers in the 1950s, cite him.

Thanks to his algorithm, Borůvka's name is perhaps the best-known Czech name appearing in classical computer science.

I wrote several articles about him with my wife. We wanted to explain that Borůvka was an important mathematician and that he knew what he was doing. The publication in which we described his algorithm is one of my most cited and has about five hundred citations. It shows how famous Borůvka became and how well-known he is to every computer science student around the world.

Why is the minimum problem interesting from a contemporary perspective as well?

It is interesting because it is a classic task that is taught, and the entire field of computer science is illustrated through it. When students enter their first year, they learn something about graphs and then receive assignments on them. And the minimum spanning tree problem is precisely one of the fundamental tasks.

At the same time, however, there are various other variants that are very useful and are specified by additional conditions that can no longer be described so simply. These are relevant to this day, as there are many variants. But they are always based on the solution that Borůvka came up with a hundred years ago.

And what does Borůvka's story tell us about himself and about the fact that he was far ahead of his time with his solution to the minimum problem?

I think Borůvka's example is very interesting because it shows that he was a strong mathematician who lived in good company. We also had a number of other experts here, such as Professor Vladimír List, who was an expert in electrical engineering and a later rector of the Brno University of Technology (VUT).

For when Borůvka returned to the Czech lands after the First World War, he studied at VUT, because Masaryk University (MU) did not yet exist when he entered higher education.

As soon as MU was founded, his teacher from VUT, Matyáš Lerch, transferred there and thus became the first professor of mathematics at MU. Borůvka was his assistant.

Unfortunately, Lerch died very early, in 1922, and Eduard Čech succeeded him in his position. He was the main figure of Czech mathematics at the time, and Borůvka was fortunate once again to be able to become his assistant.