Минимальные k-связные геометрические сети

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

Геометрические графы; евклидовы графы

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

Рассматривается следующая классическая задача оптимизации: для заданной неориентированной взвешенной геометрической сети найти подсеть минимальной стоимости, удовлетворяющую заданным априори требованиям многосвязности.

Нотация

Пусть G = (V, E) – геометрическая сеть, множество вершин V которой соответствует множеству из n точек в пространстве [math]\displaystyle{ \mathbb{R}^d \; }[/math] для определенного целого числа [math]\displaystyle{ d \ge 2 \; }[/math], а множество ребер E – множеству прямолинейных сегментов, соединяющих пары точек из V. Сеть G называется полной, если E соединяет все пары точек из V.

Стоимость [math]\displaystyle{ \delta(x, y) \; }[/math] дуги, соединяющей пару точек [math]\displaystyle{ x, y \in \mathbb{R}^d \; }[/math], равна евклидовому расстоянию между точками x и y. Иначе говоря, [math]\displaystyle{ \delta(x, y) = \sqrt{ \sum^d_{i=1} (x_i - y_i)^2} }[/math], где [math]\displaystyle{ x = (x_1, ..., x_d) \; }[/math] и [math]\displaystyle{ y = (y_1, ..., y_d) \; }[/math]. В более общем виде стоимость можно определить с использованием других норм – таких как [math]\displaystyle{ \ell_p }[/math]-нормы для любого p > 1, т.е. [math]\displaystyle{ \delta(x, y) = \Big( \sum_{i=1}^p (x_i - y_i)^p \Big)^{1/p} \; }[/math]. Стоимость сети равна сумме стоимостей всех ребер сети: [math]\displaystyle{ cost(G) = \sum_{x, y \in E} \delta(x, y) \; }[/math].

