Ширина ленты графа

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

Алгоритмы аппроксимации; метрические вложения

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

Задача нахождения ширины ленты графа заключается в установлении линейного порядка над вершинами графа [math]\displaystyle{ G = (V, E) \; }[/math], позволяющего минимизировать максимальное «растяжение» любого ребра в этом упорядочении. Более формально, пусть [math]\displaystyle{ n = |V| \; }[/math]. Рассмотрим любое взаимно-однозначное отображение [math]\displaystyle{ \pi : V \rightarrow \{ 1, 2, ..., n \} }[/math]. Ширина этого упорядочения составляет [math]\displaystyle{ bw_{\pi } (G) = max_{ \{ u, v \} \in E} | \pi (u) - \pi (v) | }[/math]. Ширина ленты графа G задается шириной ленты лучшего возможного упорядочения: [math]\displaystyle{ bw(G) = min_{\pi } bw_{\pi }(G) \; }[/math].

Изначально эта задача возникла в процессе предварительной обработки разреженных симметричных квадратных матриц. Пусть A – такая матрица [math]\displaystyle{ n \times n \; }[/math] ; рассмотрим задачу нахождения матрицы перестановок P, такой, что все ненулевые элементы [math]\displaystyle{ P^T AP \; }[/math] располагаются в максимально возможно узкой полосе вблизи от диагонали. Эта задача эквивалентна задаче минимизации ширины ленты графа G, имеющего вершины {1, 2, ..., n} и содержащего ребро {u, v} в том и только том случае, когда [math]\displaystyle{ A_{u, v} \ne 0 }[/math].

Взамен этого факта можно попытаться эффективно вычислить линейный порядок [math]\displaystyle{ \pi \; }[/math] , для которого [math]\displaystyle{ bw_{\pi }(G) \le A \cdot bw(G) }[/math], сделав при этом коэффициент аппроксимации A минимально возможным. Было показано, что задача получения любого значения A = O(1) является NP-полной [18]. Основная сложность при нахождении ширины ленты графа заключается в том, что целевая функция представляет собой максимум по всем ребрам графа. В силу этого подход «разделяй и властвуй» для нахождения ширины ленты графа неэффективен, в отличие от таких родственных задач, как алгоритм минимального линейного ранжирования [6] (здесь задача заключается в минимизации [math]\displaystyle{ \textstyle \sum_{ \{ u, v \} \in E} | \pi (u) - \pi (v) | }[/math]). Таким образом, требуется более глобальный алгоритм. Вначале следует обсудить нахождение хорошей нижней границы значения bw(G).

Локальная плотность

Обозначим для любой пары вершин [math]\displaystyle{ u, v \in V \; }[/math] за [math]\displaystyle{ d(u,v) \; }[/math] кратчайшее расстояние между u и v в графе G. Затем определим [math]\displaystyle{ B(v, r) = \{ u \in V : d(u, v) \le r \} }[/math] как шар радиуса r вокруг вершины [math]\displaystyle{ v \in V \; }[/math]. Наконец, определим локальную плотность G как [math]\displaystyle{ D(G) = max_{v \in V, r \ge 1} | B(v, r) | / (2r) }[/math]. Нетрудно заметить, что [math]\displaystyle{ bw(G) \ge D(G) \; }[/math]. Было высказано предположение, что существует верхняя граница вида [math]\displaystyle{ bw(G) \le poly(log \; n) \cdot D(G) }[/math], но до выхода основополагающей работы Файги [7] оно оставалось недоказанным.

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

Файги доказал следующие положения.

Теорема 1. Существует эффективный алгоритм, который для графа [math]\displaystyle{ G = (V, E) \; }[/math] устанавливает линейный порядок [math]\displaystyle{ \pi : V \rightarrow \{ 1, 2, ..., n \} }[/math], для которого [math]\displaystyle{ bw_{\pi } (G) \le O \Big( (log \; n)^3 \sqrt{log \; n \; log \; log \; n} \Big) \cdot D(G) }[/math]. В частности, имеется полилогарифмический относительно n /poly(log n)/ алгоритм аппроксимации для решения задачи нахождения ширины ленты в графах общего вида.

Алгоритмическую структуру Файги можно вкратце описать следующим образом.

1. Вычислить представление [math]\displaystyle{ f: \rightarrow \mathbb{R}^n }[/math] графа G в евклидовом пространстве.

