CE40 - Mathématiques, informatique théorique, automatique et traitement du signal

Algorithmes avec décomposition moins connu: graphes et matroids – ASSK

Les petites coupes à l’honneur : algorithmique pour graphes et matroides représentables

Le thème principal de ce projet est les petits phénomènes de séparation sur les graphes et les matroides linéaires, mettant l'accent sur les applications sur la conception d'algorithmes. Le concept de séparation en informatique théorique est omniprésent, sous des formes variées selon le contexte. C'est un concept fondamental qui ouvre la voie à la théorie des graphes, en particulier à la théorie de la décomposition structurelle. Il sert également de moteur majeur pour les algorithmes.

Nous fournissons une nouvelle boîte à outils combinatoire et algorithmique pour les graphiques de petite largeur de rang et pour les matroides linéaires.

Il existe deux façons dont les petites séparations sont reconnues et déployées dans les algorithmes. Premièrement, ils pourraient être utilisés pour décomposer un graphique en blocs de construction simples qui sont collés le long de petites séparations. La théorie des graphes structuraux est un programme de recherche réussi qui démontre la puissance de telles décompositions. De nombreuses classes de graphes admettent de telles décompositions, ce qui a conduit à de nombreux algorithmes efficaces fonctionnant sur des décompositions. En particulier, les décompositions arborescentes basées sur diverses notions de séparations sont une pierre angulaire de la conception d'algorithmes. La deuxième arène où de petites séparations sont utilisées est la représentation graphique de l'espace de solution à travers la lentille des petites séparations. Trouver un minimum (s, t) -cut est un problème classique pour les versions d'arête et de sommet, et le problème Minimum Cut et ses nombreuses variantes ont été largement étudiés jusqu'à présent. Il existe de nombreux problèmes fondamentaux qui peuvent être qualifiés de problèmes de séparation, pour lesquels l'espace de solution peut être soit directement codé comme une séquence de séparations, soit radicalement réduit à l'aide de petites séparations.<br />Nous avons pour objectif de faire progresser les connaissances actuelles sur les petits phénomènes de séparation.<br /><br />Les résultats attendus d'une exécution réussie du projet sont de deux ordres. Premièrement, nous fournissons une nouvelle boîte à outils combinatoire et algorithmique pour les graphiques de petite largeur de rang et pour les matroïdes linéaires de petite largeur de branche qui est parallèle à ceux développés pour les graphiques de petite largeur d'arbre. Deuxièmement, nous présentons un cadre complet pour divulguer la structure sous-jacente des problèmes de séparation de graphes et atteindre de nouveaux algorithmes.

Notre travail s'articule autour d'une multitude de concepts et de techniques en théorie des graphes / matroïdes, en conception d'algorithmes et en logique.

- Nous avons introduit un nouveau graphe invariant à double largeur. Dans une série d'articles, nous découvrons que la double largeur est un invariant puissant et très naturel qui capture un large éventail de classes de graphes classiques, en particulier les graphes décomposables de manière récursive le long de petites séparations telles que la petite largeur de rang et la largeur d'arbre, et les propriétés qui tiennent dans ces classes.

- Nous avons présenté une nouvelle technique de conception d'algorithmes à paramètres fixes pour les problèmes de coupe de graphe dans des graphes non dirigés. Notre technique est applicable aux problèmes qui peuvent être formulés comme une recherche d'une (arête) (s, t) -cut de cardinalité au plus k dans un graphe non orienté G avec les bornes désignées s et t.

- Nous avons donné des algorithmes de streaming multi-passes améliorés pour le problème de la maximisation d'une fonction sous-modulaire non négative monotone ou arbitraire soumise à une contrainte p-matchoid générale dans le modèle dans lequel les éléments de l'ensemble de terrain arrivent un à la fois dans un flux. La famille de contraintes que nous considérons généralise à la fois l'intersection de p contraintes matroïdes arbitraires et l'appariement hypergraphique p-uniforme.

- Robertson et Seymour (1983) ont prouvé que pour chaque arbre T, la classe des graphes qui ne contiennent pas T comme mineur a une largeur de chemin bornée. Pour la relation pivot-mineur, rank-width et linear rank-width prennent le rôle de tree-width et de path-width. En tant que tel, il est naturel d'examiner si pour chaque arbre T, la classe de graphes qui ne contiennent pas T en tant que pivot-mineur a une largeur de rang linéaire bornée. Nous prouvons que cette affirmation est fausse chaque fois que T est un arbre qui n'est pas une chenille. Nous sommes également en mesure de donner une confirmation partielle de cette conjecture.

Les questions centrales qui ont déclenché ce projet sont les suivantes.

A. Pour quels problèmes les décompositions basées sur le concept de séparation dense aident-elles à obtenir des algorithmes efficaces?
B. Existe-t-il un cadre unifié qui englobe les techniques et concepts existants pour les problèmes de séparation, et pouvons-nous l'utiliser pour aborder les questions ouvertes?

L'hypothèse de recherche fondamentale qui sous-tend le projet est que l'interprétation des petits phénomènes de séparation sur les graphiques du point de vue des matroides linéaires sera cruciale pour répondre à des questions ouvertes intéressantes.

Pierre Aboulker, Isolde Adler, Eun Jung Kim, Ni Luh Dewi Sintiari and Nicolas Trotignon,
«On the tree-width of even-hole-free graphs«, arXiv (2020).

Ararat Harutyunyan, Michael Lampis, Nikolaos Melissinos,
«Digraph Coloring and Distance to Acyclicity«, arXiv (2020).

Konrad K. Dabrowski, François Dross, Jisu Jeong, Mamadou Moustapha Kanté, O-joung Kwon, Sang-il Oum and Daniël Paulusma,
«Tree pivot-minors and linear rank-width«, arXiv (2020).

Édouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Thomasé, Rémi Watrigan, «Twin-width III: Max Independent Set and Coloring«, arXiv (2020).

Édouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Thomassé and Rémi Watrigan, Twin-width II: small classes, In the Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2021), arXiv.

Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, Magnus Wahlström
Solving hard cut problems via flow-augmentation, SODA 2021.

Édouard Bonnet, Eun Jung Kim, Stéphan Thomassé, Rémi Watrigan
Twin-width I: tractable FO model checking, FOCS 2020.

Mamadou Moustapha Kanté, Christophe Paul, Dimitrios M. Thilikos,
A Linear Fixed Parameter Tractable Algorithm for Connected Pathwidth, ESA 2020.

Chien-Chung Huang, Theophile Thiery and Justin Ward,
Improved Multi-Pass Streaming Algorithms for Submodular Maximization with Matroid Constraints, APPROX/RANDOM 2020.

Remy Belmonte, Eun Jung Kim, Michael Lampis, Valia Mitsou and Yota Otachi,
Grundy Distinguishes Treewidth from Pathwidth, ESA 2020.

Jungho Ahn, Eun Jung Kim and Euiwoong Lee,
Towards constant-factor approximation for chordal / distance-hereditary vertex deletion, ISAAC 2020.

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.

Coordination du projet

Eunjung Kim (LAMSADE)

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.

Partenaire

LAMSADE LAMSADE

Aide de l'ANR 211 633 euros
Début et durée du projet scientifique : décembre 2018 - 48 Mois

Liens utiles

Explorez notre base de projets financés

 

 

L’ANR met à disposition ses jeux de données sur les projets, cliquez ici pour en savoir plus.

Inscrivez-vous à notre newsletter
pour recevoir nos actualités
S'inscrire à notre newsletter