How do you schedule, in as few days as possible, thousands of students for hundreds of exams without anyone being scheduled for two exams at the same time? This is a hard problem to solve. Yet the problem of calculating the shortest distances amongst even tens of thousands of towns is easy to solve quickly.
For over five decades, mathematician Pavol Hell has been interested in understanding what makes some problems hard, while other similar sounding problems are easy. He recently retired from SFU, where he taught computing science and published prolifically, including some of the most highly cited mathematical papers.
Professor Hell began his studies at Charles University in Prague but chose to leave when the Soviet Union invaded Czechoslovakia in 1968. He was able to resume his studies in Canada, earning his MSc from McMaster University and his PhD at the Université de Montreal. After 1989 when the regime in Czechoslovakia changed, he was able to reconnect with his teachers and classmates at Charles University, and re-establish his research contacts there.
Professor Hell’s research interests took him from being trained as an algebraist interested in category theory, specializing in very abstract mathematical structures, to focusing on the particular category of graphs, and finally to working on graph algorithms. It’s a specialty useful for designing computer programs for many problems from creating efficient exam schedules, to calculating shortest distances.
Graph theory studies structures that represent simple relationships (edges consisting of two vertices) between objects (vertices) and is used to model and solve practical problems in many different fields. The above example of exam scheduling contains one of the most basic problems in graph theory, namely, how to colour the vertices with as few colours as possible so that no edge has both vertices of the same colour. This is also a hard problem, but one that graph theorists have studied for many years and for which they have developed many practical techniques. Hell worked on this problem in the 1970’s while teaching at UBC, and was able to adapt some of these techniques to the real problem of exam scheduling, improving the existing UBC schedules at the time.
Because of the simplicity of its structures, graphs are also uniquely suited to study why some problems are difficult and others are not. “It’s one thing to prove that a problem can be solved efficiently,” explains Hell, “But if you claim that a problem cannot be solved efficiently – how do you back that claim? How can you be sure someone could not come along and do it?” By the early 1970s a theory was taking shape, showing that certain problems were NP-complete, meaning they were at least as hard as some standard problems generally agreed to be hard. At the time, Hell was at Rutgers University in New Jersey and attended a series of lectures on the theory given by David S. Johnson of AT&T Bell Laboratories. Johnson was one of the most prominent champions of the theory and was at the time writing (with Mike Garey) a book that was to become the definitive work on NP-completeness.
One of the open problems presented by Johnson piqued Hell’s interest, since it was related to his category theory training. It concerned a generalization of colouring in which the colours also form a graph, and each edge must obtain adjacent colours. These are morphisms in the category of graphs.
Hell and former Prague classmate and long-time collaborator Jarik Nešetřil eventually solved Johnson’s problem, showing the problem was NP-complete with very simple exceptions. At approximately the same time, a similar result was proved about morphisms in a certain other category, and a comparison on these results suggested a natural conjecture, formulated by Moshe Vardi and Tomas Feder about structures in which such results hold. These results are dubbed dichotomies because they claim that the algorithmic problems are either efficiently solvable or NP-complete, that is they have a dichotomy of possible outcomes.
The “Feder-Vardi Dichotomy Conjecture” became a hot topic in theoretical computer science, and many top theoretical computer scientists, logicians, graph theorists, and algebraists devoted considerable efforts to its solution. As a by-product, Hell’s 1990 paper with Nešetřil on the complexity of H-colouring went viral, and many alternative proofs were developed. Hell notes that SFU colleague Andrei Bulatov was one of the two people who completed the journey, proving the Feder-Vardi Dichotomy Conjecture in 2017, more than a quarter century after its formulation.
In the meantime, Professor Hell has worked with many colleagues on proving dichotomies of many related problems, and so have many others. The entire area has enjoyed, and continues to enjoy, a great popularity, mostly for its theoretical appeal, although there are practical implications. “If you know that an efficient optimal algorithm does not exist, you can be satisfied with an approximate solution that is less than optimal, or use randomization in your algorithm,” says Hell. All aspects of graph morphisms enjoy a large following, partly due to a highly cited 2004 Oxford University Press monograph written by Hell and Nešetřil.
In his recent paper, Distance-two colorings of Barnette graphs, co-authored by Tomas Feder and Carlos Subi, Hell considered problems associated with certain polyhedra. Two old conjectures from the late 1800’s motivate research in the area, the celebrated four-colour conjecture, claiming that graphs arising from planar maps can always be coloured with four colours, and Tait’s conjecture claiming that all graphs arising from polyhedra have a cycle visiting every vertex exactly once.
This first conjecture was proved in the 1970s, but the research continues for other variants of colouring. The second conjecture was disproved in the 1940s but lead to many subsequent weaker conjectures, including two prominent conjectures of Barnette, each restricting the kind of polyhedra under consideration. The graphs associated with polyhedra are included among the graphs arising from planar maps, so both questions can be examined for them. The Barnette conjecture has recently been proved for the second kind of restriction, but remains open for the first kind. Hell’s results highlight the difference between the two kinds of polyhedra by examining one popular variant of the colouring problem – which turns out to be efficiently solvable for the second kind of restriction, but is NP-complete for the first kind.
In the process of studying the dichotomy questions Hell found he made an impact on modern graph theory. “I’ve noticed the graphs that correspond to problems that are solvable efficiently are often very nicely structured,” says Hell. This has led him deeper into analyzing specially structured graphs, a popular topic in modern graph theory. An example is the class of interval graphs, where vertices are time intervals and edges correspond to overlapping intervals. Scheduling satellite transmissions contains the problem of colouring interval graphs, and this happens to be a problem that can be solved efficiently, even though the problem is NP-complete for general graphs.
Interval graphs also have applications in bioinformatics because of the linear structure of DNA. The graphs themselves are of great theoretical interest and associated with an elegant theory. Hell found a way to discover more such results. “Proving NP-completeness of some variants of a problem leads one to focus on the remaining variants, and this is often where surprisingly elegant results can be developed,” he says. His research is now evenly divided between studying dichotomies and developing deeper understanding of such specially structured graphs.
Hell’s research into complexity dichotomies took place against the backdrop of an exciting period in the development of theoretical computer science, from the understanding of the essence of “computation” and the distinction between solvable and unsolvable problems, to the meaning of “efficient computation,” and the theory of NP-completeness. By illuminating these concepts, the field of theoretical computer science has helped contribute to the development of the information age and the explosive growth of computational technology, and will continue to have important implications into the future.
SFU's Scholarly Impact of the Week series does not reflect the opinions or viewpoints of the university, but those of the scholars. The timing of articles in the series is chosen weeks or months in advance, based on a published set of criteria. Any correspondence with university or world events at the time of publication is purely coincidental.
For more information, please see SFU's Code of Faculty Ethics and Responsibilities and the statement on academic freedom.