Учитывая граф, решите, является ли его пограничное соединение по крайней мере n / 2 или нет

В главе 1 книги «Вероятностный метод» Алона и Спенсера упоминается следующая проблема:

Учитывая граф , решите, является ли его граничная связность по крайней мере или нет.$G$$n/2$

Автор упоминает о существовании алгоритма от Matula и улучшает его до .$O(n^3)$$O(n^{8/3}\log n)$

У меня такой вопрос, каково самое известное время выполнения этой проблемы?

Позвольте мне описать улучшенный алгоритм.

Во-первых, определите, имеет ли минимальную степень не ниже n / 2 или нет. Если нет, то граничная связность явно меньше n / 2 .$G$$n/2$$n/2$

Затем, если это не так, вычислите доминирующий набор из G размера O ( log n ) . Это можно сделать за время O ( n 2 ) по алгоритму, описанному в предыдущем разделе книги.$U$$G$$O(\log n)$$O(n^2)$

Далее используются следующие не очень трудные для доказательства факты:

Если минимальная степень равна , то для любого сечения ребра размером не более δ, который делит V на V 1 и V 2 , любое доминирующее множество G должно иметь свои вершины как в V 1, так и в V 2 .$\delta$$\delta$$V$$V_1$$V_2$$G$$V_1$$V_2$

Теперь рассмотрим доминирующее множество . Так имеет минимальную степень , любой край срез размером менее должен также отделить . Таким образом, для каждого мы находим размер наименьшего среза ребра, который разделяет и . Каждая из этих вещей может быть выполнена за время с использованием алгоритма максимального потока. Таким образом, общее время занимает .$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)$

Вы можете легко проверить это за линейное время, поскольку граф имеет граничную связность по крайней мере тогда и только тогда, когда его минимальная степень равна по крайней мере n / 2 . Вы уже выступали за «только если» часть. Теперь рассмотрим граф, в котором каждая вершина имеет степень не менее n / 2 и разрез, который делит граф на два множества вершин X и ˉ X с x : = | X | ≤ н / 2 . Вершина в X может иметь не более x - 1 связей с другими вершинами в$n/2$$n/2$$n/2$$X$$\bar X$$x := |X| \leq n/2$$X$$x - 1$ , и, следовательно, должны вносить не менее n / 2 - ( x - 1 ) кромок в разрез. Таким образом, срез должен иметь размер не менее x ( n / 2 - x + 1 ) . Осталось показать, что x ( n / 2 - x + 1 ) ≥ n / 2 , что верно, поскольку ( 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$

Как ни странно, единственная ссылка, которую я нахожу на этот результат, это на конференции по биоинформатике. Мне было бы очень любопытно посмотреть, было ли это доказано где-то еще.

Отредактируйте: более ранняя ссылка: Гэри Чартранд: Теоретико-графический подход к проблеме коммуникации , SIAM J. Appl. Математика 14-4 (1966), с. 778-781.