Fomin, Fedor V. ;
Golovach, Petr A. ;
Stamoulis, Giannos ;
Thilikos, Dimitrios M.
An Algorithmic MetaTheorem for Graph Modification to Planarity and FOL
Abstract
In general, a graph modification problem is defined by a graph modification operation ⊠ and a target graph property 𝒫. Typically, the modification operation ⊠ may be vertex removal, edge removal, edge contraction, or edge addition and the question is, given a graph G and an integer k, whether it is possible to transform G to a graph in 𝒫 after applying k times the operation ⊠ on G. This problem has been extensively studied for particilar instantiations of ⊠ and 𝒫. In this paper we consider the general property 𝒫_ϕ of being planar and, moreover, being a model of some FirstOrder Logic sentence ϕ (an FOLsentence). We call the corresponding metaproblem Graph ⊠Modification to Planarity and ϕ and prove the following algorithmic metatheorem: there exists a function f: ℕ² → ℕ such that, for every ⊠ and every FOL sentence ϕ, the Graph ⊠Modification to Planarity and ϕ is solvable in f(k,ϕ)⋅n² time. The proof constitutes a hybrid of two different classic techniques in graph algorithms. The first is the irrelevant vertex technique that is typically used in the context of Graph Minors and deals with properties such as planarity or surfaceembeddability (that are not FOLexpressible) and the second is the use of Gaifman’s Locality Theorem that is the theoretical base for the metaalgorithmic study of FOLexpressible problems.
BibTeX  Entry
@InProceedings{fomin_et_al:LIPIcs:2020:12917,
author = {Fedor V. Fomin and Petr A. Golovach and Giannos Stamoulis and Dimitrios M. Thilikos},
title = {{An Algorithmic MetaTheorem for Graph Modification to Planarity and FOL}},
booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)},
pages = {51:151:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771627},
ISSN = {18688969},
year = {2020},
volume = {173},
editor = {Fabrizio Grandoni and Grzegorz Herman and Peter Sanders},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12917},
URN = {urn:nbn:de:0030drops129172},
doi = {10.4230/LIPIcs.ESA.2020.51},
annote = {Keywords: Graph modification Problems, Algorithmic metatheorems, First Order Logic, Irrelevant vertex technique, Planar graphs, Surface embeddable graphs}
}
26.08.2020
Keywords: 

Graph modification Problems, Algorithmic metatheorems, First Order Logic, Irrelevant vertex technique, Planar graphs, Surface embeddable graphs 
Seminar: 

28th Annual European Symposium on Algorithms (ESA 2020)

Issue date: 

2020 
Date of publication: 

26.08.2020 