Robert Endre Tarjan: If you want to prove something significant, you have to work on hard problems

„Mathematics is not just about solving problems. It’s about building ideas,“ says mathematician and computer scientist Robert Endre Tarjan from Princeton University. According to him, Borůvka's algorithm is a prime example of this. In the interview, he describes what makes graphs so fascinating and how modern mathematics and computer science continue to build upon Professor Borůvka's discovery.

5 Nov 2026 Adéla Lerchová

Photo: Adéla Lerchová

Prof. Robert Endre Tarjan

Tarjan is an American computer scientist and mathematician who works at Princeton University and several tech companies. He is best known for Tarjan's off-line least common ancestors algorithm and his work on minimum spanning tree algorithms, including a nearly linear-time algorithm for Borůvka's problem.

In 1986, he received the Turing Award for fundamental achievements in the design and analysis of algorithms and data structures. He is also the inaugural recipient of the Nevanlinna Prize and an ACM Fellow.

 

It is said that a hundred years ago, Professor Borůvka was ahead of his time by solving the minimum spanning tree problem. When did it become clear how important his discovery was?

I ran into it, I don't know how long ago, 40 or 50 years ago, and even at that time, it was clear that it was a very important algorithm. Well, it was overlooked for a very long time, but in the 70s and 80s people started noticing it. And they started building on it, doing it better.

It's interesting that the classical algorithms that were always taught when I was in college in the mid and late 60s were two other algorithms. One was by another Czech, Jarník, who was an even more famous mathematician who invented the algorithm that was later rediscovered, among others, by Dijkstra and Prim. And then there was another algorithm by Kruskal, at least attributed to Kruskal, and those were taught.

It turns out that Borůvka's algorithm is much nicer in some ways, particularly in that it's naturally parallelizable.

So when people started realizing that and got interested in large-scale computing operations, they rediscovered this algorithm, came back to it, and, as I said, built on it.

 

You yourself have created several significant graph algorithms and are renowned, among other things, for the nearly linear-time algorithm for Borůvka's problem. Why do people keep returning to Professor Borůvka, even though he was overlooked for such a long time?

It was the very first algorithm that was written down for finding minimum spanning trees, and it turns out to be the best one.

It was sort of forgotten for a while because in some ways the later algorithms are simpler, but they're more natural for sequential computation where you do one step after another, whereas Borůvka's algorithm is more natural for a parallel computing environment, although it's also very efficient sequentially.

I also think his paper was not necessarily well written, which might explain part of it.

Addition by Professor Nešetřil: When Borůvka worked on his algorithm in 1925 or 1926, the whole field was not developed yet. People at that time didn't talk about algorithms, they didn't even know what an algorithm was. His discovery is about graphs, but Borůvka talked about matrices and didn't know what a tree is in the problem of the so-called minimum tree, and didn't even know the word graph. That is why he described everything correctly, but lengthily. He was far ahead of his time.

 

And how did you, Professor Tarjan, get into graphs?

I was always fascinated by graphs. I was interested in the four-color problem before it was solved. Actually, back in high school I was wondering if I could figure it out.

The four-color problem was solved by Kenneth Appel and Wolfgang Haken in 1976. Using a mathematical construction, they reduced the problem to a finite number of cases, which were subsequently verified by a computer.

Mathematically, it was a very controversial result because hundreds of cases could practically no longer be checked manually, and without a computer it would have been complicated. On the other hand, the ideas behind it were very elegant.

When I was in high school, I had access to a digital computer and I experimented with some of these ideas before the proofs were actually produced. The ideas of how to put such proofs together were there, but you needed enough computing power plus enough experience to carry it out.

 

What were your first practical steps in exploring graphs during your studies?

At Stanford University, where I continued, I took a course taught by John McCarthy, one of the early pioneers of artificial intelligence. It was a course in symbolic programming in Lisp, and at the end of the year we had to work on a final project. One of the choices was to design an algorithm to test whether a graph is planar.

This brings us back to planar graphs, where you have a set of vertices and edges and you want to know if you can draw the graph so that no two edges cross. There is a famous mathematical characterization of nonplanar graphs by Kuratowski, which McCarthy suggested using as the basis for an algorithm, but that's not computationally efficient. You have to search too many configurations.

I got very interested in the topic and ran across a paper by another group of computer scientists who proposed an algorithm that could actually be implemented for the problem. I did it and proved that it has quadratic time complexity. I got an A for it in the course.

 

So you were interested in algorithms right from the start of your career?

Yes. During my studies, John Hopcroft from Cornell University came to Stanford University for a year, and I collaborated with him in the early days. We shared an office, talked about depth-first search (DFS) and graphs, and found some beautiful algorithms.

For my dissertation, I designed a linear-time algorithm for planarity testing using DFS. It kind of shocked people because they didn't think linear time complexity was possible, I think.

After that, I continued studying graph algorithms, dealing with data structures that can be used in graph algorithms, and network optimization problems. One example is the minimum spanning tree, followed by shortest path problems or network flows.

I focused on developing fast algorithms for various problems of this kind, and that's what I've been doing basically my whole professional career.

 

I suppose you are working on similar issues in your current research as well?

I'm still working on self-adjusting data structures, which is a kind of data structure that adjusts itself based on its usage. So they are self-optimizing to some extent.

I do it with a few people, including several mathematicians from Charles University. So that's another reason why I'm here, besides the 100th anniversary of Borůvka's algorithm itself.

 

When you look back at your career, what do you think is important for someone to make a breakthrough discovery?

I think it's important to work on hard and challenging problems.

Young researchers tend to jump on something, produce a quick result, publish it, and move on. It's natural to do that because there's pressure to get promoted, pressure to get a job, and so on.

If you want to prove something significant, though, you have to work on hard problems, take your time, and be patient.

 

And how is artificial intelligence projecting into research today? Could it ease the solution of such complex problems?

I think it allows us to clear a lot of busy work. But we still need creativity.

There's no strong evidence that these systems can start from scratch, find good problems, directions, and build concepts. That's really what mathematics is about. It's not just about solving problems. It's about building ideas. An example could be Borůvka's idea about graphs, which he didn't even know at his time.

All of these are things that contribute in a major way to the development of mathematics. New concepts and subsequent exploration of possibilities.


More articles

All articles

You are running an old browser version. We recommend updating your browser to its latest version.