文章基本信息

标题：An Algorithmic Meta-Theorem for Graph Modification to Planarity and FOL
本地全文：下载
作者：Fedor V. Fomin ; Petr A. Golovach ; Giannos Stamoulis 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：173
页码：51:1-51:17
DOI：10.4230/LIPIcs.ESA.2020.51
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：In general, a graph modification problem is defined by a graph modification operation âS and a target graph property ð'«. Typically, the modification operation âS 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 âS on G. This problem has been extensively studied for particilar instantiations of âS and ð'«. In this paper we consider the general property ð'«_Ï. of being planar and, moreover, being a model of some First-Order Logic sentence Ï. (an FOL-sentence). We call the corresponding meta-problem Graph âS -Modification to Planarity and Ï. and prove the following algorithmic meta-theorem: there exists a function f: â".Â² â' â". such that, for every âS and every FOL sentence Ï., the Graph âS -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 surface-embeddability (that are not FOL-expressible) and the second is the use of Gaifmanâs Locality Theorem that is the theoretical base for the meta-algorithmic study of FOL-expressible problems.
关键词：Graph modification Problems; Algorithmic meta-theorems; First Order Logic; Irrelevant vertex technique; Planar graphs; Surface embeddable graphs