Parameterized complexity of fair deletion problems II
share
Vertex deletion problems are those where given a graph G and a graph property π, the goal is to find a subset of vertices W such that G W satisfies property π. Typically, we want to minimize size of the deletion set W. Unlike this, in fair vertex deletion problems we change the objective: we minimize the maximum number of vertices deleted in neighborhood of any vertex. When the property π is expressible by an MSO formula we refer to this special case as to the MSO fair vertex deletion problem. We prove that there is an FPT algorithm for the MSO fair vertex deletion problem parametrized by the twin cover number. We study parameterized complexity of the Fair Vertex Cover (FairVC) problem. It turns out that the FairVC problem is among the simplest problems with respect to the property π (here π describes an edgeless graph). We prove that the FairVC problem is W[1]-hard with parameterization by both treedepth and feedback vertex set of the input graph. On the positive side, we provide an FPT algorithm for the FairVC problem parameterized by modular width.
READ FULL TEXT