2. Пусть [math]\displaystyle{ u_1, u_2, ..., u_n \; }[/math] – независимые случайные переменные N(0, 1); для каждой вершины [math]\displaystyle{ v \in V \; }[/math] вычислить [math]\displaystyle{ h(v) = \sum_{i=1}^n u_i f_i(v) }[/math], где [math]\displaystyle{ f_i(v) \; }[/math] – i-я координата вектора [math]\displaystyle{ f(v) \; }[/math]. N(0, 1) обозначает стандартную нормальную случайную переменную со средним значением 0 и отклонением 1.

3. Отсортировать вершины по значению h(v), разрывая связи произвольным образом, и выдать порожденный линейный порядок.

Эквивалентная характеризация этапов (2) и (3) необходима для выбора равномерного случайного вектора [math]\displaystyle{ a \in S^{n-1} }[/math] из (n-1)-мерной сферы [math]\displaystyle{ S^{n-1} \subset \mathbb{R}^n }[/math] и выдачи линейного порядка, порожденного значениями [math]\displaystyle{ h(v) = \big\langle a, f(v) \big\rangle }[/math], где [math]\displaystyle{ \big\langle \cdot , \cdot \big\rangle }[/math] обозначает обычное скалярное произведение над [math]\displaystyle{ \mathbb{R}^n }[/math]. Иными словами, вначале алгоритм вычисляет отображение [math]\displaystyle{ f: \rightarrow \mathbb{R}^n }[/math], проецирует изображения вершин на произвольно ориентированную линию и затем выдает порожденный в результате линейный порядок; этап (2) представляет собой стандартный способ реализации подобной случайной проекции.

Вложения с учетом объема

Осталось охарактеризовать только этап (1). Функция f должна каким-либо образом сохранять структуру графа G, чтобы алгоритм мог выдавать порядок с низкой шириной ленты. Существование такой функции f обуславливается наличием поля метрических вложений с малым уровнем искажений (см., например, [2, 14]). Файги предложил обобщение вложений с малым уровнем искажений до отображений, называемых вложениями с учетом объема. Грубо говоря, отображение f должно быть нерасширяющимся в том смысле, что [math]\displaystyle{ \parallel f(u) — f(v) \parallel \le 1 }[/math] для каждого ребра [math]\displaystyle{ \{ u, v \} \in E \; }[/math], и должно обладать следующим свойством: для любого набора из k вершин [math]\displaystyle{ v_1, ..., v_k \; }[/math], [math]\displaystyle{ (k-1) \; }[/math]-мерный объем выпуклой оболочки точек [math]\displaystyle{ f(v_1), ..., f(v_k) \; }[/math] должен быть максимально возможно большим. Для оптимизации эффективности алгоритма выбирается подходящее значение k. Точные определения вложений с учетом объема и детальное изложение их построения можно найти в работах [7, 10, 11]. Файге показал, что модификация алгоритма вложения Бургейна [2] дает отображение [math]\displaystyle{ f: \rightarrow \mathbb{R}^n }[/math], достаточно хорошее для обеспечения справедливости теоремы 1.

Требование [math]\displaystyle{ \parallel f(u) — f(v) \parallel \le 1 }[/math] для каждого ребра {u, v} является естественным, поскольку f(u) и f(v) должны иметь сходные проекции на произвольное направление a; из этого интуитивно следует, что u и v будут отображаться в порожденном линейном порядке не слишком далеко друг от друга. Но даже если |h(u) — h(v)| мало, может оказаться, что между h(u) и h(v) проецируется слишком много вершин, из-за чего между u и v возникает значительное растяжение. Чтобы избежать такой ситуации, изображения вершин должны быть в достаточной мере «разнесены», что соответствует требованию большого объема выпуклой оболочки изображений.

Применение

Как было отмечено ранее, задача нахождения ширины ленты графа находит применение в процессе предварительной обработки разреженных симметричных матриц. Минимизация ширины ленты матриц позволяет повысить эффективность определенных алгоритмов линейной алгебры – например, гауссова исключения; см. [3, 8, 17]. Последующие работы показали, что техники Файги можно применять к задачам проектирования СБИС [19].

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

Вначале сформулируем гипотезу о ширине ленты (подробнее, например, в [13]).

Гипотеза: для любого графа G = (V, E) с n вершинами имеем [math]\displaystyle{ bw(G) = O(log \; n) \cdot D(G) \; }[/math].

