APRRSS

F-M-DELETION paramétré par la largeur arborescente.

13.10.2017
Beteiligte : Julien Baste (ATER LIP6)
Résumé: Étant donnée une collection de graphes F, le problème de F-M-DELETION consiste, étant donnés un graphe G=(V,E) et un entier k, à décider s'il existe un ensemble S de sommets de G de taille au plus k tel que G privé des sommets de S ne contienne aucun graphe de F comme mineur. Ce problème est une généralisation de problèmes plus classiques tels que VERTEX COVER (F={K_2}), FEEDBACK VERTEX SET (F={K_3}), ou VERTEX PLANARIZATION (F={K_5, K_{3,3} }). Nous nous intéressons à la complexité paramétrée du problème F-M-DELETION lorsque le paramètre est la largeur arborescente de G (noté tw). Notre objectif est de déterminer, pour chaque famille F, quelle est la plus petite fonction f tel que F-M-DELETION puisse être résolu en temps f(tw)*poly(n) sur un graphe à n sommets.
Durée: 50 min + questions

Mehr Informationen hier …
Romain.Demangeon (at) nulllip6.fr
Mentions légales
Plan