Alladi Ramakrishnan Hall

New Directions in Parameterized Deletion Problems

Ashwin Jacob

Ben-Gurion University, Israel

This will be a hybrid meeting. Use the following link to join virtually.

zoom.us/j/99670507398

Abstract: In vertex deletion problems, we have an input graph, and we aim to find a set of k vertices such that the rest of the graph belongs to some graph class. These problems are well-studied with examples including VERTEX COVER, FEEDBACK VERTEX SET, and ODD CYCLE TRANSVERSAL.
In this thesis, we investigate vertex deletion problems in the following directions.

In the first direction, we initiate the study of a natural variation of the problem of deletion to scattered graph classes. Here, we want to delete at most k vertices so that each connected component belongs to at least one of a fixed number of graph classes in the resulting graph. We give FPT algorithms for deletion to scattered graph classes when deletion to each class is FPT, and the property that a graph belongs to each class is CMSO expressible. We then give a faster FPT algorithm for the case when each class has a finite forbidden set. Later, we do a deep dive on pairs of specific graph classes to which we would like the connected components of the resulting graph to belong and design simpler and more efficient FPT algorithms.

In the second direction, we look at several optimization problems where the parameter is the deletion distance to a graph class. Generally, such problems are studied assuming we are given a deletion set of size k as input. However, there are cases where the running time for finding the modulator is significant enough to pay attention to. We focus on one such parameter: deletion distance to chordal graphs. We develop an algorithmic framework for problems such as VERTEX COVER, FEEDBACK VERTEX SET and ODD CYCLE TRANSVERSAL that either identifies that there is no chordal deletion set of size k or gives a 2^{O(k)}n^{O(1)} algorithm to solve them. We also give FPT algorithms for other problems like LIST COLORING and variants of DOMINATING SET when parameterized by deletion distance to specific graph classes.

In the third direction, we investigate vertex deletion problems where the deletion set is also required to satisfy additional constraints. Specifically, we study the parameterized complexity of SET-COVER where there is an underlying graph on the sets, and we require that the solution is also an independent set. We also study vertex deletion problems where the deletion set is required to form a fair set, where we don't want too many neighbours of any vertex in the set.