Exact (Exponential) Algorithms for Treewidth and Minimum Fill-In

We show that for a graph $G$ on $n$ vertices its treewidth can be computed in $\mathcal{O}(poly(n) 1.9601^n)$ time. Our result is based on combinatorial upper bounds for the number of minimal separators and the number of potential maximal cliques of a graph.

Data and Resources

Additional Info

Field Value
Source Proceedings 31st International Colloquium on Automatas, Languages and Programming (ICALP 2004)
Author Kratsch, Dieter, Fomin, Fedor V., Todinca, Ioan
Maintainer CCSD
Last Updated May 9, 2026, 23:25 (UTC)
Created May 9, 2026, 23:25 (UTC)
Identifier hal-00085561
Language en
contributor Laboratoire d'Informatique Fondamentale d'Orléans (LIFO) ; Université d'Orléans (UO)-Ecole Nationale Supérieure d'Ingénieurs de Bourges
creator Kratsch, Dieter
date 2004-05-09T00:00:00
harvest_object_id 72a5f04e-581c-46d1-ae41-befc0f85f6fc
harvest_source_id 3374d638-d20b-4672-ba96-a23232d55657
harvest_source_title test moissonnage SELUNE
metadata_modified 2025-08-12T00:00:00
set_spec type:COMM