TY - GEN
T1 - Modification to planarity is fixed parameter tractable
AU - Fomin, Fedor V.
AU - Golovach, Petr A.
AU - Thilikos, Dimitrios M.
N1 - Publisher Copyright:
© Fedor V. Fomin, Petr A. Golovach, and Dimitrios M. Thilikos.
PY - 2019/3/1
Y1 - 2019/3/1
N2 - 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.
AB - 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.
KW - Irrelevant vertex technique
KW - Modification problems
KW - Planar graphs
UR - http://www.scopus.com/inward/record.url?scp=85074909200&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85074909200&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.STACS.2019.28
DO - 10.4230/LIPIcs.STACS.2019.28
M3 - Conference contribution
AN - SCOPUS:85074909200
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019
A2 - Niedermeier, Rolf
A2 - Paul, Christophe
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019
Y2 - 13 March 2019 through 16 March 2019
ER -