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)$

ds.algorithms open-problem graph-algorithms

— Vinayak Pathak
źródło

Btw, oczywiście poprawa algorytmu maksymalnego przepływu również doprowadzi do poprawy tutaj. Ale myślę, że jest najlepszym znanym obecnie algorytmem maksymalnego przepływu?

O (n^{8 / 3})

$O(n^{8/3})$

— Vinayak Pathak,

Może coś źle rozumiem, ale czy algorytm losowego skrótu Karger-Stein nie ma czasu działania ?

\tilde{O} (n^{2})

$\tilde{O}(n^2)$

— Sasho Nikolov

Czy to oczekiwany czas działania? Algorytm, który opisałem, jest całkowicie deterministyczny.

O (n^{2})

$O(n^2)$

— Vinayak Pathak,

Algorytmem jest Monte Carlo: zawsze kończy się w czasie i generuje minimalne cięcie z dużym prawdopodobieństwem. Oczywiście prawdopodobieństwo awarii zależy odwrotnie od czasu pracy. Przepraszam, biorąc pod uwagę, że cytowano Alon-Spencer. Po prostu założyłem, że algorytm jest losowy :)

\tilde{O} (n^{2})

$\tilde{O}(n^2)$

— Sasho Nikolov

Jeśli szukasz algorytmu deterministycznego, myślę, że powinieneś to określić w pytaniu. Nie znam algorytmu deterministycznego lepszego niż dla minimalnego cięcia (zobacz Stoer-Wagner dla łatwego algorytmu, który osiąga ten czas działania). Interesujące jest to, o ile lepiej możemy zrobić deterministycznie dla określonego problemu (8/3 w wykładniku wydaje się nienaturalne dla najlepszego ograniczenia, ale kto wie).

O (m n + n^{2} \log n)

$O(mn + n^2\log n)$

— Sasho Nikolov

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.

— Falk Hüffner
źródło