Local tree-width, excluded minors, and approximation algorithms

DOI10.1007/S00493-003-0037-9zbMATH Open1089.05503arXivmath/0001128OpenAlexW2013522700WikidataQ55934709 ScholiaQ55934709MaRDI QIDQ2494422FDOQ2494422

Authors: Martin Grohe 

Publication date: 27 June 2006

Published in: Combinatorica (Search for Journal in Brave)

Abstract: The local tree-width of a graph G=(V,E) is the function ltw^G: N -> N that associates with every natural number r the maximal tree-width of an r-neighborhood in G. Our main graph theoretic result is a decomposition theorem for graphs with excluded minors that essentially says that such graphs can be decomposed into trees of graphs of bounded local tree-width. As an application of this theorem, we show that a number of combinatorial optimization problems, such as Minimum Vertex Cover, Minimum Dominating Set, and Maximum Independent Set have a polynomial time approximation scheme when restricted to a class of graphs with an excluded minor.

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

Recommendations

• Improved bounds for the excluded-minor approximation of treedepth
• Improved bounds for the excluded-minor approximation of treedepth
• Dominating sets and local treewidth
• Graph minors. II. Algorithmic aspects of tree-width
• Graph Drawing
• Equivalence of local treewidth and linear local treewidth and its algorithmic applications
• Optimal algorithms for hitting (topological) minors on graphs of bounded treewidth
• Hitting minors on bounded treewidth graphs. II. Single-exponential algorithms
• Inapproximability of treewidth and related problems
• On extremal sizes of locally \(k\)-tree graphs.

zbMATH Keywords

combinatorial optimizationlocal tree-width

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial optimization (90C27) Approximation algorithms (68W25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph minors (05C83)

Cited In (44)

• Parameterized complexity of the spanning tree congestion problem
• Layered separators in minor-closed graph classes with applications
• Guard games on graphs: keep the intruder out!
• Improved bounds for the excluded-minor approximation of treedepth
• Linearity of grid minors in treewidth with applications through bidimensionality
• Approximation algorithms for polynomial-expansion and low-density graphs
• Minimal classes of graphs of unbounded clique-width
• A polynomial excluded-minor approximation of treedepth
• The degree-diameter problem for sparse graph classes
• Orthogonal tree decompositions of graphs
• Size-treewidth tradeoffs for circuits computing the element distinctness function
• Minor-Closed Graph Classes with Bounded Layered Pathwidth
• Polynomial kernels and faster algorithms for the dominating set problem on graphs with an excluded minor
• Title not available (Why is that?)
• Equivalence of local treewidth and linear local treewidth and its algorithmic applications
• Implicit branching and parameterized partial cover problems
• Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs
• Simple PTAS's for families of graphs excluding a minor
• Parameterized complexity of directed Steiner tree on sparse graphs
• Subgraph isomorphism, log-bounded fragmentation, and graphs of (locally) bounded treewidth
• Approximating sparse quadratic programs
• Large independent sets in subquartic planar graphs
• Linear kernels for (connected) dominating set on \(H\)-minor-free graphs
• Algorithmic properties of sparse digraphs
• PTAS for Sparse General-valued CSPs
• A note on the independence number, domination number and related parameters of random binary search trees and random recursive trees
• Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs
• Approximation of minimum weight spanners for sparse graphs
• Faster approximation schemes and parameterized algorithms on (odd-)\(H\)-minor-free graphs
• Structure of graphs with locally restricted crossings
• Minors and dimension
• Structure theorem and isomorphism test for graphs with excluded topological subgraphs
• Local 2-separators
• Approximation algorithms via contraction decomposition
• Contracting planar graphs to contractions of triangulations
• Distributed Dominating Set Approximations beyond Planar Graphs
• On the complexity of reasoning about opinion diffusion under majority dynamics
• Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering
• LATIN 2004: Theoretical Informatics
• Linear kernels for outbranching problems in sparse digraphs
• Target set selection with maximum activation time
• Local search: is brute-force avoidable?
• 1-planarity testing and embedding: an experimental study
• Parameterized complexity of finding small degree-constrained subgraphs

This page was built for publication: Local tree-width, excluded minors, and approximation algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2494422)