k-минимальное остовное дерево
Пример неориентированного графа со стоимостью ребер Г {\displaystyle G}
4-MST из Г {\displaystyle G}
6-MST из Г {\displaystyle G}

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

Постановка проблемы

Входные данные для задачи состоят из неориентированного графа с весами на ребрах и числа k . Выходные данные представляют собой дерево с k вершинами и k − 1 ребрами, причем все ребра выходного дерева принадлежат входному графу. Стоимостью вывода является сумма весов его ребер, а цель состоит в том, чтобы найти дерево с минимальной стоимостью. Задача была сформулирована Lozovanu & Zelikovsky (1993) [1] и Ravi et al. (1996).

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

Сложность вычислений

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

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

Даже для графа, веса ребер которого принадлежат множеству {1, 2, 3 }, проверка того, меньше ли оптимальное значение решения заданного порога, является NP-полной . Она остается 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. ^ abcde Рави, Р.; Сундарам, Р.; Марате, М.; Розенкранц, Д.; Рави, С. (1996), «Охватывающие деревья короткие или маленькие», SIAM Journal on Discrete Mathematics , 9 (2): 178–200 , arXiv : math/9409222 , doi :10.1137/S0895480194266331, S2CID  8253322. Предварительная версия этой работы была представлена ​​ранее на 5-м ежегодном симпозиуме ACM-SIAM по дискретным алгоритмам, 1994, стр. 546–555.
  3. ^ Хлебик, Мирослав; Хлебикова, Янка (2008), «Проблема дерева Штейнера на графах: результаты о неаппроксимируемости», Theoretical Computer Science , 406 (3): 207–214 , doi : 10.1016/j.tcs.2008.06.046.
  4. ^ Гарг, Навин (2005), «Сохранение эпсилона: 2-приближение для проблемы k-MST в графах», Труды 37-го ежегодного симпозиума ACM по теории вычислений , стр.  396–402 , doi :10.1145/1060590.1060650, S2CID  17089806.
  5. ^ Goemans, M .; Williamson, P. (1992), "Общая методика аппроксимации для задач ограниченного леса", SIAM Journal on Computing , 24 (2): 296–317 , CiteSeerX 10.1.1.55.7342 , doi :10.1137/S0097539793242618, S2CID  1796896 .
  6. ^ Арора, Санджив (1998), «Схемы полиномиального времени аппроксимации для евклидовых задач коммивояжера и других геометрических задач», Журнал ACM , 45 (5): 753–782 , doi : 10.1145/290179.290180 , S2CID  3023351.
  • Минимальное k-остовное дерево в "Сборнике задач оптимизации NP"
  • KCTLIB, KCTLIB — Библиотека для решения задачи о дереве с K-мощностью, взвешенной по ребрам
Получено с "https://en.wikipedia.org/w/index.php?title=K-минимальное_дерево_объединения&oldid=1250923499"