Report
Fixed-Parameter Sensitivity Oracles
| العنوان: | Fixed-Parameter Sensitivity Oracles |
|---|---|
| المؤلفون: | Bilò, Davide, Casel, Katrin, Choudhary, Keerti, Cohen, Sarel, Friedrich, Tobias, Lagodzinski, J. A. Gregor, Schirneck, Martin, Wietheger, Simon |
| سنة النشر: | 2021 |
| المجموعة: | Computer Science |
| مصطلحات موضوعية: | Computer Science - Data Structures and Algorithms |
| الوصف: | We combine ideas from distance sensitivity oracles (DSOs) and fixed-parameter tractability (FPT) to design sensitivity oracles for FPT graph problems. An oracle with sensitivity $f$ for an FPT problem $\Pi$ on a graph $G$ with parameter $k$ preprocesses $G$ in time $O(g(f,k) \cdot \textsf{poly}(n))$. When queried with a set $F$ of at most $f$ edges of $G$, the oracle reports the answer to the $\Pi$-with the same parameter $k$-on the graph $G-F$, i.e., $G$ deprived of $F$. The oracle should answer queries in a time that is significantly faster than merely running the best-known FPT algorithm on $G-F$ from scratch. We mainly design sensitivity oracles for the $k$-Path and the $k$-Vertex Cover problem. Following our line of research connecting fault-tolerant FPT and shortest paths problems, we also introduce parameterization to the computation of distance preservers. We study the problem, given a directed unweighted graph with a fixed source $s$ and parameters $f$ and $k$, to construct a polynomial-sized oracle that efficiently reports, for any target vertex $v$ and set $F$ of at most $f$ edges, whether the distance from $s$ to $v$ increases at most by an additive term of $k$ in $G-F$. Comment: 19 pages, 1 figure, abstract shortened to meet ArXiv requirements; accepted at ITCS'22 |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2112.03059 |
| رقم الانضمام: | edsarx.2112.03059 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |