The Library
A fixed-parameter tractable algorithm for elimination distance to bounded degree graphs
Tools
Agrawal, Akanksha, Kanesh, Lawqueen, Panolan, Fahad, Ramanujan, M. S. and Saurabh, Saket (2022) A fixed-parameter tractable algorithm for elimination distance to bounded degree graphs. SIAM Journal on Discrete Mathematics, 36 (2). pp. 911-921. doi:10.1137/21m1396824 ISSN 1095-7146.
|
PDF
WRAP-fixed-parameter-tractable-algorithm-elimination-bounded-degree-graphs-2022.pdf - Accepted Version - Requires a PDF viewer. Download (487Kb) | Preview |
Official URL: https://doi.org/10.1137/21m1396824
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 $K_5$-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.
Item Type: | Journal Article | ||||||
---|---|---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||
SWORD Depositor: | Library Publications Router | ||||||
Journal or Publication Title: | SIAM Journal on Discrete Mathematics | ||||||
Publisher: | Society for Industrial & Applied Mathematics (SIAM) | ||||||
ISSN: | 1095-7146 | ||||||
Official Date: | 7 April 2022 | ||||||
Dates: |
|
||||||
Volume: | 36 | ||||||
Number: | 2 | ||||||
Page Range: | pp. 911-921 | ||||||
DOI: | 10.1137/21m1396824 | ||||||
Status: | Peer Reviewed | ||||||
Publication Status: | Published | ||||||
Reuse Statement (publisher, data, author rights): | First Published in SIAM Journal on Discrete Mathematics in 36(2), 2022, published by the Society for Industrial and Applied Mathematics (SIAM)” Copyright © by SIAM. Unauthorized reproduction of this article is prohibited. | ||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||
Copyright Holders: | Copyright © 2021 by SIAMUnauthorized reproduction of this article is prohibited | ||||||
Date of first compliant deposit: | 9 June 2022 | ||||||
Date of first compliant Open Access: | 17 June 2022 |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year