TY - JOUR
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:
© 2022 Association for Computing Machinery.
PY - 2023/2/1
Y1 - 2023/2/1
N2 - 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 deletion, edge deletion, 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 the operation k times on G. This problem has been extensively studied for particular instantiations of and . In this article, we consider the general property of being planar and, additionally, being a model of some First-Order Logic (FOL) 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 : ĝ.,•2 → ĝ.,• such that, for every and every FOL-sentence , the Graph -Modification to Planarity and is solvable in f(k,||)g 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 . Typically, the modification operation may be vertex deletion, edge deletion, 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 the operation k times on G. This problem has been extensively studied for particular instantiations of and . In this article, we consider the general property of being planar and, additionally, being a model of some First-Order Logic (FOL) 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 : ĝ.,•2 → ĝ.,• such that, for every and every FOL-sentence , the Graph -Modification to Planarity and is solvable in f(k,||)g 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
UR - http://www.scopus.com/inward/record.url?scp=85148040040&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85148040040&partnerID=8YFLogxK
U2 - 10.1145/3571278
DO - 10.1145/3571278
M3 - Article
AN - SCOPUS:85148040040
SN - 1942-3454
VL - 14
JO - ACM Transactions on Computation Theory
JF - ACM Transactions on Computation Theory
IS - 3-4
M1 - 13
ER -