Algoritmos exponenciales

Texts in Theoretical Computer Science An EATCS Series
Editors: W. Brauer J. Hromkoviˇ G. Rozenberg A. Salomaa c
On behalf of the European Association for Theoretical Computer Science (EATCS)

Advisory Board: G. Ausiello M. Broy C.S. Calude A. Condon D. Harel J. Hartmanis T. Henzinger T. Leighton M. Nivat C. Papadimitriou D. Scott

For further volumes: http://www.springer.com/series/3214Fedor V. Fomin · Dieter Kratsch

Exact Exponential Algorithms

123

Prof. Dr. Fedor V. Fomin University of Bergen Inst. Informatics PO Box 7800 5020 Bergen Norway fomin@ii.uib.no

Prof. Dieter Kratsch Universit´ Paul Verlaine - Metz e LITA, UFR MIM D´ pt. Informatique e Ile du Saulcy 57045 Cedex 1 France kratsch@univ-metz.fr

Series Editors Prof. Dr. Wilfried Brauer Institut f¨ rInformatik der TUM u Boltzmannstr. 3 85748 Garching, Germany brauer@informatik.tu-muenchen.de

Prof. Dr. Juraj Hromkoviˇ c ETH Zentrum Department of Computer Science Swiss Federal Institute of Technology 8092 Z¨ rich, Switzerland u juraj.hromkovic@inf.ethz.ch Prof. Dr. Arto Salomaa Turku Centre of Computer Science Lemmink¨ isenkatu 14 A a 20520 Turku, Finland asalomaa@utu.fi

Prof. Dr. GrzegorzRozenberg Leiden Institute of Advanced Computer Science University of Leiden Niels Bohrweg 1 2333 CA Leiden, The Netherlands rozenber@liacs.nl

ISSN 1862-4499 ISBN 978-3-642-16532-0 e-ISBN 978-3-642-16533-7 DOI 10.1007/978-3-642-16533-7 Springer Heidelberg Dordrecht London New York ACM Codes: F.2, G.1, G.2
c Springer-Verlag Berlin Heidelberg 2010 This work is subject to copyright. All rights arereserved, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilm or in any other way, and storage in data banks. Duplication of this publication or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965, in its currentversion, and permission for use must always be obtained from Springer. Violations are liable to prosecution under the German Copyright Law. The use of general descriptive names, registered names, trademarks, etc. in this publication does not imply, even in the absence of a specific statement, that such names are exempt from the relevant protective laws and regulations and therefore free for general use.Cover design: KuenkelLopka GmbH, Heidelberg Printed on acid-free paper Springer is part of Springer Science+Business Media (www.springer.com)

Preface

For a long time computer scientists have distinguished between fast and slow algorithms. Fast (or good) algorithms are the algorithms that run in polynomial time, which means that the number of steps required for the algorithm to solve aproblem is bounded by some polynomial in the length of the input. All other algorithms are slow (or bad). The running time of slow algorithms is usually exponential. This book is about bad algorithms. There are several reasons why we are interested in exponential time algorithms. Most of us believe that there are many natural problems which cannot be solved by polynomial time algorithms. The most famousand oldest family of hard problems is the family of NP-complete problems. Most likely there are no polynomial time algorithms solving these hard problems and in the worst-case scenario the exponential running time is unavoidable. Every combinatorial problem is solvable in finite time by enumerating all possible solutions, i.e. by brute-force search. But is brute-force search always unavoidable?Definitely not. Already in the nineteen sixties and seventies it was known that some NP-complete problems can be solved significantly faster than by brute-force search. Three classic examples are the following algorithms for the T RAVELLING S ALESMAN problem, M AXIMUM I NDEPENDENT S ET, and C OLORING. The algorithm of Bellman [17] and Held and Karp [111] from 1962 solves the T RAVELLING S ALESMAN...