Dr. Ivan Hal Sudborough’s Paper from 1980 Given the Test of Time Award

UT Dallas Founders Professor Dr. Ivan Hal Sudborough and Dr. Burkhard Monien a professor at Paderborn University, Germany, were presented with the Test of Time Award at the 44th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2018) that was held last in June in Lübbenau, in Germany.  Their award was for their highly influential 1980 research paper titled “Bounding the Bandwidth of NP-Complete Problems.” The WG Conferences Test of Time Award recognizes highly influential papers from past WG conferences that have had a particular impact on the community. WG conferences aim to connect theory and applications by demonstrating how graph-theoretic concepts can be applied in various areas of computer science. The goal of these conferences is to present recent results and to identify and explore directions for future research. The workshop has been held each year since its early beginning, and thus, the first WG was organized in 1975. The award com­mittee looked at the papers that appeared in the first seven years of WG. From these, the committee selected papers that stood the test of time in a remarkable way, discussed the relative merits, and then, unanimously de­cided on a paper from the Sixth Workshop on Graph-Theoretic Concepts in Computer Science.  Drs. Sudborough and Monien are the first to be given the WG Conference Test of Time Award. The award committee consisted of Drs. H.L. Bodlaenger, R. Möhring, and G. Woeginger.

Drs. Sudborough’s and Monien’s paper truly stands the test of time as it was written 38 years ago and is still highly regarded. In the paper, Drs. Sudborough and Monien studied the complexity of a number of graph problems, and other problems when the graph has bounded bandwidth. A graph has the bandwidth at most k, if we can number the vertices from 1 to n, such that for each edge, the difference between the numbers of its endpoints is at most k. The authors show for several well-known NP-complete graph problems, that these become polynomial solvable when the bandwidth of the graph is bounded by a constant, and study the relative complexity of these problems. Also, for problems like SATISFIABILITY, they obtain a similar result when looking at the bandwidth of the graph that can be obtained by the connections between clauses and variables.

The result was the first in a long and important development in algorith­mic graph theory. A few years after the appearance of this WG paper, and its companion paper by Monien and Sudborough at The Annual ACM Symposium on Theory of Computing (STOC) in 1981, generalizations of this result were obtained. In the midst of the 1980s, several groups of au­thors, often independently, invited graph parameters associated with tree-like structures that allowed many NP-hard problems to be solved in polynomial time. Later, the equivalence of these concepts was observed, and the termi­nology was taken from the graph minors work by Robertson and Seymour, with the central concepts and terms being treewidth and tree-decomposition. These notions now play a central role in many graph-theoretic investigations, but also are used in practical applications. The number of papers where these concepts play a role is to be written with five digits; Google scholar lists over 18,000 papers containing the word treewidth. Graphs of bounded bandwidth have bounded treewidth.

“Thus, the award paper stands at the cradle of these developments, with the central insight that when the graph has a special structure with small separators everywhere al­lows dynamic programming and thus fast algorithmic solutions to otherwise hard problems there, on the typewriter written pages, of the WG 1980 pro­ceedings.  As WG community, we can be proud that our series of meetings contains this paper that so evidently stood the test of time. But of course, most proud can be the authors of the paper, with having about 40 years ago ideas that had such large impact,” noted one of the committee members.

Dr. Sudborough joined the UT Dallas faculty in 1985. Sudborough’s research team has solved numerous classical computer science problems, including besting a solution Bill Gates proposed years before Microsoft was established. Research areas include Telecommunication networks, parallel computation networks, efficient parallel (and sequential) algorithms, the structure of complexity classes, picture processing, automata and formal languages, graph/network algorithms (esp. embedding and layout problems), combinatorial problems (esp. sorting by prefix reversals), and computational biology. He earned his bachelor’s degree in mathematics from California State Polytechnic University, San Luis Obispo, master’s degree in mathematics from California State University, East Bay, and doctoral degree in computer science from Pennsylvania State University.

ABOUT THE UT DALLAS COMPUTER SCIENCE DEPARTMENT

The UT Dallas Computer Science program is one of the largest Computer Science departments in the United States with over 2,800 bachelors-degree students, more than 1,000 master’s students, 190 Ph.D. students,  52 tenure-track faculty members, and 41 full-time senior lecturers, as of Fall 2018. With The University of Texas at Dallas’ unique history of starting as a graduate institution first, the CS Department is built on a legacy of valuing innovative research and providing advanced training for software engineers and computer scientists.