Paper by Erik D. Demaine
- 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.
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
to 2O(1/ε) nO(1).
- The paper is 10 pages.
- The paper is available in PostScript (287k), gzipped PostScript (115k), and PDF (153k).
- See information on file formats.
- [Google Scholar search]
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated December 15, 2022 by