# Implicit Hitting Set Problems and Multi-Genome Alignment

### Richard M. Karp

University of California at Berkeley

**Abstract**

Let U be a finite set and S a family of subsets of U. Define a hitting set as a subset of U that intersects every element of S. The optimal hitting set problem is: given a positive weight for each element of U, find a hitting set of minimum total weight. This problem is equivalent to the classic weighted set cover problem.We consider the optimal hitting set problem in the case where the set system S is not explicitly given, but there is an oracle that will supply members of S satisfying certain conditions; for example, we might ask the oracle for a minimum-cardinality set in S that is disjoint from a given set Q. The problems of finding a minimum feedback arc set or minimum feedback vertex set in a digraph are examples of implicit hitting set problems. Our interest is in the number of oracle queries required to find an optimal hitting set. After presenting some generic algorithms for this problem we focus on our computational experience with an implicit hitting set problem related to multi-genome alignment in genomics. This is joint work with Erick Moreno Centeno.

**Bio**

Richard M. Karp was born in Boston, Massachusetts on January 3, 1935. He 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. From 1968 to 1994 and from 1999 to the present he has been a Professor at the
University of California, Berkeley, where he held the Class of 1939 Chair and is currently a University Professor.
From 1988 to 1995 and 1999 to the present he has been a Research Scientist at the International Computer Science
Institute in Berkeley. From 1995 to 1999 he was a Professor at the University of Washington. During the 1985-86
academic year he was the co-organizer of a Computational Complexity Year at the Mathematical sciences research
Institute in Berkeley. During the 1999-2000 academic year he was the Hewlett-Packard Visiting Professor at the
Mathematical Sciences Research Institute. The unifying theme in Karp's work has been the study of combinatorial
algorithms. His 1972 paper, "**Reducibility Among Combinatorial Problems**", showed that many of the most commonly
studied combinatorial problems are NP-complete, and hence likely to be intractable. Much of his work has concerned
parallel algorithms, the probabilistic analysis of combinatorial optimization algorithms and the construction of
randomized algorithms for combinatorial problems.

His current activities center around algorithmic methods in genomics and computer networking. He has supervised thirty-six Ph.D. dissertations. His honors and awards include: U.S. National Medal of Science, Turing Award, 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 eight 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.