Agrawal, Akanksha ;
Ramanujan, M. S.
On the Parameterized Complexity of Clique Elimination Distance
Abstract
Bulian and Dawar [Algorithmica, 2016] introduced the notion of elimination distance in an effort to define new tractable parameterizations for graph problems and showed that deciding whether a given graph has elimination distance at most k to any minorclosed class of graphs is fixedparameter tractable parameterized by k [Algorithmica, 2017].
In this paper, we consider the problem of computing the elimination distance of a given graph to the class of cluster graphs and initiate the study of the parameterized complexity of a more general version  that of obtaining a modulator to such graphs. That is, we study the (η,Clq)Elimination Deletion problem ((η,Clq)ED Deletion) where, for a fixed η, one is given a graph G and k ∈ ℕ and the objective is to determine whether there is a set S ⊆ V(G) such that the graph GS has elimination distance at most η to the class of cluster graphs.
Our main result is a polynomial kernelization (parameterized by k) for this problem. As components in the proof of our main result, we develop a k^𝒪(η k + η²)n^𝒪(1)time fixedparameter algorithm for (η,Clq)ED Deletion and a polynomialtime factormin{𝒪(η⋅ opt⋅ log² n),opt^𝒪(1)} approximation algorithm for the same problem.
BibTeX  Entry
@InProceedings{agrawal_et_al:LIPIcs:2020:13304,
author = {Akanksha Agrawal and M. S. Ramanujan},
title = {{On the Parameterized Complexity of Clique Elimination Distance}},
booktitle = {15th International Symposium on Parameterized and Exact Computation (IPEC 2020)},
pages = {1:11:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771726},
ISSN = {18688969},
year = {2020},
volume = {180},
editor = {Yixin Cao and Marcin Pilipczuk},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/13304},
URN = {urn:nbn:de:0030drops133043},
doi = {10.4230/LIPIcs.IPEC.2020.1},
annote = {Keywords: Elimination Distance, Cluster Graphs, Kernelization}
}
04.12.2020
Keywords: 

Elimination Distance, Cluster Graphs, Kernelization 
Seminar: 

15th International Symposium on Parameterized and Exact Computation (IPEC 2020)

Issue date: 

2020 
Date of publication: 

04.12.2020 