License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2022.23
URN: urn:nbn:de:0030-drops-156196
Go to the corresponding LIPIcs Volume Portal

Bilò, Davide ; Casel, Katrin ; Choudhary, Keerti ; Cohen, Sarel ; Friedrich, Tobias ; Lagodzinski, J.A. Gregor ; Schirneck, Martin ; Wietheger, Simon

Fixed-Parameter Sensitivity Oracles

LIPIcs-ITCS-2022-23.pdf (0.8 MB)


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(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 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(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 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(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 bounded-stretch fault-tolerant preservers. We construct a subgraph with O(2^{fk+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 Õ(f n^{2-1/(2^f)}) bound in the unparameterized case by Bodwin et al. [ICALP 2017].

BibTeX - Entry

  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 =	{{Fixed-Parameter Sensitivity Oracles}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{23:1--23:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-156196},
  doi =		{10.4230/LIPIcs.ITCS.2022.23},
  annote =	{Keywords: data structures, distance preservers, distance sensitivity oracles, fault tolerance, fixed-parameter tractability, k-path, vertex cover}

Keywords: data structures, distance preservers, distance sensitivity oracles, fault tolerance, fixed-parameter tractability, k-path, vertex cover
Collection: 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Issue Date: 2022
Date of publication: 25.01.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI