Остовные деревья с низким растяжением

Ключевые слова и синонимы

Остовные деревья с низким средним коэффициентом растяжения

Постановка задачи

Рассмотрим взвешенный связный мультиграф [math]\displaystyle{ G = (V, E, \omega ) \; }[/math], где [math]\displaystyle{ \omega \; }[/math] – функция, отображающая множество ребер E графа G на множество положительных вещественных чисел. Вес пути P в графе P равен сумме весов ребер, входящих в этот путь. Для пары вершин [math]\displaystyle{ u, v \in V \; }[/math] за расстояние между ними в графе G принимается минимальный вес пути, соединяющего u и v в G. Для остовного дерева T графа G растяжение дуги [math]\displaystyle{ (u, v) \in E \; }[/math] определяется следующим образом:

[math]\displaystyle{ stretch_T(u, v) = \frac{dist_T(u, v)}{dist_G(u, v)} }[/math]

а среднее растяжение по всем дугам E составляет

[math]\displaystyle{ avestr(G, T) = \frac{1}{|E|} \sum_{(u, v) \in E} stretch_T(u, v). }[/math]

Среднее растяжение мультиграфа [math]\displaystyle{ G = (V, E, \omega ) \; }[/math] определяется как наименьшее среднее растяжение остовного дерева T графа G, обозначаемое avestr(G, T). Среднее растяжение для целого положительного числа n, avestr(n), представляет собой максимальное среднее растяжение n-вершинного мультиграфа G. Задача заключается в анализе асимптотического поведения функции avestr(n).

Близкая (двойственная) задача заключается в построении вероятностного распределения D остовных деревьев для графа G, такого, что значение

[math]\displaystyle{ expstr(G, D) = max_{e = (u, v) \in E} \mathbf{E}_{T \in D} (stretch_T(u, v)) }[/math]

насколько возможно мало. Аналогично, [math]\displaystyle{ expstr(G) = min_D \{ expstr(G, D) \} \; }[/math], где минимум берется среди всех распределений D остовных деревьев графа G, и [math]\displaystyle{ expstr(n) = max_G \{ expstr(G) \} \; }[/math], где максимум берется среди всех n-вершинных мультиграфов.

Рассматривая задачу как игру двух игроков с нулевой суммой, где игрок «дерево» стремится минимизировать выигрыш, а игрок «ребро» – максимизировать его, легко увидеть, что для любого целого положительного числа n avestr(n) = expstr(n) [2]. Однако вероятностная версия задачи оказывается намного более удобной для многих вариантов приложений.

Основные результаты

Эта задача изучалась еще в шестидесятых [8, 13, 15, 16]. Серьезный прогресс был достигнут Алоном и коллегами [2], показавшими, что

[math]\displaystyle{ \Omega(log \; n) = avestr(n) = expstr(n) = exp(O( \sqrt{log \; n \cdot log \; log \; n)}). }[/math]

Элкин и коллеги [9] улучшили верхнюю границу и показали, что [math]\displaystyle{ avestr(n) = expstr(n) = O(log^2 n \cdot log \; log \; n). }[/math]

Применение

