Théorème du séparateur planaire

Une forme plus faible du théorème séparateur avec un séparateur de taille ${\displaystyle O({\sqrt {n}}\log ^{3/2}n)}$ au lieu de ${\displaystyle O({\sqrt {n}})}$ a été prouvée à l'origine par Ungar (1951)[1], et la forme avec la borne asymptotique plus fine sur la taille du séparateur a été prouvée pour la première fois par Lipton & Tarjan (1979)[2]. Depuis leurs travaux, le théorème du séparateur a été redémontré de plusieurs manières différentes, la constante dans le terme en ${\displaystyle O({\sqrt {n}})}$ du théorème a été amélioré, et le théorème a été étendu à certaines classes de graphes non planaires.

L'application itérée du théorème du séparateur produit une hiérarchie de séparateurs qui peut prendre la forme soit d'une décomposition arborescente, soit d'une décomposition en branches du graphe. Les hiérarchies de séparateurs peuvent être utilisées pour concevoir des algorithmes de diviser pour régner efficaces pour les graphes planaires, et la programmation dynamique sur ces hiérarchies peut être utilisée pour des algorithmes en temps exponentiel et traitable en complexité paramétrée pour résoudre des problèmes d'optimisation NP-difficiles sur ces graphes. Les hiérarchies de séparateurs peuvent également être utilisées dans la dissection imbriquée, une variante efficace de l'élimination de Gauss-Jordan pour résoudre des systèmes systèmes d' équations linéaires creux résultant de méthodes d' éléments finis.

Au-delà des graphes planaires, les théorèmes de séparation ont été appliqués à d'autres classes de graphes, y compris les graphes excluant un mineur, les graphes du plus proche voisin et les maillages d'éléments finis. L'existence d'un théorème séparateur pour une classe de graphes peut être formalisée et quantifiée par les concepts de largeur arborescente d'arbre d'expansion polynomial.

Le théorème du séparateur planaire est le suivant :

Dans cet énoncé il n'est pas requis que ${\displaystyle A}$ ou ${\displaystyle B}$ forment des sous-graphes connexes de ${\displaystyle G}$. L'ensemble ${\displaystyle S}$ est appelé le séparateur de cette partition.

Une formulation équivalente est que les arêtes d'un graphe planaire à ${\displaystyle n}$ sommets ${\displaystyle G}$ peuvent être partagées en arêtes de deux sous-graphes à arêtes disjointes ${\displaystyle G_{1}}$ et ${\displaystyle G_{2}}$ de sorte que chacun des deux sous-graphes a au moins ${\displaystyle n/3}$ sommets et que l'intersection des ensembles de sommets des deux sous-graphes a ${\displaystyle O({\sqrt {n}})}$ sommets. Une telle partition est connue sous le nom de séparation[3]. Pour une séparation donnée, l'intersection des deux ensembles de sommets forme un séparateur, et les sommets qui appartiennent à l'un des sous-graphes mais pas à l'autre forment des sous-ensembles séparés ayant chacun au plus ${\displaystyle 2n/3}$ sommets. Réciproquement, pour une partition en trois ensembles ${\displaystyle A}$, ${\displaystyle S}$ et ${\displaystyle B}$ satisfaisant les conditions du théorème du séparateur planaire, on peut former une séparation dans laquelle les arêtes avec une extrémité dans ${\displaystyle A}$ appartiennent à ${\displaystyle G_{1}}$, les arêtes avec une extrémité dans ${\displaystyle B}$ appartiennent à ${\displaystyle G_{2}}$, et les arêtes restantes (avec les deux extrémités dans ${\displaystyle S}$) sont réparties arbitrairement.

La constante ${\displaystyle 2/3}$ dans l'énoncé du théorème du séparateur est arbitraire et peut être remplacée par tout autre nombre dans l'intervalle ouvert ${\displaystyle (1/2,1)}$ sans changer l'énoncé du théorème : une partition en sous-ensembles de taille plus équilibrée peut être obtenue, à partir d'une partition déséquilibrée, en divisant à plusieurs reprises le plus grand des ensembles de la partition et en regroupant les composants connexes résultantes[4].

Un séparateur planaire pour un graphe grille

