IMSc Webinar

New Directions in Parameterized Deletion Problems (Synopsis Talk)

Ashwin Jacob

IMSc

Vertex deletion problems, where we modify a graph by deleting vertices to
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.