2026-07-22T06:49:50Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12755 2024-03-06T10:50:42Z ddc:004 open_access

Elimination Distance to Bounded Degree on Planar Graphs Lindermayr, Alexander Siebertz, Sebastian Vigny, Alexandre Elimination distance parameterized complexity structural graph theory We study the graph parameter elimination distance to bounded degree, which was introduced by Bulian and Dawar in their study of the parameterized complexity of the graph isomorphism problem. We prove that the problem is fixed-parameter tractable on planar graphs, that is, there exists an algorithm that given a planar graph G and integers d and k decides in time f(k,d)⋅ n^c for a computable function f and constant c whether the elimination distance of G to the class of degree d graphs is at most k. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Alexander Lindermayr and Sebastian Siebertz and Alexandre Vigny 2020 Is Part Of LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2020.65 urn:nbn:de:0030-drops-127557 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.65 eng https://creativecommons.org/licenses/by/3.0/legalcode