Complexité Paramétrée Des Problèmes D’Arbres Couvrant Avec Des Contraintes Locales.

EasyChair Preprint 2648

Abstract

On s’intéresse ici au problème minimum subTree with Local Weights (MTLW) qui généralise
des problèmes de recherche d’un sous-arbre dans un graphe devant vérifier m
contraintes et minimiser un critère. Les m contraintes et le critère sont définis comme des fonctions prenant en entrée un nœud et un sous-ensemble des arêtes incidentes à ce noeud, et renvoyant un entier positif ou négatif. Elle sont calculables en
temps polynomial. Connaissant un sous-arbre du graphe, on calcule, pour chaque fonction, la somme, pour chaque noeud de l'arbre et chaque ensemble d'arêtes incidentes à ce noeud dans l'arbre la valeur de cette fonction, ce qui nous donne m + 1 valeurs. L'objectif du problème est de trouver un arbre minimisant la dernière somme et dont les m premières valeurs sont inférieures à m entiers donnés en entrée. Ce problème généralise de nombreux problèmes de recherche de sous-arbres de la littérature.

De manière générale, on peut s’interroger sur la complexité des problèmes de recherche d’un
arbre couvrant quand le graphe est proche d’un arbre. Une mesure classique de distance entre un graphe et un arbre est la largeur d'arbre. Il a été démontré que le problème de
Steiner et le problème de k-arbre couvrant de poids minimum sont FPT vis-à-vis de la largeur
d’arbre. Il semble donc naturel de vérifier le cas du problème général MTLW. On s'est également intéressé au nombre cyclomatique.

Dans cette présentation, nous présentons des résultats de complexité paramétrée vis-à-vis de ces deux paramètres pour MTLW. Ces résultats montrent en particulier que MTLW n'est pas FPT vis-à-vis de la largeur d'arbre ou du nombre cyclomatique, mais qu'en restreignant un peu les instances de ce problème, un algorithme FPT vis-à-vis de chacun des paramètres existe et démontre l'existence d'un algorithme FPT pour de nombreux problèmes de la littérature.

Keyphrases: Arbre couvrant, Complexité paramétrée, Largeur d’arbre, Nombre cyclomatique

@booklet{EasyChair:2648,
  author    = {Dimitri Watel and Massinissa Merabet},
  title     = {Parameterized Complexity of Spanning Tree Problems with Local Constraints.},
  howpublished = {EasyChair Preprint 2648},
  year      = {EasyChair, 2020}}