Modification to Planarity is Fixed Parameter Tractable - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2019

Modification to Planarity is Fixed Parameter Tractable

Abstract

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.
Fichier principal
Vignette du fichier
LIPIcs-STACS-2019-28.pdf (844.28 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

lirmm-02342768 , version 1 (01-11-2019)

Licence

Attribution

Identifiers

Cite

Fedor V. Fomin, Petr A. Golovach, Dimitrios M. Thilikos. Modification to Planarity is Fixed Parameter Tractable. STACS 2019 - 36th International Symposium on Theoretical Aspects of Computer Science, Mar 2019, Berlin, Germany. pp.28:1--28:17, ⟨10.4230/LIPIcs.STACS.2019.28⟩. ⟨lirmm-02342768⟩
44 View
79 Download

Altmetric

Share

Gmail Facebook X LinkedIn More