TY - GEN

T1 - An algorithmic meta-theorem for graph modification to planarity and FOL

AU - Fomin, Fedor V.

AU - Golovach, Petr A.

AU - Stamoulis, Giannos

AU - Thilikos, Dimitrios M.

N1 - Publisher Copyright:
© Fedor V. Fomin, Petr A. Golovach, Giannos Stamoulis, and Dimitrios M. Thilikos.

PY - 2020/8/1

Y1 - 2020/8/1

N2 - In general, a graph modification problem is defined by a graph modification operation and a target graph property P. 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 P after applying k times the operation on G. This problem has been extensively studied for particilar instantiations of and P. In this paper we consider the general property Pφ of being planar and, moreover, being a model of some First-Order Logic sentence φ (an FOL-sentence). We call the corresponding meta-problem Graph -Modification to Planarity and φ and prove the following algorithmic meta-theorem: there exists a function f : N2 → N such that, for every and every FOL sentence φ, the Graph Modification to Planarity and φ is solvable in f(k, |φ|) · n2 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.

AB - In general, a graph modification problem is defined by a graph modification operation and a target graph property P. 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 P after applying k times the operation on G. This problem has been extensively studied for particilar instantiations of and P. In this paper we consider the general property Pφ of being planar and, moreover, being a model of some First-Order Logic sentence φ (an FOL-sentence). We call the corresponding meta-problem Graph -Modification to Planarity and φ and prove the following algorithmic meta-theorem: there exists a function f : N2 → N such that, for every and every FOL sentence φ, the Graph Modification to Planarity and φ is solvable in f(k, |φ|) · n2 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.

KW - Algorithmic meta-theorems

KW - First Order Logic

KW - Graph modification Problems

KW - Irrelevant vertex technique

KW - Planar graphs

KW - Surface embeddable graphs

UR - http://www.scopus.com/inward/record.url?scp=85092505404&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85092505404&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.ESA.2020.51

DO - 10.4230/LIPIcs.ESA.2020.51

M3 - Conference contribution

AN - SCOPUS:85092505404

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 28th Annual European Symposium on Algorithms, ESA 2020

A2 - Grandoni, Fabrizio

A2 - Herman, Grzegorz

A2 - Sanders, Peter

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 28th Annual European Symposium on Algorithms, ESA 2020

Y2 - 7 September 2020 through 9 September 2020

ER -