2026-08-17T17:24:57Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5586 2024-03-06T10:36:36Z ddc:004 open_access

Fixed-parameter Tractable Distances to Sparse Graph Classes Bulian, Jannis Dawar, Anuj parameterized complexity fixed-parameter tractable distance graph theory sparse graphs graph minor nowhere dense We show that for various classes 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 G to 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 G to a minor-closed class C is FPT. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jannis Bulian and Anuj Dawar 2015 Is Part Of LIPIcs, Volume 43, 10th International Symposium on Parameterized and Exact Computation (IPEC 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2015.236 urn:nbn:de:0030-drops-55865 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2015.236 eng https://creativecommons.org/licenses/by/3.0/legalcode