Деревья с ограниченной степенью

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

Остовные деревья с ограниченной степенью; деревья Штейнера с ограниченной степенью

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

Необходимо построить остовное дерево с малой степенью для связного неориентированного графа G = (V, E). В формулировке Штейнера, помимо входного графа G, задано также множество выделенных вершин D С V. Дерево Штейнера – это дерево в G, охватывающей, по меньшей мере, множество D.

Поскольку задача нахождения остова или дерева Штейнера с минимальной возможной степенью A * является NP-полной, любопытны подходы в аппроксимации этой задачи минимизации степени. Для многих подобных комбинаторных задач цель состоит в нахождении аппроксимации за полиномиальное время (с константой или бОльшим множителем). Для задач нахождения остова и дерева Штейнера итеративные алгоритмы аппроксимации с полиномиальным временем исполнения авторства Фюрера и Рагавачари [8] (см. также [14]) находят намного лучшее решение. Степень A дерева решения не превышает A* + 1.

Имеется всего несколько естественных NP-полных задач оптимизации, для которых оптимум может быть найден с точностью до дополнительного члена величины 1. Одной такой задачей является раскраска планарного графа; раскраска в четыре цвета может быть проведена за полиномиальное время. С другой стороны, задача раскраски в три цвета является NP-полной даже для планарных графов. Другой подобной задачей является раскраска дуг графа степени Д. Если раскраска в Д + 1 цветов всегда может быть выполнена за полиномиальное время, задача раскраски в Д цветов является NP-полной.

Хватал [3] определил меру связности графа x{G) как минимальное отношение jXj/c(X), такое, что подграф G, порожденный VnX имеет c(X) > 2 связных компонентов. Отсюда непосредственно следует справедливость неравенства 1/T(G) < A*. Уин [17] показал, что A* < -^щ + 3; иначе говоря, инверсия меры связности является хорошей аппроксимацией A*.

Множество X, такое, что отношение jXj/c(X) является мерой связности T(G), может рассматриваться как свидетель для верхней границы jXj/c(X) для T(G) и, следовательно, для нижней границы c(X)/jXj для A*. Делая это понятие более строгим, Фюрер и Рагавачари [8] определяют X как множество свидетелей решения для A* > d , если d – наименьшее целое число, большее или равное (jXj + c(X) — 1)/jXj. Их алгоритм выводит в качестве результата не только остовное дерево, но и множество свидетелей решения X, доказывая, что его степень не превышает A* + 1.

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

Легко показать, что задачи вычисления остовного дерева с минимальной степенью и дерева Штейнера являются NP-полными, поскольку они содержат задачу нахождения гамильтонова пути. Следовательно, не следует ожидать, что алгоритм с полиномиальным временем исполнения сможет найти минимальную возможную степень A*. Из того же рассуждения следует, что аппроксимацию с множителем, меньшим 3/2, невозможно провести за полиномиальное время, если только не верно соотношение P = NP. Ранние алгоритмы аппроксимации получали решение степени O(A* log n) [6], где n = j Vj – количество вершин. Оптимальный результат для случая остовного дерева был получен Фюрером и Рагавачари [7, 8].

Теорема 1. Пусть A* – степень остовного дерева с неизвестной минимальной степенью для входного графа G = (V, E). Существует алгоритм аппроксимации с полиномиальным временем исполнения для решения задачи вычисления остовного дерева с минимальной степенью, который находит остовное дерево, степень которого не превышает A* + 1. Впоследствии этот результат был расширен на случай дерева Штейнера [8].

Теорема 2. Предположим, что в задаче нахождения дерева Штейнера заданы граф G = (V, E) и произвольное подмножество D множества вершин V. Пусть A* – степень остовного дерева с неизвестной минимальной степенью для входного графа G, охватывающего по меньшей мере множество D. Тогда существует алгоритм аппроксимации с полиномиальным временем исполнения для нахождения дерева Штейнера с минимальной степенью, который находит дерево Штейнера, степень которого не превышает A* + 1. Оба алгоритма выполняются за время O(mn ■ log na(m, n)), где m – число дуг, а a – обратная функция Аккермана.

Применение

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

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

Клейн, Кришнан, Рагавачари и Рави [11] сумели найти двусвязные подграфы с приближенной минимальной степенью в двусвязных графах, а также остовные деревья с приближенной минимальной степенью (ветвления) в ориентированных графах. Эти алгоритмы выполняются за квазиполиномиальное время и аппроксимируют степень A* с приближением (1 + e)A* + O(log1+e n). Нередко задача заключается в нахождении остовного дерева, обладающего одновременно минимальной степенью и малым весом. Для графа, имеющего остовное дерево с минимальным весом (минимальное остовное дерево, или MST) со степенью A* и весом w, Фишер [5] находит остовное дерево со степенью O(A* + log n) и весом w, т.е. MST с малым весом, за полиномиальное время. Конеманн и Рави [12,13] предложили аппроксимацию по двум критериям. Пусть дано B* > A*, и пусть w – минимальный вес некоторого остовного дерева со степенью, не превышающей B*. Алгоритм находит остовное дерево со степенью O(B* + log n) и весом O(w) за полиномиальное время. Во второй статье алгоритм был адаптирован для случая, когда каждая вершина имеет собственную границу степени. Чаудхури и коллеги [2] еще более улучшили этот результат, предложив аппроксимацию одновременно для степени B* и для веса w с константным сомножителем. Еще одно расширение задачи вычисления остовного дерева с минимальной степенью предложили Рави и Сингх [15], получившие сильную аппроксимацию остовного дерева со степенью A* + 1 [8]. Их алгоритм за полиномиальное время вычисляет остовное дерево с минимальным весом со степенью A* + k для случая графа, дуги которого имеют k различных весов.

