Dado un gráfico, decida si su conectividad de borde es al menos n / 2 o no

El Capítulo 1 del libro El Método Probabilístico, de Alon y Spencer, menciona el siguiente problema:

Dado un gráfico $G$ , decida si su conectividad de borde es al menos $n/2$ o no.

El autor menciona la existencia de un $O(n^3)$ algoritmo por Matula y mejora a $O(n^{8/3}\log n)$ .

Mi pregunta es, ¿cuál es el tiempo de ejecución más conocido para este problema?

Permítanme describir el algoritmo mejorado.

Primero, decida si $G$ tiene su grado mínimo al menos $n/2$ o no. Si no, entonces la conectividad de borde es claramente menor que $n/2$ .

A continuación, si ese no es el caso, calcule un conjunto dominante $U$ de $G$ de tamaño $O(\log n)$ . Esto se puede hacer en el tiempo $O(n^2)$ , mediante un algoritmo descrito en la sección anterior del libro.

A continuación, utiliza el siguiente hecho no muy difícil de probar:

Si el grado mínimo es $\delta$ , entonces para cualquier corte de tamaño de borde como máximo $\delta$ que divida $V$ en $V_1$ y $V_2$ , cualquier conjunto dominante de $G$ debe tener sus vértices en $V_1$ y $V_2$ .

Ahora considere el conjunto dominante . Desde G tiene grado mínimo n / 2 , cualquier corte de borde de tamaño inferior a n / 2 también debe separar U . Por lo tanto, para cada i ∈ { 2 , k } , encontramos el tamaño del corte de borde más pequeño que separa u 1 y u i . Cada una de estas cosas se pueden hacer en el tiempo O ( n 8 /$U = \{u_1, \ldots , u_k\}$$G$$n/2$$n/2$$U$$i\in \{2, k\}$$u_1$$u_i$ utilizando un algoritmo de flujo máximo. Así, el tiempo total necesario es O ( n 8 / 3 log n ) .$O(n^{8/3})$$O(n^{8/3}\log n)$

Puede verificar esto fácilmente en tiempo lineal, ya que un gráfico tiene conectividad de borde al menos si y solo si su grado mínimo es al menos n / 2 . Usted ya abogó por la parte "solo si". Considere ahora un gráfico donde cada vértice tiene un grado de al menos n / 2 y un corte que divide el gráfico en dos conjuntos de vértices X y ˉ X con x : = | X | ≤ n / 2 . Un vértice en X puede tener como máximo x - 1 conexiones a otros vértices en$n/2$$n/2$$n/2$$X$$\bar X$$x := |X| \leq n/2$$X$$x - 1$ , y por lo tanto debe contribuir al menos n / 2 - ( x - 1 ) bordes al corte. Por lo tanto, el corte debe tener un tamaño de al menos x ( n / 2 - x + 1 ) . Queda por demostrar que x ( n / 2 - x + 1 ) ≥ n / 2 , lo cual es cierto ya que ( x - 1 ) ( n / 2 - x ) $X$$n/2 - (x - 1)$$x (n/2 - x + 1)$$x (n/2 - x + 1) \geq n/2$ .$(x - 1)(n/2 - x) \geq 0$

Curiosamente, la única referencia que encuentro a este resultado es esta de una conferencia de la bioinformática. Sería realmente curioso ver si se ha probado en otro lugar.

Editar: Una referencia anterior es: Gary Chartrand: un enfoque teórico gráfico para un problema de comunicación , SIAM J. Appl. Matemáticas. 14-4 (1966), págs. 778-781.