Paper by Erik D. Demaine

Reference:

Erik D. Demaine and MohammadTaghi Hajiaghayi, “Equivalence of Local Treewidth and Linear Local Treewidth and its Algorithmic Applications”, in Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2004), New Orleans, Louisiana, January 11–13, 2004, pages 833–842.

BibTeX

@InProceedings{ApexMinorFree_SODA2004,
  AUTHOR        = {Erik D. Demaine and MohammadTaghi Hajiaghayi},
  TITLE         = {Equivalence of Local Treewidth and Linear Local Treewidth
                   and its Algorithmic Applications},
  BOOKTITLE     = {Proceedings of the 15th Annual ACM-SIAM Symposium on
                   Discrete Algorithms (SODA 2004)},
  bookurl       = {http://www.siam.org/meetings/da04/},
  ADDRESS       = {New Orleans, Louisiana},
  MONTH         = {January 11--13},
  YEAR          = 2004,
  PAGES         = {833--842},

  length        = {10 pages},
  withstudent   = 1,
  dblp          = {https://dblp.org/rec/conf/soda/DemaineH04},
  ee            = {http://dl.acm.org/citation.cfm?id=982792.982919},
}

Abstract:

We solve an open problem posed by Eppstein in 1995 [14, 15] and re-enforced by Grohe [16, 17] concerning locally bounded treewidth in minor-closed families of graphs. A graph has bounded local treewidth if the subgraph induced by vertices within distance r of any vertex has treewidth bounded by a function of r (not n). Eppstein characterized minor-closed families of graphs with bounded local treewidth as precisely minor-closed families that minor-exclude an apex graph, where an apex graph has one vertex whose removal leaves a planar graph. In particular, Eppstein showed that all apex-minor-free graphs have bounded local treewidth, but his bound is doubly exponential in r, leaving open whether a tighter bound could be obtained. We improve this doubly exponential bound to a linear bound, which is optimal. In particular, any minor-closed graph family with bounded local treewidth has linear local treewidth. Our bound generalizes previously known linear bounds for special classes of graphs proved by several authors. As a consequence of our result, we obtain substantially faster polynomial-time approximation schemes for a broad class of problems in apex-minor-free graphs, improving the running time from 2^22O(1/ε) n^O(1) to 2^O(1/ε) n^O(1).

Length:

The paper is 10 pages.

Availability:

The paper is available in PostScript (287k), gzipped PostScript (115k), and PDF (153k).

See information on file formats.

[Google Scholar search]