Одним из вариантов применения остовных деревьев с низким растяжением служит решение систем линейных уравнений с симметричными матрицами с диагональным преобладанием. Боман и Хендриксон [5] первыми открыли удивительную связь между этими, на первый взгляд, совершенно разными задачами. Они применили остовные деревья из работы [2] для разработки алгоритмов решения задач с временем выполнения [math]\displaystyle{ m^{3/2} 2^{O( \sqrt {log \; n \; log \; log \; n }} log (1 / \epsilon) }[/math]. Шпильман и Тенг [14] улучшили их результат, продемонстрировав использование остовных деревьев [2] для решения систем линейных уравнений с диагональным преобладанием за время [math]\displaystyle{ m 2^{O( \sqrt {log \; n \; log \; log \; n }} log (1 / \epsilon) }[/math].

Применяя остовные деревья с низким растяжением, предложенные в [9], можно уменьшить время решения таких систем линейных уравнений до [math]\displaystyle{ m log^{O(1)} n log(1 / \epsilon) \; }[/math], а в случае, если системы планарны – до [math]\displaystyle{ O( n(log \; n \; log \; log \; n ) log (1 / \epsilon)) }[/math]. Используя недавно разработанную редукцию Бомана, Хендриксона и Вавасиса [6], можно получить алгоритм решения систем линейных уравнений, возникающих при применении метода конечных элементов для решения двумерных эллиптических уравнений в частных производных, с временем выполнения [math]\displaystyle{ O(n(log \; n \; log \; log \; n)^2 log(l / \epsilon)) }[/math].

Недавно Чекури и коллеги [7] использовали остовные деревья с низким растяжением для выведения приближенного алгоритма для задачи построения неоднородных сетей с применением «оптового» подхода. Данный алгоритм впервые обеспечивает гарантированную полилогарифмическую аппроксимацию этой задачи.

В своей недавней работе Абрахам и коллеги [1] использовали технику звездчатой декомпозиции, предложенную Элкиным и др. [9], для построения вложений с константным средним растяжением, где среднее значение берется по всем парам вершин, а не по всем ребрам. Результат находок Абрахама и коллег [1], в свою очередь, был использован в недавней работе Элкина и др. [10], посвященной фундаментальным контурам.

Открытые вопросы

Наиболее очевидный из открытых вопросов касается ликвидации разрыва между верхней границей [math]\displaystyle{ O(log^2 n \; log \; log \; n) }[/math] и нижней границей [math]\displaystyle{ \Omega(log \; n) }[/math] значения avestr(n). Еще одна интересная тема – изучение остовных деревьев с низким растяжением для различных ограниченных семейств графов. В этом направлении недавно достигли заметного прогресса Эмек и Пелег [11], построившие остовные деревья с низким растяжением со средним значением растяжения O(log n) для невзвешенных серийно-параллельных графов. Также обширным полем для исследований является нахождение других способов применения остовных деревьев с низким растяжением.

Наконец, имеется довольно близкое ослабленное понятие деревьев Штейнера или Бартала с низким растяжением. В отличие от остовных деревьев, дерево Штейнера не обязано быть подграфом исходного графа; оно может содержать ребра и вершины, не входящие в состав исходного графа. Однако при этом требуется, чтобы расстояния в дереве Штейнера были не меньше расстояний в исходном графе. Деревья Штейнера с низким растяжением широко исследовались [3, 4, 12]. Факхаренфол и коллеги [12] разработали алгоритм построения деревьев Штейнера с низким растяжением со средним значением растяжения O(log n). В настоящее время неизвестно, будет ли техника, используемая при изучении деревьев Штейнера с низким растяжением, полезна при улучшении границ остовных деревьев с низким растяжением.

См. также

• Аппроксимация метрических пространств древесными метриками

Литература

1. Abraham, I., Bartal, Y., Neiman, O.: Embedding Metrics into Ul-trametrics and Graphs into Spanning Trees with Constant Average Distortion. In: Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms, New Orleans, January 2007

2. Alon, N., Karp, R.M., Peleg, D., West, D.: A graph-theoretic gane and its application to the k-server problem. SIAM J. Comput. 24(1), 78-100 (1995). Also available Technical Report TR-91-066, ICSI, Berkeley (1991)

3. Bartal, Y.: Probabilistic approximation of metric spaces and its algorithmic applications. In: Proceedings of the 37th Annual Symposium on Foundations of Computer Science, Berlington, Oct. 1996 pp. 184-193

4. Bartal, Y.: On approximating arbitrary metrices by tree metrics. In: Proceedings of the 30th annual ACM symposium on Theory of computing, Dallas, 23-26 May 1998, pp. 161-168

5. Boman, E., Hendrickson, B.: On spanning tree preconditioners. Manuscript, Sandia National Lab. (2001)

6. Boman, E., Hendrickson, B., Vavasis, S.: Solving elliptic finite element systems in near-linear time with suppost preconditioners. Manuscript, Sandia National Lab. and Cornell, http://arXiv.org/abs/cs/0407022 Accessed 9 July 2004

7. Chekuri, C., Hagiahayi, M.T., Kortsarz, G., Salavatipour, M.: Approximation Algorithms for Non-Uniform Buy-at-Bulk Network Design. In: Proceedings of the 47th Annual Symp. on Foundations of Computer Science, Berkeley, Oct. 2006, pp. 677-686

8. Deo, N., Prabhu, G.M., Krishnamoorthy, M.S.: Algorithms for generating fundamental cycles in a graph. ACM Trans. Math. Softw. 8, 26^2(1982)

9. Elkin, M., Emek, Y., Spielman, D., Teng, S.-H.: Lower-Stretch Spanning Trees. In: Proc. of the 37th Annual ACM Symp. On Theory of Computing, STOC'05, Baltimore, May 2005, pp. 494-503

10. Elkin, M., Liebchen, C., Rizzi, R.: New Length Bounds for Cycle Bases. Inf. Proc. Lett. 104(5), 186-193 (2007)

11. Emek, Y., Peleg, D.: A tight upper bound on the probabilistic embedding of series-parallel graphs. In: Proc. of Symp. on Discr. Algorithms, SODA'06, Miami, Jan. 2006, pp. 1045-1053

12. Fakcharoenphol, J., Rao, S., Talwar, K.: A tight bound on approximating arbitrary metrics by tree metrics. In: Proceedings of the 35th annual ACM symposium on Theory of Computing, San Diego, June 2003, pp. 448^55

13. Horton, J.D.: A Polynomial-time algorithm to find the shortest cycle basis of a graph. SIAM J. Comput. 16(2), 358-366 (1987)

14. Spielman, D., Teng, S.-H.: Nearly-linear time algorithm for graph partitioning, graph sparsification, and solving linear systems. In: Proc. of the 36th Annual ACM Symp. on Theory of Computing, STOC'04, Chicago. USA, June 2004, pp. 81-90

15. Stepanec, G.F.: Basis systems of vector cycles with extremal properties in graphs. Uspekhi Mat. Nauk 19, 171-175 (1964). (In Russian)

16. Zykov, A.A.: Theory of Finite Graphs. Nauka, Novosibirsk (1969). (In Russian)