Skip to Main content Skip to Navigation
Conference papers

An FPT-Algorithm for Recognizing k-Apices of Minor-Closed Graph Classes

Ignasi Sau Valls 1 Giannos Stamoulis 2 Dimitrios M. Thilikos 1
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : Let G be a graph class. We say that a graph G is a k-apex of G if G contains a set S of at most k vertices such that G \ S belongs to G. We prove that if G is minor-closed, then there is an algorithm that either returns a set S certifying that G is a k-apex of G or reports that such a set does not exist, in 2 poly(k) n 3 time. Here poly is a polynomial function whose degree depends on the maximum size of a minor-obstruction of G, i.e., the minor-minimal set of graphs not belonging to G. In the special case where G excludes some apex graph as a minor, we give an alternative algorithm running in 2 poly(k) n 2 time.
Document type :
Conference papers
Complete list of metadata

Cited literature [51 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-02991704
Contributor : Isabelle Gouat <>
Submitted on : Friday, November 6, 2020 - 10:06:49 AM
Last modification on : Monday, December 14, 2020 - 5:27:16 PM
Long-term archiving on: : Sunday, February 7, 2021 - 6:26:49 PM

File

LIPIcs-ICALP-2020-95.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Collections

Citation

Ignasi Sau Valls, Giannos Stamoulis, Dimitrios M. Thilikos. An FPT-Algorithm for Recognizing k-Apices of Minor-Closed Graph Classes. 47th International Colloquium on Automata, Languages, and Programming (ICALP), Jul 2020, Saarbrücken, Germany. pp.95:1-95:20, ⟨10.4230/LIPIcs.ICALP.2020.95⟩. ⟨lirmm-02991704⟩

Share

Metrics

Record views

57

Files downloads

32