K-минимальное остовное дерево - K-minimum spanning tree

Пример неориентированного графа с крайними затратами
4-МСТ
6-МСТ

В k-минимальная проблема остовного дерева, учился в теоретическая информатика, запрашивает дерево минимальной стоимости, которое имеет ровно k вершины и образует подграф большего графа. Его еще называют k-MST или же взвешенный по краям k-кардинальность дерева. Найти это дерево NP-жесткий, но его можно аппроксимировать с точностью до константы коэффициент аппроксимации в полиномиальное время.

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

Вход в проблему состоит из неориентированный граф с грузами по краям и номер k. На выходе получается дерево с k вершины и k − 1 ребра, причем все ребра выходного дерева принадлежат входному графу. Стоимость вывода - это сумма весов его ребер, а цель - найти дерево с минимальной стоимостью. Проблема была сформулирована Лозовану и Зеликовский (1993)[1] и по Рави и др. (1996).

Рави и др. также рассматривается геометрическая версия задачи, которую можно рассматривать как частный случай задачи о графах. k-минимальная задача остовного дерева, вход - набор точек на плоскости. Опять же, на выходе должно быть дерево с k точек как его вершины, минимизируя общее Евклидова длина его краев. То есть это график k-минимальное остовное дерево на полный график с евклидовыми расстояниями в качестве весов.[2]

Вычислительная сложность

Когда k фиксированная константа, k-минимальная проблема остовного дерева может быть решена в полиномиальное время по перебор алгоритм, который пробует все k-наборы вершин. Однако для переменной k, то k-минимальная проблема остовного дерева оказалась NP-жесткий по снижение от Дерево Штейнера проблема.[1][2]

Редукция принимает в качестве входных данных экземпляр проблемы дерева Штейнера: взвешенный граф с подмножеством его вершин, выбранных в качестве терминалов. Задача дерева Штейнера - соединить эти терминалы деревом с минимально возможным весом. Чтобы преобразовать эту проблему в экземпляр k-минимальная проблема остовного дерева, Рави и др. (1996) прикрепить к каждому терминалу дерево ребер нулевого веса с большим числом т вершин на дерево. (Для графика с п вершины и р терминалы, они используют т = п − р − 1 добавили вершины для каждого дерева.) Затем они просят k-минимальное остовное дерево в этом расширенном графе с k = rt. Единственный способ включить такое количество вершин в k-spanning tree - использовать по крайней мере одну вершину из каждого добавленного дерева, так как не останется достаточно вершин, если хотя бы одно из добавленных деревьев пропущено. Однако для этого выбора k, это возможно для k- связующее дерево, включающее в себя только небольшое количество ребер исходного графа, необходимое для соединения всех терминалов. Следовательно k-минимальное остовное дерево должно быть сформировано путем объединения оптимального дерева Штейнера с достаточным количеством ребер с нулевым весом добавленных деревьев, чтобы сделать общий размер дерева достаточно большим.[2]

Даже для графа, веса ребер которого принадлежат множеству {1, 2, 3}, проверка того, меньше ли значение оптимального решения заданного порога, НП-полный. Он остается NP-полным для планарные графы. Геометрическая версия задачи также NP-трудна, но не принадлежит к NP из-за трудности сравнения сумм квадратных корней; вместо этого он лежит в классе проблем, сводимых к экзистенциальная теория реальности.[2]

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

Алгоритмы приближения

Из-за высокой вычислительной сложности поиска оптимального решения k-минимальное остовное дерево, большая часть исследований по проблеме вместо этого сосредоточена на аппроксимационные алгоритмы для проблемы. Цель таких алгоритмов - найти приближенное решение за полиномиальное время с малым коэффициент аппроксимации. Коэффициент аппроксимации определяется как отношение длины вычисленного решения к оптимальной длине для наихудшего случая, который максимизирует это отношение. Поскольку снижение NP-твердости для k-минимальная задача остовного дерева сохраняет вес всех решений, она также сохраняет твердость приближения проблемы. В частности, поскольку проблема дерева Штейнера NP-трудна для аппроксимации коэффициент аппроксимации лучше 96/95,[3] то же самое верно и для k-минимальная проблема остовного дерева.

Лучшее приближение, известное для общей задачи, достигает отношения приближения 2, и Гарг (2005).[4] Это приближение во многом опирается на первично-дуальную схему Гоэманс и Уильямсон (1992).[5]Когда вход состоит из точек в Евклидова плоскость (любые два из которых могут быть соединены в дереве со стоимостью, равной их расстоянию) существует схема аппроксимации полиномиальным временем разработан Арора (1998).[6]

Рекомендации

  1. ^ а б Лозовану, Д .; Зеликовский, А. (1993), "Задачи о минимальных и ограниченных деревьях", Tezele Congresului XVIII al Academiei Romano-Americane, Кишинев, п. 25. Как цитирует Рави и др. (1996).
  2. ^ а б c d е Ravi, R .; Sundaram, R .; Marathe, M .; Rosenkrantz, D .; Рави, С. (1996), "Короткие или маленькие остовные деревья", Журнал SIAM по дискретной математике, 9 (2): 178–200, arXiv:математика / 9409222, Дои:10.1137 / S0895480194266331, S2CID  8253322. Предварительная версия этой работы была представлена ​​ранее, на 5-м ежегодном симпозиуме ACM-SIAM по дискретным алгоритмам, 1994, стр. 546–555.
  3. ^ Хлебик, Мирослав; Хлебикова, Янка (2008), "Проблема дерева Штейнера на графах: результаты о несовместимости", Теоретическая информатика, 406 (3): 207–214, Дои:10.1016 / j.tcs.2008.06.046.
  4. ^ Гарг, Навин (2005), "Сохранение эпсилона: 2-приближение для задачи k-MST в графах", Материалы 37-го ежегодного симпозиума ACM по теории вычислений, стр. 396–402, Дои:10.1145/1060590.1060650, S2CID  17089806..
  5. ^ Гоэманс, М.; Уильямсон, П. (1992), "Общая методика аппроксимации для задач с ограниченными лесами", SIAM Журнал по вычислениям, 24 (2): 296–317, CiteSeerX  10.1.1.55.7342, Дои:10.1137 / S0097539793242618, S2CID  1796896.
  6. ^ Арора, Санджив (1998), "Полиномиальные схемы аппроксимации евклидова коммивояжера и другие геометрические задачи", Журнал ACM, 45 (5): 753–782, Дои:10.1145/290179.290180, S2CID  3023351.

внешняя ссылка