## ICS 269, Fall 2005: Theory Seminar

# Measure and Conquer: Domination -- A Case Study

## Jeremy Yu Meng

### December 2, 2005, in CS 259

Abstract:

This talk will be a presentation of a paper
by Fedor V. Fomin, Fabrizio Grandoni, and Dieter Kratsch from ICALP 2005.

Davis-Putnam-style exponential-time backtracking algorithms are the most
common algorithms used for finding exact solutions of NP-hard
problems. The analysis of such recursive algorithms is based on the
bounded search tree technique: a measure of the size of the subproblems
is defined; this measure is used to lower bound the progress made by the
algorithm at each branching step. For the last 30 years the research on
exact algorithms has been mainly focused on the design of more and more
sophisticated algorithms. However, measures used in the analysis of
backtracking algorithms are usually very simple. In this paper we stress
that a more careful choice of the measure can lead to significantly
better worst case time analysis. As an example, we consider the minimum
dominating set problem. The currently fastest algorithm for this problem
has running time O(2^{0.850n}) on n-nodes graphs. By measuring the
progress of the (same) algorithm in a different way, we refine the time
bound to O(2^{0.598n}). A good choice of the measure can provide such a
(surprisingly big) improvement; this suggests that the running time of
many other exponential-time recursive algorithms is largely
overestimated because of a "bad" choice of the measure.