Dado um gráfico, decida se a conectividade da borda é pelo menos n / 2 ou não

O capítulo 1 do livro The Probabilistic Method, de Alon e Spencer menciona o seguinte problema:

Dado um gráfico , decida se a conectividade da borda é pelo menos n / 2 ou não.$G$$n/2$

O autor menciona a existência de um algoritmo por Matula e melhora-lo para O ( n 8 / 3 log n ) .$O(n^3)$$O(n^{8/3}\log n)$

Minha pergunta é: qual é o tempo de execução mais conhecido para esse problema?

Deixe-me descrever o algoritmo aprimorado.

Primeiro, decida se tem seu grau mínimo de pelo menos n / 2 ou não. Caso contrário, a conectividade de borda é claramente menor que n / 2 .$G$$n/2$$n/2$

Em seguida, se esse não for o caso, calcule um conjunto dominante de G de tamanho O ( log n ) . Isso pode ser feito no tempo O ( n 2 ) , por um algoritmo descrito na seção anterior do livro.$U$$G$$O(\log n)$$O(n^2)$

Em seguida, usa o seguinte não muito difícil para provar o fato:

Se o grau mínimo for , para qualquer corte de aresta no máximo δ que divida V em V 1 e V 2 , qualquer conjunto dominante de G deve ter seus vértices em V 1 e V 2 .$\delta$$\delta$$V$$V_1$$V_2$$G$$V_1$$V_2$

Agora considere o conjunto dominante . Uma vez que L tem um grau mínimo de n / 2 , qualquer corte da borda de tamanho inferior a n / 2 também devem separar L . Assim, para cada i ∈ { 2 , k } , encontramos o tamanho do menor corte de aresta que separa u 1 e u i . Cada uma dessas coisas pode ser feito em tempo O ( n 8 /$U = \{u_1, \ldots , u_k\}$$G$$n/2$$n/2$$U$$i\in \{2, k\}$$u_1$$u_i$ usando um algoritmo de fluxo máximo. Assim, o tempo total gasto é O ( n 8 / 3 log n ) .$O(n^{8/3})$$O(n^{8/3}\log n)$

Você pode verificar isso facilmente em tempo linear, pois um gráfico tem conectividade de borda pelo menos se e somente se o seu grau mínimo for pelo menos n / 2 . Você já defendeu a parte "somente se". Considere agora um gráfico em que todo vértice possui grau pelo menos n / 2 e um corte que divide o gráfico em dois conjuntos de vértices X e ˉ X com x : = | X | ≤ n / 2 . Um vértice em X pode ter no máximo x - 1 conexões com outros vértices em$n/2$$n/2$$n/2$$X$$\bar X$$x := |X| \leq n/2$$X$$x - 1$ e, portanto, deve contribuir com pelo menos n / 2 - ( x - 1 ) arestas no corte. Assim, o corte deve ter tamanho pelo menos x ( n / 2 - x + 1 ) . Resta mostrar que x ( n / 2 - x + 1 ) ≥ n / 2 , o que é verdadeiro desde ( 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, a única referência que eu encontrar para esse resultado é este a partir de uma conferência de bioinformática. Eu ficaria muito curioso para ver se isso foi provado em outro lugar.

Edit: Uma referência anterior é: Gary Chartrand: Uma abordagem teórico-gráfica de um problema de comunicação , SIAM J. Appl. Matemática. 14-4 (1966), pp. 778-781.