(2020) A Framework for Exponential-Time-Hypothesis--Tight Algorithms and Lower Bounds in Geometric Intersection Graphs.
|
Text
20m1320870.pdf Download (1MB) | Preview |
Abstract
We give an algorithmic and lower bound framework that facilitates the construction of subexponential algorithms and matching conditional complexity bounds. It can be applied to intersection graphs of similarly-sized fat objects, yielding algorithms with running time $2^{O(n^{1-1/d})}$ for any fixed dimension $d\ge 2$ for many well-known graph problems, including Independent Set, $r$-Dominating Set for constant $r$, and Steiner Tree. For most problems, we get improved running times compared to prior work; in some cases, we give the first known subexponential algorithm in geometric intersection graphs. Additionally, most of the obtained algorithms are representation-agnostic, i.e., they work on the graph itself and do not require the geometric representation. Our algorithmic framework is based on a weighted separator theorem and various treewidth techniques. The lower bound framework is based on a constructive embedding of graphs into $d$-dimensional grids, and it allows us to derive matching $2^{\Omega(n^{1-1/d})}$ lower bounds under the exponential time hypothesis even in the much more restricted class of $d$-dimensional induced grid graphs.
| Item Type: | Article |
|---|---|
| Divisions: | Dániel Marx (DM) |
| Depositing User: | Dániel Marx |
| Date Deposited: | 04 May 2021 11:08 |
| Last Modified: | 04 May 2021 11:08 |
| Primary Research Area: | NRA1: Trustworthy Information Processing |
| URI: | https://publications.cispa.saarland/id/eprint/3397 |
Actions
Actions (login required)
 |
View Item |