В последнее время некоторые результаты были значительно улучшены. Пусть w – минимальная стоимость некоторого остовного дерева с заданной степенью B*. Алгоритм Геманса [9] дает остовное дерево со стоимостью w и степенью B* + 2. Сингху и Лау [16] удалось понизить степень до B* + 1, сохранив индивидуальные границы степени A * для каждой вершины v таким же образом.

Известны также любопытные алгоритмы аппроксимации для задачи вычисления двумерного Евклидова остовного дерева с минимальным весом и ограниченной степенью, в котором вершины представляют собой точки на плоскости, а веса дуг – евклидовы расстояния между ними. Хуллер, Рагавачари и Янг [10] предложили аппроксимации с коэффициентами 1,5 и 1,25 для границ степени 3 и 4, соответственно. Эти границы впоследствии были слегка улучшены Чаном [1]. Чуть более слабые результаты получили Фекете и коллеги [4], используя потоковые методы для более общего случая, в котором весовая функция всего лишь удовлетворяет неравенству треугольника.

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

Временная сложность алгоритмов вычисления остовного дерева с минимальной степенью и дерева Штейнера [8] составляет O(mna(m,n)\ogn). Можно ли улучшить это время до O(mn)? В частности, будет ли полезно сначала выбрать более подходящее дерево Штейнера при помощи некоторого жадного алгоритма, вместо того, чтобы начинать итерации с произвольного дерева Штейнера? Существует ли эффективный параллельный алгоритм, способный получить аппроксимацию Л* + 1 за полилогарифмическое время? Фюрер и Рагавачари [6] получили подобный NC-алгоритм, но только для аппроксимации степени с коэффициентом O(log n).

См. также

• Полностью динамическая связность
• Связность графа
• Широковещательная передача в беспроводных сетях с минимальными энергозатратами
• Минимальные остовные деревья
• Лес Штейнера
• Деревья Штейнера

Литература

1. Chan, T.M.: Euclidean bounded-degree spanning tree ratios. Discret. Comput. Geom. 32(2), 177-194 (2004)

2. Chaudhuri, K., Rao, S., Riesenfeld, S., Talwar, K.: A push-relabel algorithm for approximating degree bounded MSTs. In: Proceedings of the 33rd International Colloquium on Automata, Languages and Programming (ICALP 2006), Part I. LNCS, vol.4051, pp. 191-201. Springer, Berlin (2006)

3. Chvatal, V.: Tough graphs and Hamiltonian circuits. Discret. Math. 5, 215-228 (1973)

4. Fekete, S.P., Khuller, S., Klemmstein, M., Raghavachari, B., Young, N.: A network-flow technique for finding low-weight-bounded-degree spanning trees. In: Proceedings of the 5th Integer Programming and Combinatorial Optimization Conference (IPCO 1996) and J. Algorithms 24(2), 310-324 (1997)

5. Fischer, T.: Optimizing the degree of minimum weight spanning trees, Technical Report TR93-1338. Cornell University, Computer Science Department (1993)

6. Furer, M., Raghavachari, B.: An NC approximation algorithm for the minimum-degree spanning tree problem. In: Proceedings of the 28th Annual Allerton Conference on Communication, Control and Computing, 1990, pp. 174-281

7. Furer, M., Raghavachari, B.: Approximating the minimum degree spanning tree to within one from the optimal degree. In: Proceedings of the Third Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 1992), 1992, pp. 317-324

8. Furer, M., Raghavachari, B.: Approximating the minimum-degree Steiner tree to within one of optimal. J. Algorithms 17(3), 409-423(1994)

9. Goemans, M.X.: Minimum bounded degree spanning trees. In: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006, pp. 273-282

10. Khuller, S., Raghavachari, B., Young, N.: Low-degree spanning trees of small weight. SIAM J. Comput. 25(2), 355-368 (1996)

11. Klein, P.N., Krishnan, R., Raghavachari, B., Ravi, R.: Approximation algorithms for finding low-degree subgraphs. Networks 44(3),203-215(2004)

12. Konemann, J., Ravi, R.: A matter of degree: Improved approximation algorithms for degree-bounded minimum spanning trees. SIAM J. Comput. 31 (6), 1783-1793 (2002)

13. Konemann, J., Ravi, R.: Primal-dual meets local search: Approximating MSTs with nonuniform degree bounds. SIAM J. Comput. 34(3), 763-773 (2005)

14. Raghavachari, B.: Algorithms for finding low degree structures. In: Hochbaum, D.S. (ed.) Approximation Algorithms for NP-Hard Problems. pp. 266-295. PWS Publishing Company, Boston (1995)

15. Ravi, R., Singh, M.: Delegate and conquer: An LP-based approximation algorithm for minimum degree MSTs. In: Proceedings of the 33rd International Colloquium on Automata, Languages and Programming (ICALP 2006) Part I.LNCS, vol.4051, pp. 169-180. Springer, Berlin (2006)

16. Singh, M., Lau,L.C.: Approximating minimum bounded degree spanning trees to within one of optimal. In: Proceedings of the thirty-ninth Annual ACM Symposium on Theory of Computing (STOC 2007), New York, NY, 2007, pp. 661-670

17. Win, S.: On a connection between the existence of k-trees and the toughness of a graph. Graphs Comb. 5(1), 201-205 (1989)