On exact algorithms for treewidth

Hans L. Bodlaender, Fedor V. Fomin, Arie M.C.A. Koster, Dieter Kratsch, Dimitrios M. Thilikos

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We give experimental and theoretical results on the problem of computing the treewidth of a graph by exact exponential time algorithms using exponential space or using only polynomial space. We first report on an implementation of a dynamic programming algorithm for computing the treewidth of a graph with running time O*(2n). This algorithm is based on the old dynamic programming method introduced by Held and Karp for the TRAVELING SALESMAN problem. We use some optimizations that do not affect the worst case running time but improve on the running time on actual instances and can be seen to be practical for small instances. However, our experiments show that the space used by the algorithm is an important factor to what input sizes the algorithm is effective. For this purpose, we settle the problem of computing treewidth under the restriction that the space used is only polynomial. In this direction we give a simple O*(4n) algorithm that requires polynomial space. We also prove that using more refined techniques with balanced separators, TREEWIDTH can be computed in O*(2.9512n) time and polynomial space.

Original languageEnglish (US)
Title of host publicationAlgorithms, ESA 2006 - 14th Annual European Symposium, Proceedings
PublisherSpringer Verlag
Pages672-683
Number of pages12
ISBN (Print)3540388753, 9783540388753
DOIs
StatePublished - 2006
Event14th Annual European Symposium on Algorithms, ESA 2006 - Zurich, Switzerland
Duration: Sep 11 2006Sep 13 2006

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4168 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other14th Annual European Symposium on Algorithms, ESA 2006
Country/TerritorySwitzerland
CityZurich
Period9/11/069/13/06

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'On exact algorithms for treewidth'. Together they form a unique fingerprint.

Cite this