Разреженные остовы графов

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

[math]\displaystyle{ (1 + \epsilon, \; \beta) }[/math]-остовы; почти аддитивные остовы

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

Для пары чисел [math]\displaystyle{ \alpha, \beta: \alpha \ge 1, \beta \ge 0 \; }[/math], подграф [math]\displaystyle{ G' = (V, H) \; }[/math] невзвешенного неориентированного графа [math]\displaystyle{ G = (V, E), H \subseteq E \; }[/math], является [math]\displaystyle{ (\alpha, \; \beta) }[/math]-остовом G, если для каждой пары вершин [math]\displaystyle{ u, w \in V \; }[/math] выполняется соотношение [math]\displaystyle{ dist_{G'} (u, w) \le \alpha \cdot dist_G (u, w) + \beta \; }[/math], где [math]\displaystyle{ dist_G (u, w) \; }[/math] обозначает расстояние между u и w в G. Мы хотим показать, что для каждого n-вершинного графа существует разреженный [math]\displaystyle{ (\alpha, \; \beta) }[/math]-остов с настолько малыми значениями [math]\displaystyle{ \alpha \; }[/math] и [math]\displaystyle{ \beta \; }[/math], насколько это возможно. Задача заключается в нахождении асимптотического компромисса между [math]\displaystyle{ \alpha \; }[/math] и [math]\displaystyle{ \beta \; }[/math], с одной стороны, и разреженностью остова – с другой.

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

Элкин и Пелег [6] установили существование и возможность эффективного построения [math]\displaystyle{ (1 + \epsilon, \; \beta) }[/math]-остовов размера [math]\displaystyle{ O(\beta \; n^{1 + 1/ \kappa }) \; }[/math] для каждого n-вершинного графа G, где [math]\displaystyle{ \beta = \beta (\epsilon, \kappa) \; }[/math] константно, если [math]\displaystyle{ \kappa \; }[/math] и [math]\displaystyle{ \epsilon \; }[/math] также константны. Зависимость [math]\displaystyle{ \beta \; }[/math] от [math]\displaystyle{ \kappa \; }[/math] и [math]\displaystyle{ \epsilon \; }[/math] описывается соотношением [math]\displaystyle{ \beta (\kappa, \epsilon) = \kappa^{log \; log \; \kappa - log \; \epsilon} }[/math].

Важной составляющей построения остова в [6] является разбиение графа на области меньшего диаметра таким образом, чтобы суперграф, порожденный этими областями, был разреженным. Исследование таких разбиений было инициировано Авербухом [2], использовавшим их для синхронизации сетей. Пелег и Шеффер [8] первыми использовали подобные разбиения для построения остовов. В частности, они построили [math]\displaystyle{ (O(\kappa), \; 1) }[/math]-остовы с [math]\displaystyle{ O(n^{1 + 1/ \kappa }) \; }[/math] ребрами. Альтхофер и др. [1] предложили альтернативное доказательство результата Пелега и Шеффера, использующее элегантный «жадный» аргумент. При помощи этого аргумента Альтхоферу и коллегам также удалось расширить свой результат на взвешенные графы, что позволило улучшить скрытую в O-нотации константу в алгоритме Пелега и Шеффера и получить сопутствующие результаты для планарных графов.

Применение

Эффективные алгоритмы вычисления разреженных [math]\displaystyle{ (1 + \epsilon, \; \beta) }[/math]-остовов были разработаны в [5] и [11]. Алгоритм из [5] использовался в работах [5, 7, 10] для вычисления приближенно кратчайших путей в централизованной, распределенной, потоковой и динамической централизованной моделях вычислений. Базовый подход, использовавшийся в этих работах, заключался в построении разреженного остова и последующем вычислении точных кратчайших путей в построенном остове. Разреженность последнего гарантирует, что вычисление кратчайших путей в остове будет намного эффективнее, чем в исходном графе.

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

Основной открытый вопрос заключается в том, возможно ли получить сходные результаты при [math]\displaystyle{ \epsilon = 0 \; }[/math]. Более формально, верно ли, что для любого [math]\displaystyle{ \kappa \ge 1 \; }[/math] и любого n-вершинного графа существует [math]\displaystyle{ (1, \; \beta (\kappa)) }[/math]-остов G с [math]\displaystyle{ O(n^{1 + 1/ \kappa}) \; }[/math] ребрами? Для значений [math]\displaystyle{ \kappa \; }[/math], равных 2 и 3, в работах [3, 4, 6] на этот вопрос был дан утвердительный ответ. Некоторые нижние границы недавно были доказаны Вудруффом [12].

Менее острая проблема заключается в улучшении соотношения зависимости [math]\displaystyle{ \beta \; }[/math] от [math]\displaystyle{ \epsilon \; }[/math] и [math]\displaystyle{ \kappa \; }[/math]. Некоторого прогресса в этом отношении достигли Торуп и Цвик [11], а также Петти [9].

См. также

• Синхронизаторы, остовы

Литература

1. Althofer, I., Das, G., Dobkin, D.P., Joseph, D., Soares, J.: On Sparse Spanners of Weighted Graphs. Discret. Comput. Geom. 9,81-100(1993)

2. Awerbuch, B.: Complexity of network synchronization. J. ACM 4,804-823(1985)

3. Baswana, S., Kavitha, T., Mehlhorn, K., Pettie, S.: New Constructions of (alpha, beta)-spanners and purely additive spanners. In: Proc. of Symp. on Discrete Algorithms, Vancouver, Jan 2005, pp.672-681

4. Dor, D., Halperin, S., Zwick, U.: All Pairs Almost Shortest Paths. SIAM J. Comput. 29,1740-1759 (2000)

5. Elkin, M.: Computing Almost Shortest Paths. Trans. Algorithms 1(2),283-323(2005)

6. Elkin, M., Peleg, D.: (1 + e, /J)-Spanner Constructions for General Graphs. SIAM J. Comput. 33(3), 608-631 (2004)

7. Elkin, M., Zhang, J.: Efficient Algorithms for Constructing (1 + e, /J)-spanners in the Distributed and Streaming Models. Distrib. Comput. 18(5), 375-385 (2006)

8. Peleg, D., Schaffer, A.: Graph spanners. J. Graph Theory 13, 99-116(1989)

9. Pettie, S.: Low-Distortion Spanners. In: 34th International Colloquium on Automata Languages and Programm, Wroclaw, July 2007, pp. 78-89

10. Roditty, L., Zwick, U.: Dynamic approximate all-pairs shortest paths in undirected graphs. In: Proc. of Symp. on Foundations of Computer Science, Rome, Oct. 2004, pp. 499-508

11. Thorup, M., Zwick, U.: Spanners and Emulators with sublinear distance errors. In: Proc. of Symp. on Discrete Algorithms, Miami, Jan. 2006, pp. 802-809

12. Woodruff, D.: Lower Bounds for Additive Spanners, Emulators, and More. In: Proc. of Symp. on Foundations of Computer Science, Berckeley, Oct. 2006, pp. 389-398