2026-07-22T08:35:53Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9611 2024-03-06T10:44:32Z ddc:004 open_access

Recovering Sparse Graphs Gajarský, Jakub Král', Daniel model checking degenerate graphs interpretations bounded expansion We construct a fixed parameter algorithm parameterized by d and k that takes as an input a graph G' obtained from a d-degenerate graph G by complementing on at most k arbitrary subsets of the vertex set of G and outputs a graph H such that G and H agree on all but f(d,k) vertices. Our work is motivated by the first order model checking in graph classes that are first order interpretable in classes of sparse graphs. We derive as a corollary that if G is a graph class with bounded expansion, then the first order model checking is fixed parameter tractable in the class of all graphs that can obtained from a graph G in G by complementing on at most k arbitrary subsets of the vertex set of G; this implies an earlier result that the first order model checking is fixed parameter tractable in graph classes interpretable in classes of graphs with bounded maximum degree. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jakub Gajarský and Daniel Král' 2018 Is Part Of LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2018.29 urn:nbn:de:0030-drops-96111 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.29 eng https://creativecommons.org/licenses/by/3.0/legalcode