#### 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.

Done