zbMATH — the first resource for mathematics

Measure and conquer: Domination – a case study. (English) Zbl 1082.68866
Caires, Luís (ed.) et al., Automata, languages and programming. 32nd international colloquium, ICALP 2005, Lisbon, Portugal, July 11–15, 2005. Proceedings. Berlin: Springer (ISBN 3-540-27580-0/pbk). Lecture Notes in Computer Science 3580, 191-203 (2005).
Summary: 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.850 n}\)) 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.598 n}\)). 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.
For the entire collection see [Zbl 1078.68001].

68W05 Nonnumerical algorithms
68P05 Data structures
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Full Text: DOI