Na podstawie wykresu zdecyduj, czy jego łączność brzegowa wynosi co najmniej n / 2, czy nie

Rozdział 1 książki Metoda probabilistyczna autorstwa Alona i Spencera wymienia następujący problem:

Biorąc pod uwagę wykres , zdecyduj, czy jego łączność brzegowa wynosi co najmniej czy nie.$G$$n/2$

Autor wspomina o istnieniu przez Matula algorytmu i ulepsza go do .$O(n^3)$$O(n^{8/3}\log n)$

Moje pytanie brzmi: jaki jest najbardziej znany czas wykonywania tego problemu?

Pozwól mi opisać ulepszony algorytm.

Najpierw zdecyduj, czy ma minimalny stopień co najmniej czy nie. Jeśli nie, łączność brzegowa jest wyraźnie mniejsza niż .$G$$n/2$$n/2$

Następnie, jeśli nie jest to przypadek, to obliczenia zbiór dominujący o o wielkości . Można tego dokonać w czasie , algorytmem opisanym w poprzedniej części książki.$U$$G$$O(\log n)$$O(n^2)$

Następnie wykorzystuje następujące niezbyt trudne do udowodnienia fakty:

Jeśli minimalny stopień wynosi , to dla każdego cięcia krawędzi o wielkości co najwyżej który dzieli na i , każdy dominujący zestaw musi mieć swoje wierzchołki zarówno w jak i .$\delta$$\delta$$V$$V_1$$V_2$$G$$V_1$$V_2$

Rozważmy teraz dominujący zestaw . Ponieważ ma minimalny stopień , każdy nacięciu krawędziowym wielkości mniejszej niż musi rozdzielić . Zatem dla każdego znajdujemy rozmiar najmniejszego cięcia krawędzi, które oddziela i . Każdą z tych czynności można wykonać w czasie przy użyciu algorytmu maksymalnego przepływu. Zatem całkowity czas to .$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)$

Możesz to łatwo sprawdzić w czasie liniowym, ponieważ wykres ma łączność krawędzi co najmniej wtedy i tylko wtedy, gdy jego minimalny stopień wynosi co najmniej . Argumentowałeś już za częścią „tylko jeśli”. Rozważmy teraz wykres, na którym każdy wierzchołek ma stopień co najmniej i cięcie, które dzieli wykres na dwa zestawy wierzchołków i pomocą . Wierzchołek w może mieć najwyżej połączeń z innymi wierzchołkami w , a zatem musi przyczyniać się do cięcia co najmniej krawędzi. Zatem wycięcie musi mieć rozmiar co najmniej . Pozostaje to pokazać$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$ , co jest prawdą, ponieważ .$(x - 1)(n/2 - x) \geq 0$

O dziwo, jedyne odniesienie znajdę to wynik jest ten z konferencji bioinformatyka. Byłbym naprawdę ciekawy, czy udowodniono to gdzie indziej.

Edycja: Wcześniejsze odniesienie to: Gary Chartrand: Teoretyczne podejście do problemu komunikacji , SIAM J. Appl. Matematyka 14-4 (1966), s. 778–781.