Thursday, January 13 2022
14:00 - 15:00

Vertex deletion problems, where we modify a graph by deleting vertices toobtain a graph in a simpler class, is a well-studied optimization problemin all algorithmic paradigms including classical, approximation andparameterized complexity. In this thesis we investigate vertex deletionproblems in the following directions.In the first direction, we initiate the study of a natural variation of theproblem of deletion to {\it scattered graph classes} where we want todelete at most $k$ vertices so that in the resulting graph, each connectedcomponent belongs to one of a fixed number of graph classes. We show thatthis problem is non-uniformly fixed-parameter tractable (FPT) when thedeletion problem corresponding to each of the finite classes is known to beFPT and the properties that a graph belongs to any of the classes isexpressible in Counting Monodic Second Order (CMSO) logic. While this isshown using some black box theorems in parameterized complexity, we providea $2^{poly(k)}n^{\OO(1)}$ FPT algorithm when each of the graph classes hasa finite forbidden set. Later, we do a deep dive on pairs of specific graphclasses ($\Pi_1, \Pi_2$) in which we would like the connected components ofthe resulting graph to belong to, and design simpler and more efficient FPTalgorithms.In the second direction, we look at the associated structuralparameterizations for problems where the parameter is the deletion distanceto a graph class. Generally such problems are studied under the assumptionthat you are given a deletion set of size $k$ as input. If the problem offinding such a deletion set is known to the FPT, we can use it to find sucha set. The running time would be the sum of the running times for findingthe set and the algorithm where the modulator is assumed to be given. Formost parameterizations, assuming that a modulator is given is reasonablebut in cases where the running time for the former is significant, this isnot. We examine one such parameter, deletion distance to chordal graph. Forproblems like {\sc Vertex Cover}, {\sc Feedback Vertex Set}, {\sc Odd CycleTransversal} and so on, we provide an algorithm that either identifies thatthere is no chordal deletion set of size $k$ or give a$2^{\OO(k)}n^{\OO(1)}$ algorithm to solve them without finding themodulator.In the third direction, we investigate vertex deletion problems where thedeletion set also satisfies additional constraints. - We consider the casewhere the deletion set has the additional property of forming anindependent set. Such problems are called conflict-free problems and theyhave already been studied for various problems such as {\sc Conflict-FreeVertex Cover}, {\sc Conflict-Free Feedback Vertex Set}. We look at theconflict-free version of {\sc Set Cover} which, while not a graph problem,generalizes various deletion problems in which the deletion set coversforbidden sets such as {\sc Vertex Cover}. We look at variousparameterizations of {\sc Conflict-Free Set Cover} under various conditionsand provide upper and lower bounds.- We also study vertex deletion problems where the deletion set has theadditional property of forming a fair set. A $d$-fair set $S \subseteqV(G)$ is such that for very $v \in V(G)$, $|N(v) \cap S| \leq d$. We lookat vertex deletion problems such as {\sc Fair Vertex Cover}, {\sc FairFeedback Vertex Set} and give FPT and kernel results.

Download as iCalendar

Done