An FPT algorithm for elimination distance to bounded degree graphs

Agrawal, A. and Kanesh, L. and Panolan, Fahad and et al, . (2021) An FPT algorithm for elimination distance to bounded degree graphs. In: 38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021, 16 March 2021 through 19 March 2021, Virtual, Saarbrucken.

Text
Leibniz_International_Proceedings_1.pdf - Published Version
Available under License Creative Commons Attribution.
Download (779kB)

Abstract

In the literature on parameterized graph problems, there has been an increased effort in recent years aimed at exploring novel notions of graph edit-distance that are more powerful than the size of a modulator to a specific graph class. In this line of research, Bulian and Dawar Algorithmica, 2016 introduced the notion of elimination distance and showed that deciding whether a given graph has elimination distance at most k to any minor-closed class of graphs is fixed-parameter tractable parameterized by k Algorithmica, 2017. They showed that Graph Isomorphism parameterized by the elimination distance to bounded degree graphs is fixed-parameter tractable and asked whether determining the elimination distance to the class of bounded degree graphs is fixed-parameter tractable. Recently, Lindermayr et al. MFCS 2020 obtained a fixed-parameter algorithm for this problem in the special case where the input is restricted to K5-minor free graphs. In this paper, we answer the question of Bulian and Dawar in the affirmative for general graphs. In fact, we give a more general result capturing elimination distance to any graph class characterized by a finite set of graphs as forbidden induced subgraphs. Â© Akanksha Agrawal, Lawqueen Kanesh, Fahad Panolan, M. S. Ramanujan, and Saket Saurabh; licensed under Creative Commons License CC-BY 4.0.

[error in script]

IITH Creators:

IITH Creators	ORCiD
Panolan, Fahad	https://orcid.org/0000-0001-6213-8687

Item Type:

Conference or Workshop Item (Paper)

Additional Information:

Funding Akanksha Agrawal: Supported by New Faculty Initiative Grant, IIT Madras, Chennai, India. Fahad Panolan: Supported by Seed grant, IIT Hyderabad (SG/IITH/F224/2020-21/SG-79). M. S. Ramanujan: Supported by EPSRC grant EP/V007793/1. Saket Saurabh: Supported by funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No. 819416) and Swarnajayanti Fellowship grant DST/SJF/MSA-01/2017-18.

Uncontrolled Keywords:

Elimination Distance, Fixed-parameter Tractability, Graph Modification

Subjects:

Computer science

Divisions:

Department of Computer Science & Engineering

Depositing User:

. LibTrainee 2021

Date Deposited:

04 Aug 2022 13:19

Last Modified:

04 Aug 2022 13:19