Étant donné un graphique, décidez si sa connectivité de bord est au moins n / 2 ou non

Le chapitre 1 du livre The Probabilistic Method, par Alon et Spencer mentionne le problème suivant:

Étant donné un graphique , décidez si sa connectivité de bord est au moins ou non.$G$$n/2$

L'auteur mentionne l'existence d'un algorithme par Matula et l'améliore à .$O(n^3)$$O(n^{8/3}\log n)$

Ma question est, quel est le temps d'exécution le plus connu pour ce problème?

Permettez-moi de décrire l'algorithme amélioré.

Tout d'abord, décidez si a son degré minimum d'au moins ou non. Sinon, la connectivité de périphérie est clairement inférieure à .$G$$n/2$$n/2$

Ensuite, si ce n'est pas le cas, alors calculez un ensemble dominant de de taille . Cela peut être fait dans le temps , par un algorithme décrit dans la section précédente du livre.$U$$G$$O(\log n)$$O(n^2)$

Ensuite, il utilise les éléments suivants pas très difficiles à prouver:

Si le degré minimum est , alors pour toute coupe d'arête de taille au plus qui divise en et , tout ensemble dominant de doit avoir ses sommets à la fois et .$\delta$$\delta$$V$$V_1$$V_2$$G$$V_1$$V_2$

Considérons maintenant l'ensemble dominant . Puisque a un degré minimum , toute coupe de bord de taille inférieure à doit également séparer . Ainsi pour chaque , nous trouvons la taille de la plus petite coupe de bord qui sépare et . Chacune de ces choses peut être effectuée dans le temps utilisant un algorithme de flux maximal. Le temps total pris est donc .$U = \{u_1, \ldots , u_k\}$$G$$n/2$$n/2$$U$$i\in \{2, k\}$$u_1$$u_i$$O(n^{8/3})$$O(n^{8/3}\log n)$

Vous pouvez facilement vérifier cela en temps linéaire, car un graphique a une connectivité de bord d'au moins si et seulement si son degré minimum est d'au moins . Vous avez déjà plaidé pour la partie «seulement si». Considérons maintenant un graphique où chaque sommet a un degré d'au moins et une coupe qui divise le graphique en deux ensembles de sommets et avec . Un sommet en peut avoir au plus connexions à d'autres sommets en , et doit donc contribuer au moins arêtes à la coupe. Ainsi, la coupe doit avoir une taille d'au moins . Reste à montrer que$n/2$$n/2$$n/2$$X$$\bar X$$x := |X| \leq n/2$$X$$x - 1$$X$$n/2 - (x - 1)$$x (n/2 - x + 1)$$x (n/2 - x + 1) \geq n/2$ , ce qui est vrai puisque .$(x - 1)(n/2 - x) \geq 0$

Curieusement, la seule référence que je trouve à ce résultat est celle d'une conférence de bioinformatique. Je serais vraiment curieux de voir si cela a été prouvé ailleurs.

Edit: Une référence antérieure est: Gary Chartrand: A Graph-Theoretic Approach to a Communications Problem , SIAM J. Appl. Math. 14-4 (1966), pp. 778-781.