Эта интересная гипотеза не доказана даже для специального случая, когда G является деревом (в [ ] приведены наилучшие результаты для деревьев). Наилучшая известная граница в общем случае, основанная на работах [7, 10], имеет вид [math]\displaystyle{ bw(G) = O(log \; n)^{3.5} \cdot D(G) }[/math]. Известно, что приведенная в гипотезе верхняя граница является наилучшей возможной, даже для деревьев [4]. Можно ожидать, что подобные комбинаторные исследования позволят усовершенствовать алгоритмы аппроксимации.

Однако наилучшие алгоритмы аппроксимации, достигающие показателя [math]\displaystyle{ O((log \; n)^3 (log \; log \; n)^{1/4)} }[/math], не основываются на границе локальной плотности. Они скорее представляют собой гибрид подходов полуопределенного программирования [1, 5] с учетом предложений Файги и методов вложения с учетом объема, изложенных в [12, 16]. Определение аппроксимируемости задачи нахождения ширины ленты графа является значимой открытой проблемой; для ее решения требуется улучшение как верхней, так и нижней границ.

Литература

1. Blum, A., Konjevod, G., Ravi, R., Vempala, S.: Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems. Theor. Comput. Sci. 235(1), 25-42 (2000), Selected papers in honor of Manuel Blum (Hong Kong, 1998)

2. Bourgain,J.:On Lipschitz embedding of finite metric spaces in Hilbert space. Israel J. Math. 52(1-2), 46-52 (1985)

3. Chinn, P.Z., Chvatalova, J., Dewdney, A.K., Gibbs, N.E.: The bandwidth problem for graphs and matrices—a survey. J. Graph Theory 6(3), 223-254 (1982)

4. Chung, F.R.K., Seymour, P.D.: Graphs with small bandwidth and cutwidth. Discret. Math. 75(1-3), 113-119 (1989). Graph theory and combinatorics, Cambridge (1988)

5. Dunagan, J., Vempala, S.: On Euclidean embeddings and bandwidth minimization. In: Randomization, approximation, and combinatorial optimization, pp. 229-240. Springer (2001)

6. Even, G., Naor, J., Rao, S., Schieber, B.: Divide-and-conquer approximation algorithms via spreading metrics. J. ACM 47(4), 585-616(2000)

7. Feige, U.: Approximating the bandwidth via volume respecting embeddings. J. Comput. Syst. Sci. 60(3), 510-539 (2000)

8. George, A., Liu, J.W.H.: Computer solution of large sparse positive definite systems. Prentice-Hall Series in Computational Mathematics, Prentice-Hall Inc. Englewood Cliffs (1981)

9. Gupta, A.: Improved bandwidth approximation for trees and chordal graphs. J. Algorithms 40(1), 24-36 (2001)

10. Krauthgamer, R., Lee, J.R., Mendel, M., Naor, A.: Measured descent: A new embedding method for finite metrics. Geom. Funct. Anal. 15(4), 839-858 (2005)

11. Krauthgamer, R., Linial, N., Magen, A.: Metric embeddings-beyond one-dimensional distortion. Discrete Comput. Geom. 31(3),339-356(2004)

12. Lee, J.R.: Volume distortion for subsets of Euclidean spaces. In: Proceedings of the 22nd Annual Symposium on Computational Geometry, ACM, Sedona, AZ 2006, pp. 207-216.

13. Linial, N.: Finite metric-spaces—combinatorics, geometry and algorithms. In: Proceedings of the International Congress of Mathematicians, vol. III, Beijing, 2002, pp. 573-586. Higher Ed. Press, Beijing (2002)

14. Linial, N., London, E., Rabinovich, Y.: The geometry of graphs and some of its algorithmic applications. Combinatorica 15(2), 215-245(1995)

15. Papadimitriou, C.H.: The NP-completeness of the bandwidth minimization problem. Computing 16(3), 263-270 (1976)

16. Rao, S.: Small distortion and volume preserving embeddings for planar and Euclidean metrics. In: Proceedings of the 15th Annual Symposium on Computational Geometry, pp. 300-306. ACM, New York (1999)

17. Strang, G.: Linear algebra and its applications, 2nd edn. Academic Press [Harcourt Brace Jovanovich Publishers], New York (1980)

18. Unger, W.: The complexity of the approximation of the bandwidth problem. In: 39th Annual Symposium on Foundations of Computer Science, IEEE, 8-11 Oct 1998, pp. 82-91.

19. Vempala, S.: Random projection: A new approach to VLSI layout. In: 39th Annual Symposium on Foundations of Computer Science, IEEE, 8-11 Oct 1998, pp. 389-398.