A $c^k n$ 5-Approximation Algorithm for Treewidth
From MaRDI portal
Publication:2799353
DOI10.1137/130947374zbMath1333.05282arXiv1304.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
Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items
Edge-cut width: an algorithmically driven analogue of treewidth based on edge cuts, Non-monotone target sets for threshold values restricted to $0$, $1$, and the vertex degree, Parameterized algorithms and data reduction for the short secluded s‐t‐path problem, Edge-treewidth: algorithmic and combinatorial properties, Colouring a dominating set without conflicts: \(q\)-subset square colouring, Linear‐time algorithms for eliminating claws in graphs, Parameterized complexity of finding a spanning tree with minimum reload cost diameter, Augmenting graphs to minimize the radius, Approximating sparse quadratic programs, An FPT algorithm for node-disjoint subtrees problems parameterized by treewidth, Unnamed Item, Unnamed Item, Recognizing hyperelliptic graphs in polynomial time, On \(H\)-topological intersection graphs, Recognizing \(k\)-clique extendible orderings, Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable, 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
