Exact Algorithms for Treewidth and Minimum Fill-In

2008/01/01 by Fedor V. Fomin, Dieter Kratsch, Ioan Todinca +1 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Optimization and Search Problems #Treewidth #Combinatorics #Mathematical proof #Vertex (graph theory) #Mathematics #Partial k-tree #Graph #Discrete mathematics #1-planar graph #Algorithm #Pathwidth #Chordal graph #Line graph

paper · doi:10.1137/050643350

openalex publication_date 2008/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/02

Abstract

We show that the treewidth and the minimum fill-in of an n-vertex graph can be computed in time O(1.8899ⁿ). Our results are based on combinatorial proofs that an n-vertex graph has O(1.7087ⁿ) minimal separators and O(1.8135ⁿ) potential maximal cliques. We also show that for the class of asteroidal triple–free graphs the running time of our algorithms can be reduced to O(1.4142ⁿ).

Citations

• Coping with the NP-Hardness of the Graph Bandwidth Problem
• 3-coloring in time
• Efficient Approximation for Triangulation of Minimum Treewidth
• Which Problems Have Strongly Exponential Complexity?
• A note on the complexity of the chromatic number problem
• Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
• Computing Partitions with Applications to the Knapsack Problem
• Improved approximation algorithms for minimum-weight vertex separators
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Algorithms for maximum independent sets
• Complexity of Finding Embeddings in a k -Tree
• A partial k-arboretum of graphs with bounded treewidth
• Characterizations and algorithmic applications of chordal graph embeddings
• Finding a Maximum Independent Set
• Fixed-parameter tractability of graph modification problems for hereditary properties

Cited by

• Pathwidth [wikipedia]

Related

• Algorithms parameterized by vertex cover and modular width, through\n potential maximal cliques
• Treewidth computation and extremal combinatorics
• Space-Efficient Vertex Separators for Treewidth
• A O(c^k n) 5-Approximation Algorithm for Treewidth
• A Note on Exponential-Time Algorithms for Linearwidth