Deletion and Elimination to Hereditary Graph classes
Vertex-deletion problems have been at the heart of parameterized complexity throughout its history where the most commonly used parameter is the size of the modulator (deletion set). Recent years there have been attempts to measure the modulator in ways other than the size which is significantly smaller than the size of the modulator. In 2016, Bulian and Dawar introduced elimination distance to a graph class \(H\). In this talk we discuss elimination distance and argue that for any hereditary graph class \(H\) which is CMSO expressible and closed under disjoint union, the following statements are equivalent.
- Vertex Deletion to \(H\) parameterised by the size of the modulator is FPT.
- Elimination Distance to \(H\) parameterised by the elimination distance is FPT.
- Vertex Deletion to \(H\) parameterised by the elimination distance is FPT.
This is a joint work with Akanksha Agrawal, Lawqueen Kanesh, Daniel Lokshtanov, M. S. Ramanujan, Saket Saurabh, and Meirav Zehavi.