Quelle est la notion la plus importante de rareté pour la conception d'algorithmes de graphes efficaces?

Il existe plusieurs notions concurrentes de «graphe clairsemé». Par exemple, un graphique intégrable en surface peut être considéré comme clairsemé. Ou un graphique avec une densité de bord borné. Ou un graphique avec une circonférence élevée. Un graphique avec une grande expansion. Un graphique avec une largeur d'arbre bornée. (Même dans le sous-champ des graphiques aléatoires, il est légèrement ambigu quant à ce que l'on pourrait appeler clairsemé.) Et cetera.

Quelle notion de «graphe clairsemé» a eu le plus d'impact sur la conception d'algorithmes de graphes efficaces, et pourquoi? De même, quelle notion de "graphe dense" ...? (NB: Karpinski a beaucoup travaillé sur les résultats d'approximation pour un modèle standard de graphiques denses.)

Je viens de voir un exposé de J. Nesetril sur un de ses programmes (avec P. Ossona de Mendez) pour capturer des mesures de rareté dans des graphiques dans un cadre unifié (asymptotique). Ma question - oui, peut-être assez subjective et j'attends des camps différents - est motivée par le désir de saisir une perspective à multiples facettes sur l'utilisation de la rareté dans les algorithmes (et de combler toute lacune dans ma propre compréhension du problème).

Je pense que selon toute norme raisonnable, un graphique en grille tridimensionnelle n × n × n devrait être considéré comme clairsemé, et cela exclut la plupart des définitions candidates impliquant des plongements de surface ou des mineurs. (Cependant, une largeur d'arbre sublinéaire serait toujours possible.)

Ma mesure d'économie préférée actuelle est la dégénérescence . La dégénérescence d'un graphe est le minimum, sur tous les ordres linéaires des sommets du graphe, du degré maximal maximal dans l'orientation acyclique dirigée du graphe formé en orientant chaque arête des sommets antérieurs aux sommets ultérieurs de l'ordre. De manière équivalente, c'est le maximum, sur tous les sous-graphiques, du degré minimum dans le sous-graphique. Ainsi, par exemple, les graphes planaires ont une dégénérescence de cinq car tout sous-graphe d'un graphe planaire a un sommet de degré au plus cinq. La dégénérescence est facile à calculer en temps linéaire, et l'ordre linéaire qui provient de la définition est utile dans les algorithmes .

La dégénérescence fait partie d'un facteur constant de certaines autres mesures standard, y compris l'arboricité, l'épaisseur et le degré moyen maximal de tout sous-graphique, mais je pense que celles-ci sont plus difficiles à utiliser.

Il semble y avoir beaucoup de «bonnes» notions de rareté, mais il y a quelque chose d'une hiérarchie pour ces notions structurelles de rareté qui ont une saveur théoriquement modèle. Je pense que ceux-ci ont eu un fort impact sur les algorithmes de graphes efficaces.

$k$$K_{k+2}$

Les notes de cours d'Anuj Dawar de novembre 2010 traitent également de la largeur des arbres délimités localement, ce qui est incomparable avec les mineurs exclus. Le degré délimité définit clairement les graphiques clairsemés, et ces graphiques ont une largeur d'arbre locale limitée, mais ne sont pas définissables par un ensemble de mineurs exclus.

L'impact du degré borné est clair: c'est souvent l'une des premières restrictions à rendre un problème difficile traitable, par exemple l'algorithme de Luks pour l'isomorphisme graphique sur les graphes à degré borné. L'impact de l'exclusion d'un mineur est également clair, au moins sous le couvert d'une largeur d'arbre limitée (comme l'a souligné Suresh).

La notion d'exclusion locale d'un mineur généralise à la fois la largeur d'arbre limitée localement et les mineurs exclus, formant ainsi la classe "la plus générale" de la hiérarchie. Cependant, il n'est pas encore clair comment utiliser cette propriété dans les algorithmes pratiques. Même le cas «traitable» de l'exclusion d'un mineur n'a pas nécessairement de bons algorithmes pratiques; les grandes constantes abondent dans les algorithmes théoriques du modèle. J'espère que certaines de ces classes se révéleront avoir des algorithmes pratiquement efficaces à long terme.

Voir aussi ma réponse ce qui est facile pour les graphiques mineurs pour d'autres commentaires connexes.

Je ne peux penser à aucune propriété de graphique qui ait eu autant d'impact sur la conception d'algorithmes efficaces que la largeur d'arbre bornée et la bidimensionnalité en général.

On peut considérer un graphe comme une matrice d'adjacence - il existe plusieurs définitions de la rareté de la matrice (% d'entrées nulles, par exemple) qui pourraient se traduire par le graphe lui-même. Autre que% d'entrées nulles, la bande passante de la matrice sous un réordonnancement pourrait être un bon proxy pour la rareté du graphique (il semble que la bande passante soit liée à la dégénérescence).