Alberto Apostolico Memorial Lecture

Richard M. Karp - University Professor at University of California, Berkeley; Director of the Simons Institute for the Theory of Computing; 1985 Turing Award Winner

Monday, March 13, 2017

Klaus 1116 - 11:00 am (lunch to follow in the Atrium. Please RSVP here!)

Livestream: http://www.cc.gatech.edu/event-webcast

Title:  The Colorful Connected Subgraph Problem

Abstract:   

A graph is given, together with a color assigned to each vertex. Many vertices may receive the same color. We consider the NP-hard problem of finding a connected subgraph with a minimum number of vertices, such that the subgraph must contain at least one vertex of each color. In particular, we are interested in perfect solutions, in which no color is repeated. Versions of the problem arise in the context of protein-protein interaction networks, social networks and sensor networks. The problem (or even a generalization in which the edges of the graph are weighted) can be solved by a dynamic programming in time polynomial in the size of the graph but exponential in the number of colors. It can also be represented by an integer program with polynomial-bounded numbers of variables and linear constraints. We present a simple fast heuristic algorithm and describe its performance on large 2-dimensional grid graphs, under various specifications of the number of colors and their frequency distribution, using a random model and a semi-random model. 

In the random model the color assignment is chosen uniformly at random among assignments with the given frequency distribution. The algorithm reliably gives near-perfect solutions, provided the distribution of color frequencies is not highly skewed.

In the semi-random model a random perfect solution is planted, and the completion of the color assignment is random.

Regardless of the frequency distribution the algorithm reliably produces perfect solutions. In this case we extend the algorithm to generate many perfect solutions, and report on its performance.

This is joint work with Manuel Torres (UC Irvine).

Bio:

Richard M. Karp attended Boston Latin School and Harvard University, receiving his Ph.D. in 1959. From 1959 to 1968, he was a member of the Mathematical Sciences Department at IBM Research. He is a University Professor at UC Berkeley and director of the Simons Institute for the Theory of Computing. He joined the Berkeley faculty in 1968 and has also been a faculty member at the University of Washington (1995-99) and a research scientist at the International Computer Science Institute in Berkeley (1988-1995 and 1999-2012).

Karp's research is on combinatorial algorithms, computational complexity, and algorithmic methods in genomics and computer networking. He has supervised 42 Ph.D. dissertations. Honors and awards include: U.S. National Medal of Science, Turing Award, Kyoto Prize, Fulkerson Prize, Harvey Prize (Technion), Centennial Medal (Harvard), Lanchester Prize, Von Neumann Theory Prize, Von Neumann Lectureship, Distinguished Teaching Award (Berkeley), Faculty Research Lecturer (Berkeley), Miller Research Professor (Berkeley), Babbage Prize and 10 honorary degrees. He is a member of the U.S. National Academies of Sciences and Engineering, the American Philosophical Society and the French Academy of Sciences, and a Fellow of the American Academy of Arts and Sciences, the American Association for the Advancement of Science, the Association for Computing Machinery, and the Institute for Operations Research and Management Science.