# A measure & conquer approach for the analysis of exact algorithms

@article{Fomin2009AM, title={A measure \& conquer approach for the analysis of exact algorithms}, author={F. Fomin and Fabrizio Grandoni and Dieter Kratsch}, journal={J. ACM}, year={2009}, volume={56}, pages={25:1-25:32} }

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… Expand

#### 233 Citations

Design by Measure and Conquer: Exact algorithms for dominating set

- Mathematics
- 2009

The measure and conquer approach has proven to be a powerful tool to analyse exact algorithms for combinatorial problems, like Dominating Set and Independent Set. In this paper, we propose to use… Expand

Design by Measure and Conquer, A Faster Exact Algorithm for Dominating Set

- Computer Science, Mathematics
- STACS
- 2008

Design by measure and conquer is proposed to be a form of computer aided algorithm design, thus giving a new, possibly faster algorithm in the design of algorithms. Expand

Exponential Time Algorithms - Structures, Measures, and Bounds

- Computer Science
- 2010

This book studies exponential time algorithms for NP-hard problems, to design algorithms for combinatorially hard problems that execute provably faster than a brute-force enumeration of all candidate solutions. Expand

Parameterized Measure & Conquer for Problems with No Small Kernels

- Mathematics, Computer Science
- Algorithmica
- 2011

Using M&C in this context will allow us to improve on the hitherto published running times of parameterized algorithms based on the idea of first enumerating minimal vertex covers, which will use polynomial space. Expand

Inclusion/Exclusion Meets Measure and Conquer

- Mathematics, Computer Science
- Algorithmica
- 2013

This paper shows that inclusion/exclusion as a branching rule can be combined in a branch-and-reduce algorithm with traditional branching rules and reduction rules, and obtains the currently fastest exact exponential-time algorithms for a number of domination problems in graphs. Expand

Separate, Measure and Conquer: Faster Polynomial-Space Algorithms for Max 2-CSP and Counting Dominating Sets

- Mathematics, Computer Science
- ICALP
- 2015

The design is the design of a general method to integrate the advantage from the separator-branching into Measure and Conquer, for an improved running time analysis. Expand

Exactly Solving the Maximum Weight Independent Set Problem on Large Real-World Graphs

- Computer Science
- ALENEX
- 2019

This work develops a full suite of new reductions for the maximum weight independent set problem and provides extensive experiments to show their effectiveness in practice on real-world graphs of up to millions of vertices and edges and shows that combining kernelization with local search produces higher-quality solutions than local search alone. Expand

Branch-and-Reduce Exponential/FPT Algorithms in Practice: A Case Study of Vertex Cover

- Computer Science
- ALENEX
- 2015

The results indicate that branch-and-reduce algorithms are actually quite practical and competitive with other state-of-the-art approaches for several kinds of instances, thus showing the practical impact of theoretical research on branching algorithms. Expand

Exploiting structure to cope with NP-hard graph problems : polynomial and exponential time exact algorithms

- Computer Science
- 2010

This thesis presents several polynomial time algorithms for solving restrictions of these problems to specific graph classes, in particular graphs without long induced paths, chordal graphs and clawfree graphs. Expand

Measure and Conquer : Analysis of a Branch-and-Reduce Algorithm for the Maximum Bounded-degree-1 Set Problem

- 2012

Recently Measure and Conquer is used to obtain tighter bounds of running time of branch-andreduce algorithms. A graph is bounded-degree-1 if its maximum degree is less than or equal to one. The… Expand

#### References

SHOWING 1-10 OF 122 REFERENCES

Measure and conquer: a simple O(20.288n) independent set algorithm

- Computer Science, Mathematics
- SODA '06
- 2006

This paper applies the "Measure and Conquer" approach to the analysis of a very simple backtracking algorithm solving the well-studied maximum independent set problem, and shows that a good choice of the measure can have a tremendous impact on the running time bounds achievable. Expand

Measure and Conquer: Domination - A Case Study

- Computer Science
- ICALP
- 2005

Davis-Putnam-style exponential-time backtracking algorithms are the most common algorithms used for finding exact solutions of NP-hard problems; the running time of these algorithms is largely overestimated because of a “bad” choice of the measure. Expand

Labeled Search Trees and Amortized Analysis: Improved Upper Bounds for NP-Hard Problems

- Mathematics, Computer Science
- Algorithmica
- 2004

This paper uses amortized analysis to show how simple algorithms, if analyzed properly, may perform much better than the upper bounds on their running time derived by considering only a worst-case scenario. Expand

Design by Measure and Conquer, A Faster Exact Algorithm for Dominating Set

- Computer Science, Mathematics
- STACS
- 2008

Design by measure and conquer is proposed to be a form of computer aided algorithm design, thus giving a new, possibly faster algorithm in the design of algorithms. Expand

SAT Local Search Algorithms: Worst-Case Study

- Mathematics, Computer Science
- Journal of Automated Reasoning
- 2004

Both upper and lower bounds of the form 2α n (α<1 is a constant) are proved for local search algorithms, and the class of linear-size formulas considered for the upper bound covers most of the DIMACS benchmarks; the satisfiability problem for this class of formulas is NP-complete. Expand

Algorithmics in Exponential Time

- Computer Science, Mathematics
- STACS
- 2005

The purpose of the current paper is to show cases in which the constant c could be significantly reduced, and to point out that there are some randomized exponential-time algorithms which use randomization in some new ways. Expand

On Exact Algorithms for Treewidth

- Computer Science
- ESA
- 2006

It is proved that using more refined techniques with balanced separators, TREEWIDTH can be computed in O(2.9512n) time and polynomial space and it is shown that the space used by the algorithm is an important factor to what input sizes the algorithms is effective. Expand

Exponential Lower Bounds for the Running Time of DPLL Algorithms on Satisfiable Formulas

- Computer Science, Mathematics
- SODA '04
- 2004

DPLL (for Davis, Putnam, Logemann, and Loveland) algorithms form the largest family of contemporary algorithms for SAT (the propositional satisfiability problem) and are widely used in applications.… Expand

An Improved Exact Algorithm for the Domatic Number Problem

- Mathematics, Computer Science
- 2006 2nd International Conference on Information & Communication Technologies
- 2006

It is shown that the 3-domatic number problem can be solved for graphs G with bounded maximum degree Delta (G) by a randomized algorithm, whose running time is better than the previous bound due to Riege and Rothe (2005) whenever Delta(G) > 5. Expand

Improved Exponential-Time Algorithms for Treewidth and Minimum Fill-In

- Mathematics, Computer Science
- LATIN
- 2006

It is shown that the number of potential maximal cliques for an arbitrary graph G on n vertices is ${\mathcal O}^{*}$(1.8135n), and that all potential maximalCliques can be listed in ${\ mathcal O]^{*]$ (1.8899n) time. Expand