A measure & conquer approach for the analysis of exact algorithms

ABSTRACT

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.

REFERENCES

• 1: Michael Alekhnovich , Edward A. Hirsch , Dmitry Itsykson, Exponential Lower Bounds for the Running Time of DPLL Algorithms on Satisfiable Formulas, Journal of Automated Reasoning, v.35 n.1-3, p.51-72, October 2005 [doi>10.1007/s10817-005-9006-x]
• 2: Richard Beigel, Finding maximum independent sets in sparse and general graphs, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.856-857, January 17-19, 1999, Baltimore, Maryland, United States
• 3: Richard Beigel , David Eppstein, 3-coloring in time O(1.3289ⁿ), Journal of Algorithms, v.54 n.2, p.168-204, February 2005 [doi>10.1016/j.jalgor.2004.06.008]
• 4: Andreas Bjorklund , Thore Husfeldt, Inclusion--Exclusion Algorithms for Counting Set Partitions, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.575-582, October 21-24, 2006 [doi>10.1109/FOCS.2006.41]
• 5: Hans L. Bodlaender , Fedor V. Fomin , Arie M. C. A. Koster , Dieter Kratsch , Dimitrios M. Thilikos, On exact algorithms for treewidth, Proceedings of the 14th conference on Annual European Symposium, p.672-683, September 11-13, 2006, Zurich, Switzerland [doi>10.1007/11841036_60]
• 6: Tobias Brueggemann , Walter Kern, An improved deterministic local search algorithm for 3-SAT, Theoretical Computer Science, v.329 n.1-3, p.303-313, 13 December 2004 [doi>10.1016/j.tcs.2004.08.002]
• 7: Byskov, J. M. 2004. Enumerating maximal independent sets with applications to graph colouring. Oper. Res. Lett. 32, 6, 547--556.
• 8: Jianer Chen , Iyad A. Kanj , Weijia Jia, Vertex cover: further observations and further improvements, Journal of Algorithms, v.41 n.2, p.280-301, November 2001 [doi>10.1006/jagm.2001.1186]
• 9: Jianer Chen , Iyad A. Kanj , Ge Xia, Labeled Search Trees and Amortized Analysis: Improved Upper Bounds for NP-Hard Problems, Algorithmica, v.43 n.4, p.245-273, December 2005 [doi>10.1007/s00453-004-1145-7]
• 10: Evgeny Dantsin , Andreas Goerdt , Edward A. Hirsch , Ravi Kannan , Jon Kleinberg , Christos Papadimitriou , Prabhakar Raghavan , Uwe Schöning, A deterministic (2 - 2/(k+ 1))ⁿ algorithm for k-SAT based on local search, Theoretical Computer Science, v.289 n.1, p.69-83, 23 October 2002 [doi>10.1016/S0304-3975(01)00174-8]
• 11: Martin Davis , George Logemann , Donald Loveland, A machine program for theorem-proving, Communications of the ACM, v.5 n.7, p.394-397, July 1962 [doi>10.1145/368273.368557]
• 12: Martin Davis , Hilary Putnam, A Computing Procedure for Quantification Theory, Journal of the ACM (JACM), v.7 n.3, p.201-215, July 1960 [doi>10.1145/321033.321034]
• 13: Downey, R. G., and Fellows, M. R. 1999. Parameterized complexity. Monographs in Computer Science. Springer-Verlag, Berlin, Germany.
• 14: Ebenegger, C., Hammer, P. L., and de Werra, D. 1984. Pseudo Boolean functions and stability of graphs. Ann. Disc. Math. 19, 83--98.
• 15: Eppstein, D. 2003a. Small maximal independent sets and faster exact graph coloring. J. Graph Algor. Appl. 7, 2, 131--140.
• 16: Eppstein, D. 2003b. The traveling salesman problem for cubic graphs. In Proceedings of the Workshop on Algorithms and Data Structures (WADS). 307--318.
• 17: David Eppstein, Quasiconvex analysis of multivariate recurrence equations for backtracking algorithms, ACM Transactions on Algorithms (TALG), v.2 n.4, p.492-509, October 2006 [doi>10.1145/1198513.1198515]
• 18: Fedor V. Fomin , Serge Gaspers , Artem V. Pyatkin , Igor Razgon, On the Minimum Feedback Vertex Set Problem: Exact and Enumeration Algorithms, Algorithmica, v.52 n.2, p.293-307, August 2008 [doi>10.1007/s00453-007-9152-0]
• 19: Fomin, F., Grandoni, F., and Kratsch, D. 2005a. Measure and conquer: Domination—a case study. In Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP). Lecture Notes in Computer Science, vol. 3580, Springer-Verlag, Berlin, Germany, 191--203.
• 20: Fomin, F., Grandoni, F., and Kratsch, D. 2005b. Some new techniques in design and analysis of exact (exponential) algorithms. Bull. Europ. Assoc. Theoret. Comput. Sci. 87, 47--77.
• 21: Fedor V. Fomin , Fabrizio Grandoni , Dieter Kratsch, Measure and conquer: a simple O(2^0.288n) independent set algorithm, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.18-25, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109560]
• 22: Fedor V. Fomin , Fabrizio Grandoni , Artem V. Pyatkin , Alexey A. Stepanov, Combinatorial bounds via measure and conquer: Bounding minimal dominating sets and applications, ACM Transactions on Algorithms (TALG), v.5 n.1, p.1-17, November 2008 [doi>10.1145/1435375.1435384]
• 23: Fedor V. Fomin , Fabrizio Grandoni , Dieter Kratsch, Solving Connected Dominating Set Faster than 2 ⁿ, Algorithmica, v.52 n.2, p.153-166, August 2008 [doi>10.1007/s00453-007-9145-z]
• 24: Fedor V. Fomin , Dieter Kratsch , Ioan Todinca , Yngve Villanger, Exact Algorithms for Treewidth and Minimum Fill-In, SIAM Journal on Computing, v.38 n.3, p.1058-1079, June 2008 [doi>10.1137/050643350]
• 25: Fomin, F. V., Kratsch, D., and Woeginger, G. J. 2004. Exact (exponential) algorithms for the dominating set problem. In Proceedings of the International Workshop on Graph-Theoretic Concepts in Computer Science (WG). 199--210.
• 26: Fomin, F. V., and Stepanov, A. 2007. Counting minimum weighted dominating sets. In Proceedings of the International Computing and Combinatorics Conference (COCOON). 65--74.
• 27: Fürer, M. 2006. A faster algorithm for finding maximum independent sets in sparse graphs. In Proceedings of the Latin American Theoretical Informatics Symposium (LATIN). 491--501.
• 28: Gaspers, S., and Liedloff, M. 2006. A branch-and-reduce algorithm for finding a minimum independent dominating set in graphs. In Proceedings of the International Workshop on Graph-Theoretic Concepts in Computer Science (WG). 78--89.
• 29: Jens Gramm , Edward A. Hirsch , Rolf Niedermeier , Peter Rossmanith, Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT, Discrete Applied Mathematics, v.130 n.2, p.139-155, 15 August 2003 [doi>10.1016/S0166-218X(02)00402-X]
• 30: Grandoni, F. 2004. Exact algorithms for hard graph problems. Ph.D. dissertation, Università di Roma “Tor Vergata”, Roma, Italy.
• 31: Grandoni, F. 2006. A note on the complexity of minimum dominating set. J. Disc. Algor. 4, 2, 209--214.
• 32: Gupta, S., Raman, V., and Saurabh, S. 2006. Fast exponential algorithms for maximum regular induced subgraph problems. In Proceedings of the Foundations of Software Technology and Theoretical Computer Science (FSTTCS). 139--151.
• 33: Håstad, J. 1999. Clique is hard to approximate within n^{1−ε}. Acta Math. 182, 1, 105--142.
• 34: Haynes, T. W., Hedetniemi, S. T., and Slater, P. J. 1998. Fundamentals of Domination in Graphs. Marcel Dekker, Inc., New York.
• 35: Held, M., and Karp, R. M. 1962. A dynamic programming approach to sequencing problems. J. SIAM 10, 196--210.
• 36: Edward A. Hirsch, New Worst-Case Upper Bounds for SAT, Journal of Automated Reasoning, v.24 n.4, p.397-420, May 2000 [doi>10.1023/A:1006340920104]
• 37: Edward A. Hirsch, SAT Local Search Algorithms: Worst-Case Study, Journal of Automated Reasoning, v.24 n.1-2, p.127-143, February 2000 [doi>10.1023/A:1006318521185]
• 38: Ellis Horowitz , Sartaj Sahni, Computing Partitions with Applications to the Knapsack Problem, Journal of the ACM (JACM), v.21 n.2, p.277-292, April 1974 [doi>10.1145/321812.321823]
• 39: Russell Impagliazzo , Ramamohan Paturi , Francis Zane, Which problems have strongly exponential complexity?, Journal of Computer and System Sciences, v.63 n.4, p.512-530, December 2001 [doi>10.1006/jcss.2001.1774]
• 40: Iwama, K. 2004. Worst-case upper bounds for k-SAT. Bull. Europ. Associ. Theoret. Comp. Sci. 82, 61--71.
• 41: Kazuo Iwama , Suguru Tamaki, Improved upper bounds for 3-SAT, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 42: T Jian, An O(20.304n) Algorithm for Solving Maximum Independent Set Problem, IEEE Transactions on Computers, v.35 n.9, p.847-851, September 1986 [doi>10.1109/TC.1986.1676847]
• 43: Samuel Kohn , Allan Gottlieb , Meryle Kohn, A generating function approach to the Traveling Salesman Problem, Proceedings of the 1977 annual conference, p.294-300, January 1977 [doi>10.1145/800179.810218]
• 44: Mikko Koivisto, An O*(2^n ) Algorithm for Graph Coloring and Other Partitioning Problems via Inclusion--Exclusion, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.583-590, October 21-24, 2006 [doi>10.1109/FOCS.2006.11]
• 45: Arist Kojevnikov , Alexander S. Kulikov, A new approach to proving upper bounds for MAX-2-SAT, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.11-17, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109559]
• 46: Kowalik, L. 2006. Improved edge-coloring with three colors. In Proceedings of the International Workshop on Graph-Theoretic Concepts in Computer Science (WG). 90--101.
• 47: Dieter Kratsch , Mathieu Liedloff, An exact algorithm for the minimum dominating clique problem, Theoretical Computer Science, v.385 n.1-3, p.226-240, October, 2007 [doi>10.1016/j.tcs.2007.06.014]
• 48: O. Kullmann, New methods for 3-SAT decision and worst-case analysis, Theoretical Computer Science, v.223 n.1-2, p.1-72, July 28, 1999 [doi>10.1016/S0304-3975(98)00017-6]
• 49: Lawler, E. L. 1976. A note on the complexity of the chromatic number problem. Info. Process. Lett. 5, 3, 66--67.
• 50: Monien, B., and Speckenmeyer, E. 1985. Solving satisfiability in less than 2ⁿ steps. Disc. Appl. Math. 10, 3, 287--295.
• 51: Ramamohan Paturi , Pavel Pudlák , Michael E. Saks , Francis Zane, An improved exponential-time algorithm for k-SAT, Journal of the ACM (JACM), v.52 n.3, p.337-364, May 2005 [doi>10.1145/1066100.1066101]
• 52: Pavel Pudlák , Russell Impagliazzo, A lower bound for DLL algorithms for k-SAT (preliminary version), Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.128-136, January 09-11, 2000, San Francisco, California, United States
• 53: Randerath, B. and Schiermeyer, I. 2004. Exact algorithms for MINIMUM DOMINATING SET. Tech. Rep. zaik-469, Zentrum für Angewandte Informatik, Köln, Germany.
• 54: Ran Raz , Shmuel Safra, A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.475-484, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258641]
• 55: Razgon, I. 2006a. Exact computation of maximum induced forest. In Proceedings of the Scandinavian Workshop on Algorithm Theory (SWAT). 160--171.
• 56: Razgon, I. 2006b. A faster solving of the maximum independent set problem for graphs with maximal degree 3. In Proceedings of the Algorithms and Complexity in Durham Workshop (ACiD). 131--142.
• 57: Reed, B. 1996. Paths, stars and the number three. Combinatorics, Probability and Computing 5, 3, 277--295.
• 58: Tobias Riege , Jörg Rothe , Holger Spakowski , Masaki Yamamoto, An improved exact algorithm for the domatic number problem, Information Processing Letters, v.101 n.3, p.101-106, February, 2007 [doi>10.1016/j.ipl.2006.08.010]
• 59: Robson, J. M. 1986. Algorithms for maximum independent sets. J. Algor. 7, 3, 425--440.
• 60: Robson, J. M. 2001. Finding a maximum independent set in time O(2^n/4). Tech. Rep. 1251-01, LaBRI, Université Bordeaux I.
• 61: Uwe Schöning, A Probabilistic Algorithm for k-SAT and Constraint Satisfaction Problems, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.410, October 17-18, 1999
• 62: Schöning, U. 2005. Algorithmics in exponential time. In Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS). 36--43.
• 63: Schroeppel, R., and Shamir, A. 1981. A T = O(2^n/2), S = O(2^n/4) algorithm for certain NP-complete problems. SIAM J. Comput. 10, 3, 456--464.
• 64: Tarjan, R., and Trojanowski, A. 1977. Finding a maximum independent set. SIAM J. Comput. 6, 3, 537--546.
• 65: van Rooij, J., and Bodlaender, H. L. 2008. Design by measure and conquer, a faster exact algorithm for dominating set. In Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS). 657--668.
• 66: Villanger, Y. 2006. Improved exponential-time algorithms for tree-width and minimum fill-in. In Proceedings of the Latin American Theoretical Informatics Symposium (LATIN). 800--811.
• 67: West, D. B. 1996. Introduction to Graph Theory. Prentice Hall, Englewood Cliffs.
• 68: Ryan Williams, A new algorithm for optimal 2-constraint satisfaction and its implications, Theoretical Computer Science, v.348 n.2, p.357-365, 8 December 2005 [doi>10.1016/j.tcs.2005.09.023]
• 69: Gerhard J. Woeginger, Exact algorithms for NP-hard problems: a survey, Combinatorial optimization - Eureka, you shrink!, Springer-Verlag New York, Inc., New York, NY, 2003
• 70: David Zuckerman, Linear degree extractors and the inapproximability of max clique and chromatic number, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132612]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

General Terms:
Algorithms, Theory

Keywords:
Dominating set, exact algorithm, independent set