*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
Alberto Apostolico Memorial Lecture
Richard M. Karp - Simons Institute/UC Berkeley
Monday, March 13, 2017
Klaus 1116 - 11:00 am
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 the 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).
His research is on combinatorial algorithms, computational complexity and algorithmic methods in genomics and computer networking. He has supervised forty-two 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 ten 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.
------------------------------------------------------------------------
Videos of recent talks are available at: https://smartech.gatech.edu/handle/1853/46836
Click here to subscribe to the seminar email list: arc-colloq@cc.gatech.edu
