4pm Tuesday 4th June 2002
Room 2511, JCMB, King's Buildings
Paul Erdoes (1913-1996) is a well-known mathematician, who has worked in combinatorics, number theory, and other areas, and has published more than 1500 papers. But what is parameterized complexity theory? And what does Erdoes have to do with it? To answer the second question first - to the best of my knowledge, Erdoes has nothing to do with parameterized complexity theory. Parameterized complexity theory is a relatively new branch of computational complexity theory that provides a framework for a refined complexity analysis of algorithmic problems that look intractable at first sight. In recent years, it has found its way into various areas of computer science such as database theory, artificial intelligence, and computational biology.
This talk is going to be an introduction into a few new algorithmic and complexity theoretic ideas that have evolved out of parameterized complexity theory. To illustrate these ideas, we consider a graph whose vertices represent scientific authors, with an edge between two vertices if the the two authors have published joint paper. Paul Erdoes, with over 500 co-authors, is represented by a vertex of particularly high degree. The Erdoes number of an author is its distance from Erdoes in this graph. (I'm serious, see http://www.acs.oakland.edu/~grossman/erdoshp.html.) Computing the Erdoes number of an author is algorithmically easy, but there are related problems that are much more interesting: For example, suppose we want to rank all authors of Erdoes number k by the number of different paths connecting them with Erdoes. Can we do this efficiently?