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]. There has been a subsequent series of results on the fixed-parameter tractability of elimination distance to various graph classes. However, one class of graph classes to which the computation of elimination distance has remained open is the class of graphs that are characterized by the exclusion of a family ${\cal F}$ of finite graphs as topological minors. In this paper, we settle this question by showing that the problem of determining elimination distance to such graphs is also fixed-parameter tractable.
翻译:在关于参数化图解问题的文献中,近年来更加努力地探索图形编辑-距离的新概念,这些新概念比特定图类的调制器大小更强大。在研究的这一行中,Bulian和Dawar[Algorithmica,2016年]引入了消除距离的概念,并表明决定某一图是否将最多以美元消除距离到任何不公开的图类的固定参数为以美元[Algorithmica,2017年]的可移动参数。随后在固定参数距离至各种图类的消除距离的可移动性方面产生了一系列结果。然而,计算消除距离仍然开放的一类图类是将家庭用美元/卡费作为表层未成年人排除的图表。在本文中,我们通过表明确定消除距离的问题与这些图类的距离也是固定参数可移动的。