Subexponential parameterized algorithms

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

Research output: Contribution to journalArticlepeer-review


We give a review of a series of techniques and results on 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 the Bidimensionality Theory. Here we present not only the potential, but also the boundaries, of this theory. For the second step, we describe recent techniques, associating the analysis of subexponential algorithms to combinatorial bounds related to Catalan numbers. As a result, we have 2O (sqrt(k)) {dot operator} 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)
Pages (from-to)29-39
Number of pages11
JournalComputer Science Review
Issue number1
StatePublished - Apr 2008

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