Alladi Ramakrishnan Hall

Decremental fixed-parameter sensitivity oracles

Lawqueen Kanesh

IIT Jodhpur

In this talk, I will talk about decremental fixed-parameter sensitivity oracles for a number
of basic covering and packing problems on graphs. We give a sensitivity oracle that preprocesses the given graph in time f(k, l)n^O(1) such that, when
given a set of l edge deletions, the data structure decides in time f(k,l) whether the updated
graph is a positive instance of the problem. These results are obtained as a corollary of our central
result, which is the first decremental sensitivity oracle for Topological Minor Deletion problem
(cover all topological minors in the input graph that belong to a specified set, using k vertices).
Our methodology produces explicit bounds on the preprocessing and query times for several
problems. Moreover, when restricted to the class of bounded treewidth graphs, our preprocessing
and query times have only a polynomial dependence on the number of edges in the query.