Alberto Apostolico Memorial Lecture: Richard M. Karp (UC Berkeley/Simons Institute)

Event Details
  • Date/Time:
    • Monday March 13, 2017 - Tuesday March 14, 2017
      11:00 am - 11:59 am
  • Location: KACB 1116 and Atrium
  • Phone:
  • URL:
  • Email:
  • Fee(s):
  • Extras:

Birney Robert or Dani Denton


Summary Sentence: Turing award winner speaking on March 13, 11am (Klaus 1116)

Full Summary: No summary paragraph submitted.

  • Richard M. Karp Richard M. Karp

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!)


Title:  The Colorful Connected Subgraph Problem


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).


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.

Additional Information

In Campus Calendar

School of Computational Science and Engineering, School of Computer Science, School of Interactive Computing, College of Computing

Invited Audience
Faculty/Staff, Public, Undergraduate students, Graduate students
Richard M. Karp, UC Berkeley, Georgia Tech, College of Computing
  • Created By: Birney Robert
  • Workflow Status: Published
  • Created On: Jan 12, 2017 - 2:47pm
  • Last Updated: Apr 13, 2017 - 5:13pm