We show that for various classes $mathcal{C}$ of sparse graphs, and several measures of distance to such classes (such as edit distance and elimination distance), the problem of determining the distance of a given graph $small{G}$ to $mathcal{C}$ is fixed-parameter tractable. The results are based on two general techniques. The first of these, building on recent work of Grohe et al. establishes that any class of graphs that is slicewise nowhere dense and slicewise first-order definable is FPT. The second shows that determining the elimination distance of a graph $small{G}$ to a minor-closed class $mathcal{C}$ is FPT. We demonstrate that several prior results (of Golovach, Moser and Thilikos and Mathieson) on the fixed-parameter tractability of distance measures are special cases of our first method.
展开▼
机译：我们表明，对于稀疏图的各种类别$ mathcal {C} $以及到此类距离的几种度量（例如编辑距离和消除距离），确定给定图$ small {G的距离的问题} $到$ mathcal {C} $是固定参数易处理的。结果基于两种通用技术。第一个是基于Grohe等人最近的工作。确定切片无处密集且切片可一阶定义的任何图类都是FPT。第二个步骤显示确定图$ small {G} $到次要封闭类$ mathcal {C} $的消除距离是FPT。我们证明，关于距离测度的固定参数易处理性的几个先前结果（Golovach，Moser和Thilikos和Mathieson的结果）是我们第一种方法的特殊情况。
展开▼