Considérons un graphe grille avec ${\displaystyle r}$ lignes et ${\displaystyle c}$ colonnes ; le nombre ${\displaystyle n}$ de sommets est égal ${\displaystyle rc}$. Dans l'exemple, on a ${\displaystyle r=5}$, ${\displaystyle c=8}$, et ${\displaystyle n=rc=40}$. Si ${\displaystyle r}$ est impair, il y a une seule ligne centrale, et sinon il y a deux lignes près du centre ; de même, si ${\displaystyle c}$ est impair, il y a une seule colonne centrale, et sinon il y a deux colonnes près du centre. Si on prend pour ${\displaystyle S}$ l'une de ces lignes ou colonnes centrales, et on supprime ${\displaystyle S}$ du graphe, on partitionne le graphe en deux sous-graphes connexes plus petits ${\displaystyle A}$ et ${\displaystyle B}$, dont chacun a au plus ${\displaystyle n/2}$ sommets. Si ${\displaystyle r\leq c}$ (comme dans l'illustration), le choix d'une colonne centrale donne un séparateur ${\displaystyle S}$ avec ${\displaystyle r\leq {\sqrt {n}}}$ sommets, et de même si ${\displaystyle c\leq r}$ le choix d'une ligne centrale donne un séparateur avec au plus ${\displaystyle {\sqrt {n}}}$ sommets. Ainsi, chaque graphe grille a un séparateur ${\displaystyle S}$ de taille au plus ${\displaystyle {\sqrt {n}}}$, dont la suppression partitionne le graphe en deux composantes connexes qui chacune est de taille au plus ${\displaystyle n/2}$.

Le théorème du séparateur planaire stipule qu'une partition similaire peut être construite dans n'importe quel graphe planaire. Le cas des graphes planaires arbitraires diffère du cas des graphes grille en ce que le séparateur a une taille en ${\displaystyle O({\sqrt {n}})}$ qui peut être plus grande que ${\displaystyle {\sqrt {n}}}$, et que la borne sur la taille des deux sous-ensembles ${\displaystyle A}$ et ${\displaystyle B}$ (dans les versions les plus courantes du théorème) est ${\displaystyle 2n/3}$ plutôt que ${\displaystyle n/2}$, et que les deux sous-ensembles ${\displaystyle A}$ et ${\displaystyle B}$ ne forment pas nécessairement des sous-graphes connexes.

Un polyèdre formé en remplaçant chacune des faces d'un icosaèdre par un maillage de 100 triangles, un exemple de la construction minorante de Djidjev (1982)

Dans un graphe grille ${\displaystyle {\sqrt {n}}\times {\sqrt {n}}}$, un ensemble ${\displaystyle S}$ de ${\displaystyle s<{\sqrt {n}}}$ les points peut inclure un sous-ensemble d'au plus ${\displaystyle s(s-1)/2}$ points de grille, et le maximum est atteint en disposant ${\displaystyle S}$ en diagonale près d'un coin de la grille. Par conséquent, afin de former un séparateur qui sépare au moins ${\displaystyle n/3}$ des points de la grille restante, ${\displaystyle s}$ doit être au moins égal à ${\displaystyle {\sqrt {2n/3}}\approx 0.82{\sqrt {n}}}$.

Il existe pour tout ${\displaystyle n}$ des graphes planaires à ${\displaystyle n}$ sommets tels que tout séparateur ${\displaystyle S}$ qui partitionne le graphe restant en sous-graphes d'au plus ${\displaystyle 2n/3}$ sommets a une taille au moins égale à ${\displaystyle {\sqrt {4\pi n/{\sqrt {27}}}}\approx 1.56{\sqrt {n}}}$[4]. La construction consiste à approximer une sphère par un polyèdre convexe, à remplacer chacune des faces du polyèdre par un maillage triangulaire, et à appliquer un des théorèmes isopérimétriques à la surface de la sphère.

Certains graphes peu denses n'ont pas de séparateurs de taille sous-linéaire : ainsi, dans un graphe d'expansion, la suppression d'une fraction constante de sommets ne laisse toujours qu'une seule composante connexe.

Un des plus anciens théorèmes de séparation connus est peut-être le résultat de Jordan (1869) selon lequel tout arbre peut être divisé en sous-arbres d'au plus ${\displaystyle n/2}$ sommets chacun par la suppression d'un seul sommet[10]. En particulier, le sommet qui minimise la taille maximale des composants a cette propriété, car sinon son voisin dans l'unique grand sous-arbre formerait une partition encore meilleure. En appliquant la même technique à une décomposition arborescente d'un graphe arbitraire, il est possible de montrer que tout graphe possède un séparateur de taille au plus égale à sa largeur arborescente.

Un graphe ${\displaystyle G}$ qui n'est pas planaire, mais qui peut être plongé sur une surface de genre ${\displaystyle g}$, possède un séparateur avec ${\displaystyle O({\sqrt {gn}})}$ sommets, comme l'ont prouvé Gilbert, Hutchinson & Tarjan (1984)[16] en utilisant une approche similaire à celle de Lipton & Tarjan (1979). Ils regroupent les sommets du graphe en niveaux dans un parcours en largeur et trouvent deux niveaux dont la suppression laisse au plus un grand composant composé d'un petit nombre de niveaux. Ce composant restant peut être rendu planaire en supprimant un certain nombre de chemins du parcours en largeur proportionnels au genre, puis la méthode de Lipton & Tarjan peut être appliquée au graphe planaire restant. Le résultat résulte d'un équilibrage délicat entre la taille des deux niveaux supprimés et le nombre de niveaux qui sont entre eux. Si le plongement du graphe est donné, son séparateur peut être trouvé en temps linéaire. Les graphes de genre ${\displaystyle g}$ ont également des séparateurs d'arêtes de taille ${\displaystyle O({\sqrt {g\Delta n}})}$[17].

Les graphes de genre borné forment un exemple d'une famille de graphes fermés par l'opération de passage aux mineurs, et les théorèmes de séparation s'appliquent également aux familles de graphes fermés par mineurs arbitraires. En particulier, si une famille de graphes a un mineur exclu avec ${\displaystyle h}$ sommets, alors il a un séparateur avec ${\displaystyle O(h{\sqrt {n}})}$ sommets, et un tel séparateur peut être trouvé dans le temps ${\displaystyle O(n^{1+\varepsilon })}$ pour tout ${\displaystyle \varepsilon >0}$.

La méthode des séparateurs par cercles de Miller et al. (1997) se généralise aux graphes d'intersection de tout système de boules ${\displaystyle d}$-dimensionnelles avec la propriété que tout point de l'espace est couvert par au plus un certain nombre constant ${\displaystyle k}$ de boules, aux graphes des ${\displaystyle k}$-plus proches voisins dans ${\displaystyle d}$ dimensions[10] et aux graphes issus des maillages éléments finis[18]. Les séparateurs de sphères ainsi construits partitionnent le graphe d'entrée en sous-graphes d'au plus ${\displaystyle n(d+1)/(d+2)}$ sommets. La taille des séparateurs pour les graphes d'intersection de boules et des graphes des plus proches voisins sont ${\displaystyle O(k^{1/d}n^{1-1/d})}$ .

Les décompositions de séparateurs peuvent être utiles pour la conception d' algorithmes de diviser pour régner pour résoudre des problèmes sur des graphes planaires. A titre d'exemple, un problème qui peut être résolu de cette manière est de trouver le cycle le plus court dans un graphe planaire pondéré. Cela peut être fait comme suit :

• Partitionner le graphe donné ${\displaystyle G}$ en trois sous-ensembles ${\displaystyle S}$, ${\displaystyle A}$, ${\displaystyle B}$ d'après le théorème du séparateur planaire ;
• rechercher récursivement des cycles les plus courts dans ${\displaystyle A}$ et ${\displaystyle B}$ ;
• utiliser l'algorithme de Dijkstra pour trouver, pour chaque sommet ${\displaystyle s}$ dans ${\displaystyle S}$, le cycle le plus court qui passe par ${\displaystyle s}$ dans ${\displaystyle G}$ ;
• renvoyer le plus court des cycles trouvés dans les étapes ci-dessus.

Le temps des deux appels récursifs à ${\displaystyle A}$ et ${\displaystyle B}$ dans cet algorithme est dominé par le temps nécessaire pour effectuer les ${\displaystyle O({\sqrt {n}})}$ appels à l'algorithme de Dijkstra, de sorte que cet algorithme trouve le cycle le plus court dans ${\displaystyle O(n^{3/2}\log n)}$ temps.

Un algorithme plus rapide pour le même problème de cycle le plus court, exécuté en temps ${\displaystyle O(n\log ^{3}n)}$, a été donnée par Wulff-Nilsen (2009)[19].

Frederickson a proposé un autre algorithme plus rapide pour trouves les chemins les plus courts depuis une source unique en implémentant le théorème du séparateur dans les graphes planaires[20]. Il s'agit d'une amélioration de l'algorithme de Dijkstra avec une recherche itérative sur un sous-ensemble soigneusement sélectionné des sommets. Cette version prend un temps ${\displaystyle O(n{\sqrt {\log n}})}$ dans un graphe à ${\displaystyle n}$ sommets. Henzinger et al.[21] ont étendu la technique de division de Frederickson pour l'algorithme de calcul des chemins les plus courts depuis une source unique dans les graphes planaires à des arêtes de longueurs non négatives et donnent un algorithme en temps linéaire.

La dissection emboîtée est une variation basée sur un séparateur de la technique du diviser pour régner de l'élimination gaussienne dans la résolution des systèmes d'équations linéaires sur une structure de graphe planaire, tels que ceux résultant de la méthode des éléments finis. Il s'agit de trouver un séparateur pour le graphe décrivant le système d'équations, d'éliminer récursivement les variables dans les deux sous-problèmes séparés l'un de l'autre par le séparateur, puis d'éliminer les variables dans le séparateur[22]. Le remplissage du système pour cette méthode (c'est-à-dire le nombre de coefficients non nuls de la décomposition de Cholesky résultante de la matrice) est en ${\displaystyle O(n\log n)}$, permettant à cette méthode d'être compétitive avec les méthodes itératives pour les mêmes problèmes[22].

Le paradigme du diviser pour régner qui est basé sur les séparateurs a également été utilisé pour concevoir des structures de données pour les algorithmes sur les graphes dynamiques et la localisation de points[23], des algorithmes pour la triangulation de polygones[24] des problèmes de plus court chemin ou la construction de graphes voisins les plus proches[25] et des algorithmes d'approximation pour le calcul d'un stable maximal d'un graphe planaire[23].