A Single-Exponential Time 2-Approximation Algorithm for Treewidth

2021/04/15 by Korhonen, Tuukka · 18 citations
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2104.07463

Abstract

We give an algorithm that, given an n-vertex graph G and an integer k, in time 2^O(k) n either outputs a tree decomposition of G of width at most 2k + 1 or determines that the treewidth of G is larger than k. This is the first 2-approximation algorithm for treewidth that is faster than the known exact algorithms, and in particular improves upon the previous best approximation ratio of 5 in time 2^O(k) n given by Bodlaender et al. [SIAM J. Comput., 45 (2016)]. Our algorithm works by applying incremental improvement operations to a tree decomposition, using an approach inspired by a proof of Bellenbaum and Diestel [Comb. Probab. Comput., 11 (2002)].

Cited by

• Excluding a Forest Induced Minor
• A Unified Complexity-Algorithm Account of Constant-Round QAOA Expectation Computation
• New Algorithms and Hardness Results for Connected Clustering
• Polynomial-time algorithms for PATH COVER and PATH PARTITION on trees and graphs of bounded treewidth
• Compact representations of pattern-avoiding permutations
• The Parameterized Complexity of Computing the VC-Dimension
• An efficient algorithm for F-subgraph-free Edge Deletion on graphs having a product structure
• On the Structural Parameterizations of 2-Club with Triangle Constraints
• Parameterized Complexity of Vehicle Routing
• Parameterized Algorithms for Computing Pareto Sets
• On the Parameterized Complexity of Grundy Domination and Zero Forcing Problems
• A Parameterized Perspective on Uniquely Restricted Matchings
• On Fixed-Parameter Tractability of Weighted 0-1 Timed Matching Problem on Temporal Graphs
• Parameterized complexity of isometric path partition: treewidth and diameter
• Finding sparse induced subgraphs on graphs of bounded induced matching treewidth
• Parameterized Critical Node Cut Revisited
• Catching Rats in H-minor-free Graphs
• Edge Clique Partition and Cover Beyond Independence

Related

• An Improved Parameterized Algorithm for Treewidth
• A O(c^k n) 5-Approximation Algorithm for Treewidth
• Optimized 2-Approximation of Treewidth
• An Improvement of Reed's Treewidth Approximation
• Treewidth Parameterized by Feedback Vertex Number