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

ABSTRACT

For more than 30 years Davis-Putnam-style exponential-time backtracking algorithms have been the most common tools used for finding exact solutions of NP-hard problems. Despite of that, the way to analyze such recursive algorithms is still far from producing tight worst case running time bounds.The "Measure and Conquer" approach is one of the recent attempts to step beyond such limitations. The approach is based on the choice of the measure of the subproblems recursively generated by the algorithm considered; this measure is used to lower bound the progress made by the algorithm at each branching step. A good choice of the measure can lead to a significantly better worst case time analysis.In this paper we apply "Measure and Conquer" to the analysis of a very simple backtracking algorithm solving the well-studied maximum independent set problem. The result of the analysis is striking: the running time of the algorithm is O(2^0.288n), which is competitive with the current best time bounds obtained with far more complicated algorithms (and naive analysis).Our example shows 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: 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
• 2: 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]
• 3: J. M. Byskov, Enumerating maximal independent sets with applications to graph colouring. Operations Research Letters 32:547--556, 2004.
• 4: 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]
• 5: J. Chen, I. A. Kanj, and G. Xia. Labeled search trees and amortized analysis: improved upper bounds for NP-hard problems. Proceedings of the 14th Annual International Symposium on Algorithms and Computation (ISAAC 2003), Springer LNCS vol. 2906, 2003, pp. 148--157.
• 6: 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]
• 7: David Eppstein, Quasiconvex analysis of backtracking algorithms, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 8: F. V. Fomin, F. Grandoni, and D. Kratsch. Measure and Conquer: Domination - A Case Study, Proceedings of the 32nd International Colloquium on Automata, Languages and Programming (ICALP 2005), Springer LNCS vol. 3580, 2005, pp. 191--203.
• 9: F. V. Fomin, D. Kratsch, and I. Todinca. Exact algorithms for treewidth and minimum fill-in. Proceedings of the 31st International Colloquium on Automata, Languages and Programming (ICALP 2004), Springer LNCS vol. 3142, 2004, pp. 568--580.
• 10: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 11: J. Håstad. Clique is hard to approximate within n1-ε. Acta Math. 182 (1):105--142, 1999.
• 12: 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
• 13: T Jian, AN O (20.304n) algorithm for solving maximum independent set problems, IEEE Transactions on Computers, v.35 n.9, p.847-851, Sept. 1986 [doi>10.1109/TC.1986.1676847]
• 14: J. M. Robson. Algorithms for maximum independent sets. Journal of Algorithms, 7(3):425--440, 1986.
• 15: J. M. Robson. Finding a maximum independent set in time O(2n/4). Technical Report 1251--01, LaBRI, Université Bordeaux I, 2001.
• 16: 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
• 17: R. Tarjan. Finding a maximum clique. Technical Report 72--123, Computer Sci. Dept., Cornell Univ., Ithaca, NY, 1972.
• 18: R. Tarjan and A. Trojanowski. Finding a maximum independent set. SIAM Journal on Computing, 6(3):537--546, 1977.
• 19: R. Williams. A new algorithm for optimal constraint satisfaction and its implications. Proceedings of the 31st International Colloquium on Automata, Languages and Programming (ICALP 2004), Springer LNCS vol. 3142, 2004, pp. 1227--1237.
• 20: 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

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Backtracking

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

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Dynamic programming

General Terms:
Algorithms, Theory

Keywords:
NP-hard problems, algorithms and data structures, exponential-time exact algorithms, independent set problem