Сеть G = (V, E) служит остовом множества точек S (охватывает множество точек S), если V = S. Сеть G является k-вершинно-связной, если для любого множества [math]\displaystyle{ U \subseteq V \; }[/math], состоящего из менее чем k вершин, сеть [math]\displaystyle{ (V \backslash U, E \cap ((V \backslash U) \times (V \backslash U)) }[/math] является связной. Подобным же образом G является k-реберно-связной, если для любого множества [math]\displaystyle{ \mathcal{E} \subseteq E \; }[/math] с количеством ребер менее k сеть [math]\displaystyle{ (V, E \backslash \mathcal{E}) \; }[/math] является связной.

(Евклидова) задача нахождения k-вершинно-связной остовной сети минимальной стоимости

Для заданного множества S из n точек в евклидовом пространстве [math]\displaystyle{ \mathbb{R}^d \; }[/math] найти k-вершинно-связную евклидову сеть минимальной стоимости, охватывающую точки S.

(Евклидова) задача нахождения k-реберно-связной остовной сети минимальной стоимости

Для заданного множества S из n точек в евклидовом пространстве [math]\displaystyle{ \mathbb{R}^d \; }[/math] найти k-реберно-связную евклидову сеть минимальной стоимости, охватывающую точки S.

Рассматривается также вариант, допускающий наличие параллельных ребер:

(Евклидова) задача нахождения k-реберно-связной остовной мультисети минимальной стоимости

Для заданного множества S из n точек в евклидовом пространстве [math]\displaystyle{ \mathbb{R}^d \; }[/math] найти k-реберно-связную евклидову мультисеть минимальной стоимости, охватывающую точки S (под мультисетью понимается сеть, допускающая наличие параллельных ребер.

Понятие k-связности с минимальной стоимостью естественным образом расширяется на k-связность евклидовой сети Штейнера, если разрешить использование дополнительных вершин, называемых точками Штейнера. Для заданного набора точек S в пространстве [math]\displaystyle{ \mathbb{R}^d \; }[/math] геометрическая сеть G представляет собой k-вершинно-связную (или k-реберно-связную) сеть Штейнера для S, если множество вершин G является надмножеством S и для каждой пары точек из S существует k внутренне вершинно-непересекающихся (реберно-непересекащихся, соответственно) путей, соединяющих их в G.

(Евклидова) задача нахождения k-вершинно/реберно-связной сети Штейнера минимальной стоимости

Найти сеть минимальной стоимости на надмножестве S, являющуюся k-вершинно/реберно-связной сетью Штейнера для S.

Заметим, что при k = 1 эта задача представляет собой просто задачу построения минимального дерева Штейнера, которой посвящено множество работ (см., например, [14]).

В более общей формулировке задач о многосвязности в графах следует учитывать неоднородные ограничения связности.

Задача построения сети с повышенной живучестью

Для заданного набора S точек в [math]\displaystyle{ \mathbb{R}^d \; }[/math] и функции требования связности [math]\displaystyle{ r: S \times S \to \mathbb{N} \; }[/math] найти геометрическую сеть минимальной стоимости, охватывающую точки из S, такую, что для любой пары вершин [math]\displaystyle{ p, q \in S \; }[/math] подсеть имеет [math]\displaystyle{ r_{p, q} \; }[/math] внутренне вершинно-непересекающихся (или реберно-непересекащихся, соответственно) путей между p и q.

Во многих приложениях этой задачи, нередко считающихся наиболее интересными [9, 13], функция требования связности определяется при помощи функции от одного аргумента, присваивающей каждой вершине p ее тип связности [math]\displaystyle{ r_v \in \mathbb{N} \; }[/math]. Тогда для любой пары вершин [math]\displaystyle{ p, q \in S \; }[/math] требование связности [math]\displaystyle{ r_{p, q} \; }[/math] задается просто в виде [math]\displaystyle{ min \{ r_p, r_q \} \; }[/math] [12, 13, 17, 18]. В число таких приложений входит задача о вычислении дерева Штейнера, (см., например, [2]), в которой [math]\displaystyle{ r_p \in \{ 0, 1 \} \; }[/math] для любой вершины [math]\displaystyle{ p \in S \; }[/math].

Схема аппроксимации с полиномиальным временем выполнения (PTAS) представляет собой семейство алгоритмов [math]\displaystyle{ \{ \mathcal{A}_\varepsilon \} \; }[/math], такое, что для каждого фиксированного [math]\displaystyle{ \varepsilon \gt 0 \; }[/math] алгоритм [math]\displaystyle{ \mathcal{A}_\varepsilon \; }[/math] исполняется за время, полиномиальное относительно размера входного графа, и обеспечивает [math]\displaystyle{ (1 + \varepsilon) \; }[/math]-аппроксимацию.

Родственные работы

Исчерпывающий обзор результатов решения задач о нахождении k-вершинно-связных или k-реберно-связных остовных подграфов с минимальной стоимостью, задач о неоднородной связности, задач о пополнении связности и геометрических задач приведен в работах [1, 3, 11, 15].

Несмотря на высокую практическую значимость задач о многосвязности в геометрических сетях и большое количество опубликованных практических эвристических результатов (см., например, [12, 13, 17, 18]), до недавнего времени совсем небольшое число теоретических исследований было посвящено разработке эффективных аппроксимационных алгоритмов этих задач. Эта ситуация резко контрастирует с обширным списком успешных теоретических исследований соответствующих задач на общеметрических пространствах и для взвешенных графов общего вида. Таким образом, до 1998 года даже для самой простой и наиболее фундаментальной задачи о многосвязности, а именно – задачи о нахождении 2-вершинно-связной сети минимальной стоимости, охватывающей заданный набор точек на евклидовой плоскости, не удавалось получить аппроксимации с лучшим коэффициентом, чем [math]\displaystyle{ \frac{3}{2} }[/math] (где [math]\displaystyle{ \frac{3}{2} }[/math] – это наилучший известный коэффициент аппроксимации с полиномиальным временем выполнения для сетей общего вида, веса в которых удовлетворяют неравенству треугольника [8]. Другие результаты можно найти в [4, 15]).

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

Первым результатом является расширение хорошо известного понятия о NP-полноте задачи нахождения 2-связной сети минимальной стоимости в графах общего вида (см., например, [10]) на геометрические сети.

Теорема 1. Задача нахождения 2-вершинно/реберно-связной геометрической сети минимальной стоимости, охватывающей набор из n точек на плоскости, является NP-полной.

Следующий результат показывает, что если рассматривать задачи о многосвязных объектах минимальной стоимости при достаточно большой размерности, эти задачи становятся APX-полными.

Теорема 2 ([6]). Существует константа [math]\displaystyle{ \xi \gt 0 \; }[/math], такая, что задача аппроксимации 2-связной геометрической сети минимальной стоимости, охватывающей набор из n точек в [math]\displaystyle{ \mathbb{R}^{\lceil log_2 \; n \rceil} }[/math], с коэффициентом [math]\displaystyle{ 1 + \xi \; }[/math] является NP-полной.

Этот результат также можно расширить на любую [math]\displaystyle{ \ell_p }[/math]--норму.

Теорема 3 ([6]). Для любого целого числа [math]\displaystyle{ d \ge log \; n }[/math] и любого фиксированного [math]\displaystyle{ p \ge 1 \; }[/math] существует константа [math]\displaystyle{ \xi \gt 0 \; }[/math], такая, что задача аппроксимации 2-связной сети минимальной стоимости, охватывающей набор из n точек в метрике [math]\displaystyle{ \ell_p }[/math]- в пространстве [math]\displaystyle{ \mathbb{R}^d \; }[/math], с коэффициентом [math]\displaystyle{ 1 + \xi \; }[/math] является NP-полной.

Поскольку задачи о многосвязности с нахождением объектов минимальной стоимости довольно сложны, исследователи обращаются к аппроксимационным алгоритмам. Объединяя некоторые идеи, сформулированные Аророй [2] (см. также [6]) для аппроксимационных алгоритмов задачи коммивояжера с полиномиальным временем выполнения, с несколькими новыми идеями, разработанными специально для решения задач о многосвязности в геометрических сетях, Шумай и Лингас получили следующие результаты.

Теорема 4 ([5, 6]). Пусть k и d – любые целые числа, [math]\displaystyle{ k, d \ge 2 \; }[/math], а [math]\displaystyle{ \varepsilon \; }[/math] – любое положительное вещественное число. Пусть S – множество из n точек в пространстве [math]\displaystyle{ \mathbb{R}^d \; }[/math]. Существует рандомизированный алгоритм, который за время [math]\displaystyle{ n \cdot (log \; n)^{(kd / \varepsilon)^{O(d)}} \cdot 2^{2^{(kd / \varepsilon)^{O(d)}}} }[/math] с вероятностью не менее 0,99 находит k-вершинно-связную (или k-реберно-связную) остовную сеть для S, стоимость которой не более чем в [math]\displaystyle{ (1 + \varepsilon) \; }[/math] раз превышает оптимальную.

Кроме того, этот алгоритм может быть дерандомизирован за полиномиальное время с тем, чтобы возвращать k-вершинно-связную (или k-реберно-связную) остовную сеть для S, стоимость которой не более чем в [math]\displaystyle{ (1 + \varepsilon) \; }[/math] раз превышает оптимальную.

Заметим, что в случае, если все значения d, k и [math]\displaystyle{ \varepsilon \; }[/math] являются константными, время выполнения составляет [math]\displaystyle{ n \cdot log^{O(1)} \; n }[/math].

Результат теоремы 4 позволяет получить схему аппроксимации с полиномиальным временем выполнения (PTAS) для малых значений k и d.

Теорема 5 (PTAS для вершинной или реберной связности [6, 5]). Пусть [math]\displaystyle{ d \ge 2 \; }[/math] – любое константное целое число. Существует определенная положительная константа [math]\displaystyle{ c \lt 1 \; }[/math], такая, что для всех [math]\displaystyle{ k \le (log \; log \; n)^c }[/math] задача построения k-вершинно-связной или k-реберно-связной остовной сети минимальной стоимости для множества точек в пространстве [math]\displaystyle{ \mathbb{R}^d \; }[/math] допускает использование PTAS.

В следующей теореме рассматриваются мультисети, в которых допустимые решения могут использовать параллельные ребра.

Теорема 6 ([5]). Пусть k и d – любые целые числа, [math]\displaystyle{ k, d \ge 2 \; }[/math], а [math]\displaystyle{ \varepsilon \; }[/math] – любое положительное вещественное число. Пусть S – множество из n точек в пространстве [math]\displaystyle{ \mathbb{R}^d \; }[/math]. Существует рандомизированный алгоритм, который за время [math]\displaystyle{ n \cdot log \; n \cdot (d / \varepsilon)^{O(d)} + n \cdot 2^{2^{(k^{O(1)} \cdot d / \varepsilon)^{O(d^2)})}} }[/math] с вероятностью не менее 0,99 находит k-реберно-связную остовную мультисеть для S, стоимость которой не более чем в [math]\displaystyle{ (1 + \varepsilon) \; }[/math] раз превышает оптимальную. Этот алгоритм может быть дерандомизирован за полиномиальное время.

Сочетая формулировку данной теоремы с тем фактом, что параллельные ребра можно удалить в случае k = 2, получаем следующий результат для задачи 2-связности в сетях.

Теорема 7 (Схемы аппроксимации для 2-связных графов, [5]). Пусть d – любое целое число, [math]\displaystyle{ d \ge 2 \; }[/math], а [math]\displaystyle{ \varepsilon \; }[/math] – любое положительное вещественное число. Пусть S – множество из n точек в пространстве [math]\displaystyle{ \mathbb{R}^d \; }[/math]. Существует рандомизированный алгоритм, который за время [math]\displaystyle{ n \cdot log \; n \cdot (d / \varepsilon)^{O(d)} + n \cdot 2^{(d / \varepsilon)^{O(d^2)}} }[/math] с вероятностью не менее 0,99 находит 2-вершинно-связную (или 2-реберно-связную) остовную сеть для S, стоимость которой не более чем в [math]\displaystyle{ (1 + \varepsilon) \; }[/math] раз превышает оптимальную. Этот алгоритм может быть дерандомизирован за полиномиальное время.

Для константного значения d время выполнения рандомизированных алгоритмов составляет [math]\displaystyle{ n \; log \; n \cdot (1 / \varepsilon)^{O(1)} + 2^{(1 / \varepsilon)^{O(1)}} }[/math].

Теорема 8 ([7]). Пусть d – любое целое число, [math]\displaystyle{ d \ge 2 \; }[/math], а [math]\displaystyle{ \varepsilon \; }[/math] – любое положительное вещественное число. Пусть S – множество из n точек в пространстве [math]\displaystyle{ \mathbb{R}^d \; }[/math]. Существует рандомизированный алгоритм, который за время [math]\displaystyle{ n \cdot log \; n \cdot (d / \varepsilon)^{O(d)} + n \cdot 2^{(d / \varepsilon)^{O(d^2)}} + n \cdot 2^{2^{d^{d^{O(1)}}}} }[/math] с вероятностью не менее 0,99 находит 2-вершинно-связную (или 2-реберно-связную) остовную сеть Штейнера для S, стоимость которой не более чем в [math]\displaystyle{ (1 + \varepsilon) \; }[/math] раз превышает оптимальную. Этот алгоритм может быть дерандомизирован за полиномиальное время.

Теорема 9 ([7]). Пусть d – любое целое число, [math]\displaystyle{ d \ge 2 \; }[/math], а [math]\displaystyle{ \varepsilon \; }[/math] – любое положительное вещественное число. Пусть S – множество из n точек в пространстве [math]\displaystyle{ \mathbb{R}^d \; }[/math]. Существует рандомизированный алгоритм, который за время [math]\displaystyle{ n \cdot log \; n \cdot (d / \varepsilon)^{O(d)} + n \cdot 2^{(d / \varepsilon)^{O(d^2)}} + n \cdot 2^{2^{d^{d^{O(1)}}}} }[/math] с вероятностью не менее 0,99 находит [math]\displaystyle{ (1 + \varepsilon) \; }[/math]-аппроксимацию геометрической сети с повышенной живучестью с [math]\displaystyle{ r_v \in \{ 0, 1, 2 \} \; }[/math] для любого [math]\displaystyle{ v \in V \; }[/math]. Этот алгоритм может быть дерандомизирован за полиномиальное время.

Применение

Задачи о многосвязности занимают центральное место в алгоритмической теории графов и широко применяются в сферах вычислительных наук и исследования операций – см., например, [1, 13, 11, 18]. Они также играют исключительно важную роль в решении задач о построении сетей, возникающих во многих практических ситуациях [1, 13]. Среди типичных областей применения можно упомянуть телекоммуникации, компьютерные и улично-дорожные сети. Задачи о связности низкой степени для геометрических сетей на плоскости нередко могут достаточно точно аппроксимировать подобные практические задачи (см., например, обсуждение в [13, 17, 18]). Задача построения сети с повышенной живучестью в геометрических сетях также возникает во множестве практических ситуаций – в частности, в телекоммуникациях, при проектировании сетей телекоммуникаций, проектировании СБИС и т.п. [12, 13, 17, 18].

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

Вышеприведенные результаты позволяют создавать эффективные алгоритмы только для малых значений требования связности k; время выполнения является полиномиальным только для значения k, не превышающего [math]\displaystyle{ (log \; log \; n)^c }[/math] для определенной положительной константы c < 1. Любопытно было бы узнать, можно ли получить алгоритм схемы аппроксимации с полиномиальным временем выполнения для больших значений k.

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

См. также

• Евклидова задача коммивояжера
• Минимальные геометрические остовные деревья

Литература

1. Ahuja, R.K., Magnanti, T.L., Orlin, J.B., Reddy, M.R.: Applications of network optimization. In: Handbooks in Operations Research and Management Science, vol. 7, Network Models, chapter 1,pp. 1-83. North-Holland, Amsterdam (1995)

2. Arora, S.: Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. J. ACM 45(5), 753-782 (1998)

3. Berger, A., Czumaj, A., Grigni, M., Zhao, H.: Approximation schemes for minimum 2-connected spanning subgraphs in weighted planar graphs. Proc. 13th Annual European Symposium on Algorithms, pp. 472^83. (2005)

4. Cheriyan, J., Vetta, A.: Approximation algorithms for network design with metric costs. Proc. 37th Annual ACM Symposium on Theory of Computing, Baltimore, 22-24 May 2005, pp. 167-175.(2005)

5. Czumaj, A., Lingas, A.: Fast approximation schemes for Euclidean multi-connectivity problems. Proc. 27th Annual International Colloquium on Automata, Languages and Programming, Geneva, 9-15 July 2000, pp. 856-868

6. Czumaj, A., Lingas, A.: On approximability of the minimum-cost k-connected spanning subgraph problem. Proc. 10th Annual ACM-SIAM Symposium on Discrete Algorithms, Baltimore, 17-19 January 1999, pp. 281-290

7. Czumaj, A., Lingas, A., Zhao, H.: Polynomial-time approximation schemes for the Euclidean survivable network design problem. Proc. 29th Annual International Colloquium on Au tomata, Languages and Programming, Malaga, 8-13 July 2002, pp. 973-984

8. Frederickson, G.N., JaJa, J.: On the relationship between the biconnectivity augmentation and Traveling Salesman Problem. Theor. Comput. Sci. 19(2), 189-201 (1982)

9. Gabow, H.N., Goemans, M.X., Williamson, D.P.: An efficient approximation algorithm for the survivable network design problem. Math. Program. Ser. B 82(1-2), 13-40 (1998)

10. Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-completeness. Freeman, New York, NY (1979)

11. Goemans, M.X., Williamson, D.P.: The primal-dual method for approximation algorithms and its application to network design problems. In: Hochbaum, D. (ed.) Approximation Algorithms for NP-Hard Problems, Chapter 4, pp. 144-191. PWS Publishing Company, Boston (1996)

12. Grotschel, M., Monma, C.L., Stoer, M.: Computational results with a cutting plane algorithm for designing communication networks with low-connectivity constraints. Oper. Res. 40(2), 309-330(1992)

13. Grotschel, M., Monma, C.L., Stoer, M.: Design of survivable net works. In: Handbooks in Operations Research and Manage ment Science, vol. 7, Network Models, chapter 10, pp. 617-672. North-Holland, Amsterdam (1995)

14. Hwang, F.K., Richards, D.S., Winter, P.: The Steiner Tree Problem. North-Holland, Amsterdam (1992)

15. Khuller, S.: Approximation algorithms for finding highly connected subgraphs. In: Hochbaum, D. (ed.) Approximation Algorithms for NP-Hard Problems, Chapter 6, pp. 236-265. PWS Publishing Company, Boston (1996)

16. Mitchell, J.S.B.: Guillotine subdivisions approximate polygonal subdivisions: A simple polynomial-time approximation scheme for geometric TSP, k-MST, and related problems. SIAM J. Comput. 28(4), 1298-1309 (1999)

17. Monma, C.L., Shallcross, D.F.: Methods for designing communications networks with certain two-connected survivability constraints. Operat. Res. 37(4), 531-541 (1989)

18. Stoer, M.: Design of Survivable Networks. Springer, Berlin (1992)