ANR-DFG - Appel à projets générique 2020 - DFG

Théories Unifiantes dans les Algorithmes Multivarieés – UTMA

Théories Unifiantes dans les Algorithmes Multivarieés

L'étude de la tractabilité des problèmes de calcul est un défi central de l'informatique théorique. Une question centrale est de savoir quand, pourquoi et comment les problèmes informatiques peuvent être résolus efficacement. Pour répondre à cette question, la théorie des algorithmes a offert de puissants résultats unificateurs, appelés méta-théorèmes algorithmiques (AMT), qui fournissent des conditions mathématiques générales impliquant la dérivation automatique d'algorithmes efficaces.

Distiller la valeur méta-algorithmique de tous les aspects de la théorie de la complexité paramétrée. Inventer de nouveaux paramètres structurels qui systématisent nouvelles techniques algorithmiques.

L'objectif ultime est d'établir les TAM comme un ingrédient d'unification essentiel de la théorie des algorithmes. Pour y parvenir, nous devons introduire de nouvelles logiques, basées sur des opérateurs invariants par isomorphisme, qui peuvent être évalués efficacement sur la base de la technique que nous cherchons à capturer. Un exemple de tels opérateurs logiques serait un opérateur pour affirmer l'existence d'un nombre fixe de chemins disjoints, ou un opérateur pour tester la planarité. Ces deux opérateurs peuvent être évalués efficacement avec la technique des sommets non pertinents. Le défi consistera à trouver un ensemble naturel d'opérateurs qui permette d'exprimer commodément les problèmes algorithmiques tout en évitant la redondance entre les opérateurs. Le choix d'un tel ensemble d'opérateurs est également fortement lié aux réductions logiques entre les problèmes algorithmiques. Les nouvelles logiques seront construites sur la base de la logique du premier ordre ou de la logique monadique du second ordre, selon le contexte, et étendront ces logiques de base par des opérateurs qui ne sont pas exprimables dans la logique de base. Les techniques décrites dans la section 1 montrent souvent leur potentiel sur des classes de graphes restreintes, comme les graphes de genre limité ou les graphes sans H-minor, où les FO peuvent également être évaluées efficacement. Cela donne lieu à la deuxième composante, structurelle, des nouveaux AMT que nous visons, c'est-à-dire étudier et inventer de nouveaux paramètres structurels qui systématisent ou incorporent de nouvelles techniques algorithmiques. Comprendre les limites d'applicabilité de ces techniques et fournir des paramètres structurels naturels qui capturent leur applicabilité. Chaque notion abstraite de connectivité basée sur des fonctions d'ensembles submodulaires symétriques donne lieu à une mesure de largeur combinatoire avec des applications algorithmiques spécifiques. Des exemples bien connus sont la connectivité des sommets, qui conduit à la notion de largeur de branche (qui est équivalente à la largeur d'arbre) ou le rang de coupe, qui conduit à la notion de largeur de rang (qui est équivalente à la largeur de clique). D'autres fonctions de connectivité comprennent la connectivité des arêtes, la connectivité des hypergraphes, la connectivité de l'appariement, la connectivité des matrices, etc. Chacune de ces fonctions de connectivité conduit à ses propres techniques algorithmiques. Chacune de ces fonctions de connectivité conduit à ses propres techniques algorithmiques. Cela permet dans de nombreux cas d'obtenir des algorithmes de programmation dynamique efficaces, et en particulier, cela conduit dans de nombreux cas à un model checking MSO efficace. Le troisième défi que nous envisageons de relever est de trouver les (nouvelles) logiques les plus générales qui peuvent être évaluées efficacement sur des classes de graphes structurellement restreintes bien connues.

Le premier paquet de travail répond partiellement au défi 1. Notre objectif est de construire une théorie méta-algorithmique systématisant l'applicabilité de la technique des sommets non pertinents et de définir une logique, plus générale que FO, dans laquelle les TAM peuvent être prouvées pour certaines classes de graphes épars. Compte tenu des restrictions de complexité connues sur les problèmes où la technique des sommets non pertinents s'applique. Nous poursuivrons d'abord cet objectif sur les graphes topologiquement contraints dont les caractéristiques structurelles sont plus simples à traiter. Nos résultats peuvent être indicatifs sur la façon de procéder pour des conditions de sparsité de graphes plus générales. Nous tenterons également de prouver des résultats de dureté qui entravent l'applicabilité de la technique des sommets non pertinents dans les graphes généraux.

Le deuxième paquet de travail répond partiellement au défi 1 et au défi 2. Nous voulons exploiter tout le potentiel de l'approche de programmation dynamique en explorant de nouveaux paramètres structurels et, sur les classes de graphes structurels qui en résultent, nous voulons systématiser et intégrer de nouvelles techniques algorithmiques. Des approches alternatives de programmation dynamique, combinées à des techniques puissantes telles que la séparation aléatoire, la compréhension récursive et l'utilisation de séparateurs importants, ont été utilisées pour la conception d'algorithmes FPT pour des problèmes qui ne rentrent dans aucun cadre méta-algorithmique connu. Comme il existe des techniques et des idées communes à tous ces résultats, la création d'un cadre méta-algorithmique qui peut subsumer la plupart d'entre eux dans un seul AMT est actuellement un défi important.

Le troisième paquet de travail répond partiellement au défi 1. Nous avons pour objectif de prouver des AMT pour les problèmes de comptage et de dénombrement. Pour cet objectif, la première étape est d'exploiter dans quelle mesure l'arsenal méta-algorithmique pour les problèmes de comptage peut aller plus loin que les cadres standards.

Le quatrième paquet de travail répond partiellement au défi 1. Notre objectif est d'étendre l'horizon combinatoire de la théorie de la bidimensionnalité et de systématiser son applicabilité. Notre principale approche pour atteindre cet objectif est de prouver que la condition SQGM est valable pour les graphes qui admettent certains encastrements dans des dimensions supérieures.

Le dernier paquet de travail répond partiellement aux défis 1 et 3. Notre objectif est d'introduire d'autres logiques qui capturent des techniques algorithmiques et de trouver les classes de graphes les plus générales sur lesquelles nous pouvons tester efficacement les propriétés définissables dans ces logiques, ainsi que de trouver les logiques les plus générales qui peuvent être testées efficacement sur des classes de graphes bien étudiées.

Tâches 1.1 et 1.2 :

Le résultat principal est le méta-théorème algorithmique de [16]. Il prouve que les problèmes de modification où la propriété cible est exprimée par une phrase du premier ordre plus la planarité, admettent un algorithme FPT quadratique. [16] est le premier résultat fournissant des conditions méta-algorithmiques pour l'applicabilité de la technique des sommets non pertinents. Ce résultat a été largement généralisé dans [22] où une nouvelle logique est introduite pour les problèmes de modification de graphes, la logique T, et un méta-théorème est prouvé affirmant que sur les classes de graphes mineurs fermés, la vérification de modèle pour T peut être faite par un algorithme FPT quadratique.

Tâche 2.1 et tâche 2.2 :
Dans [17], nous proposons une technique de programmation dynamique pour les graphes à faible décomposition arborescente.
décomposabilité. Nous proposons un méta-algorithme pour le problème suivant : calculer la taille minimale d'un ensemble de sommets d'un graphique
dont l'élimination produit un graphe excluant H comme mineur. Le résultat principal de [17] est qu'il donne une condition méta-paramétrique sur H distinguant nettement les cas où cette programmation dynamique peut être faite en temps O(c^(tw log tw) · n) ou en temps O(c^(tw) · n).

- Tâche 2.3 et 3.1 :
Le résultat principal dans cette direction est [11] où nous fournissons une dichotomie nette sur les cas où le problème du comptage des appariements parfaits est polynomialement soluble ou #P-complet. Le résultat dans [11] fournit une hiérarchie paramétrique structurelle appelée vga-hiérarchie, qui produit des paramètres qui sont plus généraux que la largeur des arbres.

- Tâche 3.2 :
Un résultat dans cette direction est l'utilisation de techniques de noyautage pour la dérivation d'algorithmes d'approximation à facteur constant dans [14].

- Tâches 4.1 et 4.2 :
Les principaux résultats des tâches 4.1 et 4.2 sont ceux de [3] où nous donnons une large famille de classes de graphes définis par la géométrie et basés sur les graphes d'intersection d'objets convexes. Dans [3], nous prouvons que ces classes satisfont la condition, plus générale, de SQCM.

- Tâche 5.1 :
Le résultat principal de cette tâche est [5] (voir aussi [20] où nous prouvons le méta-théorème algorithmique suivant. Si f est une phrase FOL dont le modèle de préfixe est ???, alors le problème de concevoir si un graphe G a une distance d'élimination au plus k à un modèle de f admet un algorithme FPT, s'exécutant en temps f(k) - nO(|f|). Dans [5], on prouve que ce résultat est optimal dans le sens où on ne peut pas s'attendre à un tel algorithme pour des préfixes de quantification plus compliqués.

- Tâche 5.2 :
Le premier pas vers la réalisation de la tâche 5.2 a été fait dans [25], [26] et [2] où nous développons des éléments de la théorie structurelle des graphes afin de construire une théorie algorithmique de la programmation dynamique.

Le développement de la théorie de la complexité algorithmique est un enjeu majeur de l’informatique. La question centrale
est quand, pourquoi et comment un problème algorithmique peut être résolu efficacement. Pour répondre à cette question,
les théorèmes méta-algorithmiques (MTA) sont des outils unificateurs puissants. Ils décrivent des conditions générales qui
permettent de décrire automatiquement des algorithmes efficaces. Ces conditions dépendent généralement d’une part
de la complexité descriptive des problèmes et d’autre part propriétés structurelles des données à traiter. Elles relèvent donc
de la logique et de la combinatoire. Les MTAs, bien que peu fréquents, sont précieux car ils fournissent une compréhension
approfondie de la complexité intrinsèque des problèmes algorithmiques.

Cette proposition vise à développer le potentiel d’unification des MTAs dans des algorithmes combinatoires.
Nous allons utiliser le cadre de la théorie de la complexité paramétrée, ou l’efficacité d’un algorithme est mesurée
non seulement par rapport à la taille de l’entrée mais aussi par rapport à des paramètres secondaires qui jouent un
rôle clé dans l’explosion combinatoire du temps de calcul. Cette analyse multivariée permet de prendre en compte de manière
flexible les conditions logiques et structurelles qui sont généralement rencontrées dans les paramétrisations de
problèmes algorithmiques. La théorie de la complexité paramétrée offre aujourd’hui un arsenal étendu de techniques et de
paradigmes algorithmiques pour la résolution de problèmes spécifiques. Leur généralisation systématique aux MTAs est un défi
important et non trivial qui nécessite un em changement qualitatif dans la théorie des algorithmes de l’étude de problèmes spécifiques
à la recherche de conditions (logique et combinatoires) unificatrices permettant la descriptions d’algorithmes génériques.

Nous prévoyons d’étudier et d’exploiter le meilleur potentiel méta-algorithmique des techniques les plus avancées issues de
la théorie de la complexité paramétrée contemporaine. Nous visons l’obtention de MTAs pour de larges familles de problèmes
dans divers contextes dans des algorithmes combinatoires. Notre ambition finale est de développer les MTAs comme outil
unificateur incontournable de la théorie de la complexité algorithmique.

Coordination du projet

Dimitrios Thilikos (Laboratoire d'Informatique, de Robotique et de Microélectronique de Montpellier)

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

UBremen University of Bremen
LIRMM Laboratoire d'Informatique, de Robotique et de Microélectronique de Montpellier

Aide de l'ANR 189 918 euros
Début et durée du projet scientifique : août 2021 - 36 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