A Fixed-Parameter Tractable Algorithm for Elimination Distance to Bounded Degree Graphs

Agrawal, Akanksha and Kanesh, Lawqueen and Panolan, Fahad and et al, . (2022) A Fixed-Parameter Tractable Algorithm for Elimination Distance to Bounded Degree Graphs. SIAM Journal on Discrete Mathematics, 36 (2). pp. 911-921. ISSN 0895-4801

Full text not available from this repository. (Request a copy)

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, 75 (2016), pp. 363-382] 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, 79 (2017), pp. 139-158]. 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, Siebertz, and Vigny [MFCS 2020, LIPIcs Leibniz Int. Proc. Inform. 170, Wadern Germany, 2020, 65] 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. © 2022 Society for Industrial and Applied Mathematics

[error in script]

IITH Creators:

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

Item Type:

Article

Additional Information:

\ast Received by the editors February 3, 2021; accepted for publication (in revised form) November 10, 2021; published electronically April 7, 2022. Extended abstract appeared at STACS 2021 [LIPIcs Leibniz Int. Proc. Inform. 187, Wadern, Germany, 2021, 5]. \bfF \bfu \bfn \bfd \bfi \bfn \bfg : Agrawal is supported by New Faculty Initiation Grant IIT Madras. Panolan is supported by Seed grant, IIT Hyderabad (SG/IITH/F224/2020-21/SG-79). Ramanujan is supported by Engineering and Physical Sciences Research Council's New Investigator Award (EP/V007793/1). Saurabh is supported by the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement 819416); and he also acknowledges the support of Swarnajayanti Fellowship grant DST/SJF/MSA-01/2017-18. https://doi.org/10.1137/21M1396824 \dagger Indian Institute of Technology Madras, Chennai, India (akanksha@cse.iitm.ac.in). \ddagger National University of Singapore, Singapore (lawqueen@comp.nus.edu.sg). \S Indian Institute of Technology, Hyderabad, India (panolan@iith.ac.in). \P University of Warwick, Warwick, UK (r.maadapuzhi-sridharan@warwick.ac.uk). \| University of Bergen, Norway and Institute of Mathematical Sciences, HBNI, India (saket@imsc. res.in).

Uncontrolled Keywords:

elimination distance; fixed-parameter tractability; graph modification

Subjects:

Computer science
Mathematics

Divisions:

Department of Computer Science & Engineering
Department of Mathematics

Depositing User:

. LibTrainee 2021

Date Deposited:

18 Jul 2022 13:12

Last Modified:

18 Jul 2022 13:12