Fixed-Parameter Sensitivity Oracles
summary
Proposes fixed-parameter sensitivity oracles that preprocess a graph for up to f simultaneous edge failures while keeping parameter k fixed. For vertex cover the paper builds an equivalent kernel and gives a data structure with space 3^{F+K} and query 2^F, an alternative with query K^2 but preprocessing exponential in K, and a polynomial-space (O(K^2)) version with query ~1.274^K. For k‑path it gives a randomized oracle with space ~k^{F+1}, preprocessing ~1.657^K, query O(F^2), plus a sampled-subgraph tradeoff; for distances it produces F-independent linear-size preservers when allowing an additive k slack.
AI-written summary · about