2009/08/01 by Fedor V. Fomin, Fabrizio Grandoni, Dieter Kratsch · 5 citations
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Advanced Graph Theory Research #Formal Methods in Verification #Measure (data warehouse) #Algorithm #Backtracking #Divide and conquer algorithms #Computer science #Set (abstract data type) #Simple (philosophy) #Upper and lower bounds #Time complexity #Mathematics #Mathematical optimization #Data mining
paper · doi:10.1145/1552285.1552286
openalex publication_date 2009/08/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/28
For more than 40 years, Branch & Reduce exponential-time backtracking algorithms have been among the most common tools used for finding exact solutions of NP-hard problems. Despite that, the way to analyze such recursive algorithms is still far from producing tight worst-case running time bounds. Motivated by this, we use an approach, that we call “Measure & Conquer”, as an attempt to step beyond such limitations. The approach is based on the careful design of a nonstandard measure of the subproblem size; this measure is then used to lower bound the progress made by the algorithm at each branching step. The idea is that a smarter measure may capture behaviors of the algorithm that a standard measure might not be able to exploit, and hence lead to a significantly better worst-case time analysis. In order to show the potentialities of Measure & Conquer, we consider two well-studied NP-hard problems: minimum dominating set and maximum independent set. For the first problem, we consider the current best algorithm, and prove (thanks to a better measure) a much tighter running time bound for it. For the second problem, we describe a new, simple algorithm, and show that its running time is competitive with the current best time bounds, achieved with far more complicated algorithms (and standard analysis). Our examples show that a good choice of the measure, made in the very first stages of exact algorithms design, can have a tremendous impact on the running time bounds achievable.