An FPT-Algorithm for Recognizing k-Apices of Minor-Closed Graph Classes - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Communication Dans Un Congrès Année : 2020

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

Résumé

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.
Fichier principal
Vignette du fichier
LIPIcs-ICALP-2020-95.pdf (950.9 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

lirmm-02991704 , version 1 (06-11-2020)

Licence

Paternité

Identifiants

Citer

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

Altmetric

Partager

Gmail Facebook X LinkedIn More