Subexponential parameterized algorithms

Frederic Dorn, Fedor V. Fomin, Dimitrios M. Thilikos

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


We present a series of techniques for the design of subexponential parameterized algorithms for graph problems. The design of such algorithms usually consists of two main steps: first find a branch- (or tree-) decomposition of the input graph whose width is bounded by a sublinear function of the parameter and, second, use this decomposition to solve the problem in time that is single exponential to this bound. The main tool for the first step is Bidimensionality Theory. Here we present the potential, but also the boundaries, of this theory. For the second step, we describe recent techniques, associating the analysis of sub-exponential algorithms to combinatorial bounds related to Catalan numbers. As a result, we have 2 o(√k)·no(1) time algorithms for a wide variety of parameterized problems on graphs, where n is the size of the graph and k is the parameter.

Original languageEnglish (US)
Title of host publicationAutomata, Languages and Programming - 34th International Colloquium, ICALP 2007, Proceedings
PublisherSpringer Verlag
Number of pages13
ISBN (Print)3540734198, 9783540734192
StatePublished - 2007
Event34th International Colloquium on Automata, Languages and Programming, ICALP 2007 - Wroclaw, Poland
Duration: Jul 9 2007Jul 13 2007

Publication series

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


Conference34th International Colloquium on Automata, Languages and Programming, ICALP 2007

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Subexponential parameterized algorithms'. Together they form a unique fingerprint.

Cite this