Modification to planarity is fixed parameter tractable
Peer reviewed, Journal article
Published version
Åpne
Permanent lenke
https://hdl.handle.net/1956/23373Utgivelsesdato
2019Metadata
Vis full innførselSamlinger
Originalversjon
https://doi.org/10.4230/lipics.stacs.2019.28Sammendrag
A replacement action is a function L that maps each k-vertex labeled graph to another k-vertex graph. We consider a general family of graph modification problems, called L-Replacement to C, where the input is a graph G and the question is whether it is possible to replace in G some k-vertex subgraph H of it by L(H) so that the new graph belongs to the graph class C. L-Replacement to C can simulate several modification operations such as edge addition, edge removal, edge editing, and diverse completion and superposition operations. In this paper, we prove that for any action L, if C is the class of planar graphs, there is an algorithm that solves L-Replacement to C in O(|G| 2 ) steps. We also present several applications of our approach to related problems.