Bilò, Davide ;
Casel, Katrin ;
Choudhary, Keerti ;
Cohen, Sarel ;
Friedrich, Tobias ;
Lagodzinski, J.A. Gregor ;
Schirneck, Martin ;
Wietheger, Simon
FixedParameter Sensitivity Oracles
Abstract
We combine ideas from distance sensitivity oracles (DSOs) and fixedparameter 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 GF, i.e., G deprived of F. The oracle should answer queries in a time that is significantly faster than merely running the bestknown FPT algorithm on GF from scratch.
We design sensitivity oracles for the kPath and the kVertex Cover problem. Our first oracle for kPath has size O(k^{f+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(({f+k}/f)^f ({f+k}/k)^k fk⋅log(n)) at the expense of increasing the query time to O(({f+k}/f)^f ({f+k}/k)^k f min{f,k}⋅log(n)). Both oracles can be modified to handle vertexfailures, but we need to replace k with 2k in all the claimed bounds.
Regarding kVertex Cover, we design three oracles offering different tradeoffs between the size and the query time. The first oracle takes O(3^{f+k}) space and has O(2^f) query time, the second one has a size of O(2^{f+k²+k}) and a query time of O(f+k²); finally, the third one takes O(fk+k²) space and can be queried in time O(1.2738^k + f). All our oracles are computable in time (at most) proportional to their size and the time needed to detect a kpath or kvertex cover, respectively. We also provide an interesting connection between kVertex Cover and the faulttolerant 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 faulttolerant 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 polynomialsized 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 GF. The oracle size is O(2^k k²⋅n), while the time needed to answer a query is O(2^k f^ω k^ω), where ω < 2.373 is the matrix multiplication exponent. The second problem we study is about the construction of boundedstretch faulttolerant preservers. We construct a subgraph with O(2^{fk+f+k} k ⋅ n) edges that preserves those svdistances that do not increase by more than k upon failure of F. This improves significantly over the Õ(f n^{21/(2^f)}) bound in the unparameterized case by Bodwin et al. [ICALP 2017].
BibTeX  Entry
@InProceedings{bilo_et_al:LIPIcs.ITCS.2022.23,
author = {Bil\`{o}, Davide and Casel, Katrin and Choudhary, Keerti and Cohen, Sarel and Friedrich, Tobias and Lagodzinski, J.A. Gregor and Schirneck, Martin and Wietheger, Simon},
title = {{FixedParameter Sensitivity Oracles}},
booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
pages = {23:123:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772174},
ISSN = {18688969},
year = {2022},
volume = {215},
editor = {Braverman, Mark},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/15619},
URN = {urn:nbn:de:0030drops156196},
doi = {10.4230/LIPIcs.ITCS.2022.23},
annote = {Keywords: data structures, distance preservers, distance sensitivity oracles, fault tolerance, fixedparameter tractability, kpath, vertex cover}
}
25.01.2022
Keywords: 

data structures, distance preservers, distance sensitivity oracles, fault tolerance, fixedparameter tractability, kpath, vertex cover 
Seminar: 

13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Issue date: 

2022 
Date of publication: 

25.01.2022 