A $c^k n$ 5-Approximation Algorithm for Treewidth

DOI10.1137/130947374zbMath1333.05282DBLPjournals/siamcomp/BodlaenderDDFLP16arXiv1304.6321OpenAlexW2313886575WikidataQ59567401 ScholiaQ59567401MaRDI QIDQ2799353

Daniel Lokshtanov, Pål Grønås Drange, Michał Pilipczuk, Markus Sortland Dregi, Fedor V. Fomin, Hans L. Bodlaender

Publication date: 11 April 2016

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1304.6321

zbMATH Keywords

algorithmsapproximationtreewidthgraphsfixed parameter tractability

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (only showing first 100 items - show all)

A polynomial excluded-minor approximation of treedepth ⋮ A parameterized complexity view on collapsing \(k\)-cores ⋮ A new approach on locally checkable problems ⋮ Parameterized Complexity of $$(A,\ell )$$-Path Packing ⋮ Lower Bounds for Dominating Set in Ball Graphs and for Weighted Dominating Set in Unit-Ball Graphs ⋮ As Time Goes By: Reflections on Treewidth for Temporal Graphs ⋮ Four Shorts Stories on Surprising Algorithmic Uses of Treewidth ⋮ Computing Tree Decompositions ⋮ Linear Time Parameterized Algorithms for Subset Feedback Vertex Set ⋮ Computing L(p,1)-Labeling with Combined Parameters ⋮ An Improvement of Reed’s Treewidth Approximation ⋮ A Structural Approach to Kernels for ILPs: Treewidth and Total Unimodularity ⋮ Weighted proper orientations of trees and graphs of bounded treewidth ⋮ Treewidth distance on phylogenetic trees ⋮ Finding all leftmost separators of size \(\le k\) ⋮ Structural parameterizations with modulator oblivion ⋮ Sum-of-Products with Default Values: Algorithms and Complexity Results ⋮ Space-efficient vertex separators for treewidth ⋮ On some domination colorings of graphs ⋮ Eccentricity queries and beyond using hub labels ⋮ Unnamed Item ⋮ Harmless sets in sparse classes ⋮ Rank-width: algorithmic and structural results ⋮ Bisection of bounded treewidth graphs by convolutions ⋮ On quasi-planar graphs: clique-width and logical description ⋮ Linear kernels for outbranching problems in sparse digraphs ⋮ Efficient FPT algorithms for (strict) compatibility of unrooted phylogenetic trees ⋮ Treewidth-aware reductions of normal \textsc{ASP} to \textsc{SAT} - is normal \textsc{ASP} Harder than \textsc{SAT} after all? ⋮ New Results on Directed Edge Dominating Set ⋮ Deterministic Algorithms for the Independent Feedback Vertex Set Problem ⋮ Parameterized edge Hamiltonicity ⋮ From tree-decompositions to clique-width terms ⋮ The graphs of stably matchable pairs ⋮ Computing the best-case energy complexity of satisfying assignments in monotone circuits ⋮ Parameterized approximation via fidelity preserving transformations ⋮ Combinatorial problems on \(H\)-graphs ⋮ Parameterized complexity of envy-free resource allocation in social networks ⋮ Parameterized complexity of happy coloring problems ⋮ Refining the complexity of the sports elimination problem ⋮ Unnamed Item ⋮ Eulerian walks in temporal graphs ⋮ An FPT 2-approximation for tree-cut decomposition ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A PTAS for the Cluster Editing Problem on Planar Graphs ⋮ Sketched representations and orthogonal planarity of bounded treewidth graphs ⋮ Reconfiguration of cliques in a graph ⋮ Typical sequences revisited -- computing width parameters of graphs ⋮ Hitting Minors on Bounded Treewidth Graphs. I. General Upper Bounds ⋮ On directed covering and domination problems ⋮ An improvement of Reed's treewidth approximation ⋮ Computing \(L(p, 1)\)-labeling with combined parameters ⋮ Succinct certification of monotone circuits ⋮ On Algorithms Employing Treewidth for $L$-bounded Cut Problems ⋮ On the parameterized complexity of computing balanced partitions in graphs ⋮ Waypoint routing on bounded treewidth graphs ⋮ Target set selection for conservative populations ⋮ Coloring temporal graphs ⋮ New width parameters for SAT and \#SAT ⋮ Minimum size tree-decompositions ⋮ Unnamed Item ⋮ \textsc{ToTo}: an open database for computation, storage and retrieval of tree decompositions ⋮ On distance-preserving elimination orderings in graphs: complexity and algorithms ⋮ The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs ⋮ Unnamed Item ⋮ Generalized feedback vertex set problems on bounded-treewidth graphs: chordality is the key to single-exponential parameterized algorithms ⋮ Temporal graph classes: a view through temporal separators ⋮ On structural parameterizations of the edge disjoint paths problem ⋮ Editing to a planar graph of given degrees ⋮ Large Independent Sets in Triangle-Free Planar Graphs ⋮ Minimum reload cost graph factors ⋮ Tree-coloring problems of bounded treewidth graphs ⋮ Subexponential-time algorithms for finding large induced sparse subgraphs ⋮ Parameterized Approximation Schemes for Independent Set of Rectangles and Geometric Knapsack ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Walking through waypoints ⋮ The complexity of tree partitioning ⋮ Hitting forbidden induced subgraphs on bounded treewidth graphs ⋮ Finding Detours is Fixed-Parameter Tractable ⋮ Hitting minors on bounded treewidth graphs. II. Single-exponential algorithms ⋮ A Framework for Exponential-Time-Hypothesis--Tight Algorithms and Lower Bounds in Geometric Intersection Graphs ⋮ Faster Computation of Path-Width ⋮ Hitting Forbidden Induced Subgraphs on Bounded Treewidth Graphs ⋮ Lean Tree-Cut Decompositions: Obstructions and Algorithms ⋮ Algorithms and complexity for Turaev-Viro invariants ⋮ Unnamed Item ⋮ On knot-free vertex deletion: fine-grained parameterized complexity analysis of a deadlock resolution graph problem ⋮ Connecting knowledge compilation classes and width parameters ⋮ A Linear-Time Parameterized Algorithm for Node Unique Label Cover ⋮ Finding small-width connected path decompositions in polynomial time ⋮ Multivariate analysis of orthogonal range searching and graph distances ⋮ Finding, hitting and packing cycles in subexponential time on unit disk graphs ⋮ Coloring a dominating set without conflicts: \(q\)-subset square coloring ⋮ Pure Nash equilibria in graphical games and treewidth ⋮ Unnamed Item ⋮ On Directed Covering and Domination Problems ⋮ Experimental Evaluation of a Branch-and-Bound Algorithm for Computing Pathwidth and Directed Pathwidth ⋮ Parameterized complexity of \((A,\ell)\)-path packing

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Equitable colorings of bounded treewidth graphs
• Parameterized graph separation problems
• Approximation algorithms for treewidth
• Shortest paths in digraphs of small treewidth. II: Optimal parallel algorithms
• A partial k-arboretum of graphs with bounded treewidth
• Treewidth. Computations and approximations
• Shortest paths in digraphs of small treewidth. I: Sequential algorithms
• Dynamic algorithms for graphs of bounded treewidth
• Graph minors. XIII: The disjoint paths problem
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth
• Inapproximability of Treewidth, One-Shot Pebbling, and Related Layout Problems
• Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
• Improved Approximation Algorithms for Minimum Weight Vertex Separators
• Graph minors. II. Algorithmic aspects of tree-width
• Complexity of Finding Embeddings in a k-Tree
• Parallel Tree Contraction Part 2: Further Applications
• Parallel Algorithms with Optimal Speedup for Bounded Treewidth
• Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
• Algorithms for Vertex Partitioning Problems on Partial k-Trees
• Fast Hamiltonicity Checking Via Bases of Perfect Matchings
• Solving partial constraint satisfaction problems with tree decomposition
• Efficient Parallel Algorithms for Graphs of Bounded Tree-Width
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• A linear time algorithm for finding tree-decompositions of small treewidth
• AN IMPROVED ALGORITHM FOR FINDING TREE DECOMPOSITIONS OF SMALL WIDTH
• Deterministic Single Exponential Time Algorithms for Connectivity Problems Parameterized by Treewidth
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth

This page was built for publication: A $c^k n$ 5-Approximation Algorithm for Treewidth