L'Agence nationale de la recherche Des projets pour la science

Translate this page in english

Mathématiques, informatique théorique, automatique et traitement du signal (CE40) 2018
Projet ASSK

Algorithmes avec décomposition moins connu: graphes et matroids

Le principal objectif du projet est l'étude - structurelle et algorithmique - des petites coupes dans les graphes et matroides. La notion de coupe est omni-présente dans plusieurs domaines de l'informatique théorique, et revêt plusieurs formes. Informellement, une petite coupe dans une structure relationnelle, par exemple un graphe ou une formule logique, est une bipartition de son domaine et telle que les relations entre les deux parties de la bipartition puissent être décrites par une information de petite taille. On peut citer en théorie des graphes, des coupes basées sur des bipartitions des sommets comme les modules ou les splits, et d'autres basées sur des bipartitions des arêtes telles que celle résultant dans les problèmes de flots. Les différentes notions de petite coupe ont été un concept fondamental dans les différentes notions de décompositions de graphes et les applications algorithmiques associées.

Il existe principalement deux manières différentes d'utiliser les coupes en algorithmique. D'abord dans le paradigme diviser-pour-mieux régner qui consiste à décomposer le graphe en des graphes basiques, où le problème est supposé facile, ces derniers décrivant à travers de petites coupes l'ensemble des arêtes du graphe. L'autre façon d'utiliser les petites coupes est la possibilité de réduire l'espace de recherche d'une solution optimale. Il existe plusieurs problèmes fondamentaux qui peuvent être décrits en terme de `problèmes de séparation' et tels que l'espace de solution peut être, soit directement codé en un ensemble de séparations ou, être réduit drastiquement par l'utilisation de petites coupes.

Dans le cas des familles de graphes peu denses, les décompositions structurelles et leurs conséquences algorithmiques sont plus ou moins bien comprises maintenant, ce qui est loin d'être le cas des décompositions basées sur des coupes denses. Il apparait récemment que la notion de décomposition en rang, qui semble être la décomposition la plus intéressante structurellement parmi toutes les décompositions basées sur des coupes denses, est beaucoup plus facile à manipuler lorsqu'elle est décrite en termes de coupes dans les matroides représentables. Il existe plusieurs questions de base ouvertes depuis longtemps dans les problèmes de séparation. Et beaucoup de concepts et techniques élaborées ces dernières années ont joué un rôle important dans les problèmes de couverture/packing de chemins, même si souvent considéré peu important. En plus, les techniques développées pour les problèmes de couverture restent souvent valables (utilisables telles quelles) pour les problèmes de packing et vice-versa. Une ressemblance étroite - avec une explication mathématique cohérente - semble également exister entre ces deux problèmes, et les matroides représentables apparaissent à nouveau dans la compréhension de la dualité entre ces deux problèmes.

L'objectif du projet est d'apporter une brique dans la compréhension des phénomènes de petites coupes. Les questions principales sont : Quels problèmes admettent des algorithmes efficaces (et compressions) dans les familles de graphes de largeur de rang bornée ? Peut-on expliquer dans un cadre unifié les algorithmes (et compressions) basés sur les coupes de petite taille ? Nous pensons que l'interprétation des phénomènes de coupes dans les graphes par des notions similaires dans les matroides représentables fournirait un tel cadre unifié. Dans cette optique, nous divisons la stratégie en quatre tâches :
A. Mise en place d'algorithmes efficaces dans les familles de matroides représentables de largeur de branche bornée.
B. Etude de la structure des matroides représentables de largeur de branche bornée.
C. Etude des propriétés combinatoires des problèmes de couplage dans les matroides représentables, espérant généraliser les techniques existentes élaborées pour les problèmes de séparation dans les graphes.
D. Etude des applications algorithmiques des généralisations proposées.

Partenaires

LAMSADE LAMSADE

Aide de l'ANR 211 634 euros
Début et durée du projet scientifique janvier 2019 - 48 mois

 

Programme ANR : Mathématiques, informatique théorique, automatique et traitement du signal (CE40) 2018

Référence projet : ANR-18-CE40-0025

Coordinateur du projet :
Madame Eunjung Kim (LAMSADE)

 

Revenir à la page précédente

 

L'auteur de ce résumé est le coordinateur du projet, qui est responsable du contenu de ce résumé. L'ANR décline par conséquent toute responsabilité quant à son contenu.