Equivalence of Local Treewidth and Linear Local Treewidth and its Algorithmic Applications
We solve an open problem posed by Eppstein in 1995 and re-enforced by Grohe 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...
| Հիմնական հեղինակներ: | , |
|---|---|
| Հրապարակվել է: |
2023
|
| Առցանց հասանելիություն: | https://hdl.handle.net/1721.1/149989 |
| _version_ | 1826201184150487040 |
|---|---|
| author | Demaine, Erik D. Hajiaghayi, Mohammad Taghi |
| author_facet | Demaine, Erik D. Hajiaghayi, Mohammad Taghi |
| author_sort | Demaine, Erik D. |
| collection | MIT |
| description | We solve an open problem posed by Eppstein in 1995 and re-enforced by Grohe 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^(2^(2^O(1/epsilon))) n^O(1) to 2^O(1/epsilon) n^O(1). |
| first_indexed | 2024-09-23T11:47:33Z |
| id | mit-1721.1/149989 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T11:47:33Z |
| publishDate | 2023 |
| record_format | dspace |
| spelling | mit-1721.1/1499892023-03-30T03:49:30Z Equivalence of Local Treewidth and Linear Local Treewidth and its Algorithmic Applications Demaine, Erik D. Hajiaghayi, Mohammad Taghi We solve an open problem posed by Eppstein in 1995 and re-enforced by Grohe 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^(2^(2^O(1/epsilon))) n^O(1) to 2^O(1/epsilon) n^O(1). 2023-03-29T15:37:24Z 2023-03-29T15:37:24Z 2003-05 https://hdl.handle.net/1721.1/149989 MIT-LCS-TR-903 application/pdf |
| spellingShingle | Demaine, Erik D. Hajiaghayi, Mohammad Taghi Equivalence of Local Treewidth and Linear Local Treewidth and its Algorithmic Applications |
| title | Equivalence of Local Treewidth and Linear Local Treewidth and its Algorithmic Applications |
| title_full | Equivalence of Local Treewidth and Linear Local Treewidth and its Algorithmic Applications |
| title_fullStr | Equivalence of Local Treewidth and Linear Local Treewidth and its Algorithmic Applications |
| title_full_unstemmed | Equivalence of Local Treewidth and Linear Local Treewidth and its Algorithmic Applications |
| title_short | Equivalence of Local Treewidth and Linear Local Treewidth and its Algorithmic Applications |
| title_sort | equivalence of local treewidth and linear local treewidth and its algorithmic applications |
| url | https://hdl.handle.net/1721.1/149989 |
| work_keys_str_mv | AT demaineerikd equivalenceoflocaltreewidthandlinearlocaltreewidthanditsalgorithmicapplications AT hajiaghayimohammadtaghi equivalenceoflocaltreewidthandlinearlocaltreewidthanditsalgorithmicapplications |