Proprietes combinatoires et algorithmiques des associaèdra des graphes et polytopes hypergraphes

école doctorale

équipe

GAMBLE

contexte

L'un des principaux problèmes combinatoires liés aux polytopes à n dimensions consiste à trouver le chemin le plus court entre deux sommets d'un graphe formé par les sommets et les arêtes du polytope, la longueur du chemin étant définie par le nombre de ses arêtes. L'estimation de la longueur de ces chemins fait l'objet de recherches intensives depuis les débuts de la théorie de la programmation linéaire et l'invention par Dantzig, vers 1947, de l'algorithme du simplexe, qui cherche des solutions à un programme linéaire en passant de manière itérative d'une solution viable à une autre, le long des arêtes du polytope. Une classe importante de polytopes convexes sont les polymatroïdes qui sont construits à partir de fonctions sous-modulaires [9]. Les polytopes hypergraphiques et les associaèdre des graphes sont de polymatroïdes. Du point de vue de l'optimisation, il s'agit de polytopes qui généralisent les polytopes de base des matroïdes, tout en conservant la propriété selon laquelle les sommets extrêmes par rapport à une fonction linéaire peuvent être facilement identifiés à l'aide d'un algorithme glouton [9, 5]. Les polymatroïdes constituent donc une classe de programmes linéaires qui peuvent être résolus en temps fortement polynomial. Récemment, Cardinal et Steiner ont montré que le problème du chemin le plus court sur les polytopes hypergraphiques est APX-difficile et ont fourni un algorithme d'approximation en temps polynomial pour ce problème, où le facteur d'approximation est le degré de code maximal de l'hypergraphe [2]. Une famille spécial des polytopes hypergraphiques sont les associèdra de graphes. Les associahedra de graphes constituent des représentations naturelles des relations d'adjacence entre des structures combinatoires telles que les permutations, les partitions, les triangulations ou les arbres, générées par des opérations réversibles et locales appelées « flips ». Ces polytopes convexes sont étudiés dans de nombreuses applications en informatique, par exemple en optimisation [7], dans les systèmes de visualisation hiérarchique [10], dans la génération de structures aléatoires [4], ainsi que pour l'étude de modèles probabilistes [8]. Un des problèmes plus intéressants est celui du calcul des géodésiques entre sommets de ce polytope. Il a été démontré [6] que le problème de décision correspondant est NP-complet en général, mais qu'il peut être résolu en temps polynomial lorsque le graphe d'entrée est un graphe 'split' complet [1]. Dans un article très récent [3], il est démontré que ce problème est FPT pour tous les associaèdre des graphes.

spécialité

Informatique

laboratoire

LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications