Ширина ленты графа: различия между версиями

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

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

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

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

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

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

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