Measure and Conquer:A Simple O(20.288n) Independent Set AlgorithmFedor V. Fomin∗Fabrizio Grandoni†Dieter Kratsch‡AbstractFor more than 30 years Davis-Putnam-style exponential-time backtracking algorithms have been the most commontools used for finding exact solutions of NP-hard problems.Despite of that, the way to analyze such recursive algorithmsis still far from producing tight worst case running timebounds.The “Measure and Conquer” approach is one of the re-cent attempts to step beyond such limitations. The approachis based on the choice of the measure of the subproblemsrecursively generated by the algorithm considered; this mea-sure is used to lower bound the progress made by the algo-rithm at each branching step. A good choice of the measurecan lead to a significantly better worst case time analysis.In this paper we apply “Measure and Conquer” to theanalysis of a very simple backtracking algorithm solving thewell-studied maximum independent set problem. The resultof the analysis is striking: the running time of the algorithmis O(20.288n), which is competitive with the current best timebounds obtained with far more complicated algorithms (andnaive 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 boundsachievable.Keywords: Algorithms and data structures, exponential-time exact algorithms, NP-hard problems, independent setproblem.1 IntroductionRecently, there has been a growing interest in the design andanalysis of exact exponential time algorithms for NP-hardproblems such as satisfiability [6, 12, 16], coloring [2, 3],maximum independent set [1, 5], max-cut [19], minimum∗Department of Informatics, University of Bergen, N-5020 Bergen, Nor-way, [email protected]. Supported by Norges forskningsr˚ad project160778/V30.†Dipartimento di Informatica, Universit`a di Roma “La Sapienza”, ViaSalaria 113, 00198 Roma, Italy, [email protected]. Sup-ported by EC Project DELIS, and project WebMinds of the Italian Ministryof University and Research (MIUR).‡LITA, Universit´e de Metz, 57045 Metz Cedex 01, France,[email protected] set [8], treewidth [9] and many others. (See thesurvey [20].) There are several explanations to that:• There are certain applications that require exact solu-tions of NP-hard problems, although this might only bepossible for moderate input sizes.• Approximation algorithms are not always satisfactory.For example, maximum independent set is hard toapproximate within n1−ε[11].• A reduction of the base of the exponential runningtime, say from O(2n) to O(20.9n), increases the size ofthe instances solvable within a given amount of timeby a constant multiplicative factor; running a givenexponential algorithm on a faster computer can enlargethe mentioned size only by a constant additive factor.• The design and analysis of exact algorithms leads toa better understanding of NP-hard problems and ini-tiates interesting new combinatorial and algorithmicchallenges.Related Work. The design of exponential algorithms forthe maximum independent set problem has a long historystarting from the first algorithm due to Tarjan [17] break-ing the trivial O(2n) bound. The first published algorithmis due to Tarjan and Trojanowski (1977): it has runningtime O(2n/3) and polynomial space complexity [18]. In1986 Jian published a polynomial-space algorithm of run-ning time O(20.304n) [13] and Robson came out with a poly-nomial space algorithm of running time O(20.296n) and withan exponential space algorithm using time O(20.276n) [14].In a recent technical report [15] Robson claims better run-ning times, both in polynomial and in exponential space. Thedescription of his new algorithm, which is partially computergenerated, takes almost 18 pages. A significant amount of re-search was also devoted to solve the maximum independentset problem on sparse graphs [1, 4, 5].All mentioned exact algorithms for the maximum in-dependent set problem are search-tree based. They use abranch and reduce paradigm with a (long) list of reductionand branching rules. Often, this list is derived from a some-what tedious and complicated case analysis. The runningtime analysis leads to a linear recurrence for each branching18SODA ’06, January 22-26, Miami, FL ©2006 SIAM ISBN 0-89871-605-5/06/01rule that can be solved using standard techniques. The clas-sical worst case running time analysis of such algorithms isbased on the assumption that a “natural” size of a problem(instance) is associated to each node of the search tree. Forgraph algorithms the natural measure is the number of ver-tices or edges in the corresponding (remaining) graph and itis not surprising that usually this measure is used for maxi-mum independent set.The interest on exact algorithms for the independentset problem seems to have vanished in the nineties. Thisis partially due to the fact that the current best algorithmsfor the problem are already very complicated: adding a fewmore branching rules in order to slightly reduce their runningtime might seem a waste of time.Fortunately the growing interest on exact algorithms forNP-hard problems has led to important new insights. One ofthose is the idea to use non-standard measures for the size ofa problem (instance). Using this approach, that they called“Measure and Conquer”, Fomin et al. obtained the currentlyfastest O(20.598n) algorithm for the minimum dominating setproblem [8].New Results. In this paper we continue our previouswork on the “Measure and Conquer” method [8]. To studythe power of the method it is natural to test it at a probleminto which a lot of effort was put with the classical anal-ysis — the maximum independent set problem. To stressthe power of the method, we developed a very simple al-gorithm: it can be described in a few lines and analyzed ina few pages (though we needed a computer to find a goodmeasure for it). Our polynomial-space algorithm has run-ning time O(20.288n). Currently there is no better publishedpolynomial-space algorithm.The algorithm uses reduction rules based on dominationand folding which are known in the literature. We alsointroduce the useful notion of mirroring, which allows togreatly simplify the description of the algorithm. Intuitively,when we branch by discarding a node, we can discard itsmirrors as well. This handy tool might be of independentinterest.The current
View Full Document
Unlocking...