Thursday, January 13 2022

14:00 - 15:00

14:00 - 15:00

obtain a graph in a simpler class, is a well-studied optimization problem

in all algorithmic paradigms including classical, approximation and

parameterized complexity. 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 {\it scattered graph classes} where we want to

delete at most $k$ vertices so that in the resulting graph, each connected

component belongs to one of a fixed number of graph classes. We show that

this problem is non-uniformly fixed-parameter tractable (FPT) when the

deletion problem corresponding to each of the finite classes is known to be

FPT and the properties that a graph belongs to any of the classes is

expressible in Counting Monodic Second Order (CMSO) logic. While this is

shown using some black box theorems in parameterized complexity, we provide

a $2^{poly(k)}n^{\OO(1)}$ FPT algorithm when each of the graph classes has

a finite forbidden set. Later, we do a deep dive on pairs of specific graph

classes ($\Pi_1, \Pi_2$) in which we would like the connected components of

the resulting graph to belong to, and design simpler and more efficient FPT

algorithms.

In the second direction, we look at the associated structural

parameterizations for problems where the parameter is the deletion distance

to a graph class. Generally such problems are studied under the assumption

that you are given a deletion set of size $k$ as input. If the problem of

finding such a deletion set is known to the FPT, we can use it to find such

a set. The running time would be the sum of the running times for finding

the set and the algorithm where the modulator is assumed to be given. For

most parameterizations, assuming that a modulator is given is reasonable

but in cases where the running time for the former is significant, this is

not. We examine one such parameter, deletion distance to chordal graph. For

problems like {\sc Vertex Cover}, {\sc Feedback Vertex Set}, {\sc Odd Cycle

Transversal} and so on, we provide an algorithm that either identifies that

there is no chordal deletion set of size $k$ or give a

$2^{\OO(k)}n^{\OO(1)}$ algorithm to solve them without finding the

modulator.

In the third direction, we investigate vertex deletion problems where the

deletion set also satisfies additional constraints. - We consider the case

where the deletion set has the additional property of forming an

independent set. Such problems are called conflict-free problems and they

have already been studied for various problems such as {\sc Conflict-Free

Vertex Cover}, {\sc Conflict-Free Feedback Vertex Set}. We look at the

conflict-free version of {\sc Set Cover} which, while not a graph problem,

generalizes various deletion problems in which the deletion set covers

forbidden sets such as {\sc Vertex Cover}. We look at various

parameterizations of {\sc Conflict-Free Set Cover} under various conditions

and provide upper and lower bounds.

- We also study vertex deletion problems where the deletion set has the

additional property of forming a fair set. A $d$-fair set $S \subseteq

V(G)$ is such that for very $v \in V(G)$, $|N(v) \cap S| \leq d$. We look

at vertex deletion problems such as {\sc Fair Vertex Cover}, {\sc Fair

Feedback Vertex Set} and give FPT and kernel results.

Done