Fixed-Parameter Sensitivity Oracles

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 Π on a graph G with parameter k preprocesses G in time O(g(f, k) · poly(n)). When queried with a set F of at most f edges of G, the oracle reports the answer to the Π - 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 design sensitivity oracles for the k-Path and the k-Vertex Cover problem. Our first oracle for k-Path has size O(kf+1) and query time O(f min{f, log(f) + k}). We use a technique inspired by the work of Weimann and Yuster [FOCS 2010, TALG 2013] on distance sensitivity problems to reduce the space to O ((Eqaution presented) fk · log n) at the expense of increasing the query time to O((Eqaution presented) f min{f, k} · log n). Both oracles can be modified to handle vertex-failures, but we need to replace k with 2k in all the claimed bounds. Regarding k-Vertex Cover, we design three oracles offering different trade-offs between the size and the query time. The first oracle takes O(3f+k) space and has O(2f) query time, the second one has a size of O(2f+k2+k) and a query time of O(f+k2); finally, the third one takes O(fk + k2) space and can be queried in time O(1.2738k + f). All our oracles are computable in time (at most) proportional to their size and the time needed to detect a k-path or k-vertex cover, respectively. We also provide an interesting connection between k-Vertex Cover and the fault-tolerant shortest path problem, by giving a DSO of size O(poly(f, k) · n) with query time in O(poly(f, k)), where k is the size of a vertex cover. Following our line of research connecting fault-tolerant FPT and shortest paths problems, we 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. The oracle size is O(2kk2 · n), while the time needed to answer a query is O(2kfωkω), where ω < 2.373 is the matrix multiplication exponent. The second problem we study is about the construction of bounded-stretch fault-tolerant preservers. We construct a subgraph with O(2fk+f+k k · n) edges that preserves those s-v-distances that do not increase by more than k upon failure of F. This improves significantly over the (Eqaution presented) bound in the unparameterized case by Bodwin et al. [ICALP 2017].