k - минимальное остовное дерево

Проблема $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) прикрепляют к каждому терминалу дерево ребер с нулевым весом и большим числом $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]

Ссылки

^ Jump up to: ^а ^б Лозовану, Д.; Зеликовский, А. (1993), «Задачи о минимальных и ограниченных деревьях», Tezele Congresului XVIII al Academiei Romano-Americane, Кишниев , с. 25 . Как цитируют Рави и др. (1996) .
^ Jump up to: ^а ^б ^с ^д ^и Рави, Р.; Сундарам, Р.; Марат, М.; Розенкранц, Д.; Рави, С. (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.
^ Хлебик, Мирослав; Хлебикова, Янка (2008), «Проблема дерева Штейнера на графах: результаты о неаппроксимируемости», Theoretical Computer Science , 406 (3): 207–214, doi : 10.1016/j.tcs.2008.06.046 .
^ Гарг, Навин (2005), «Сохранение эпсилона: 2-аппроксимация задачи k-MST в графах», Труды 37-го ежегодного симпозиума ACM по теории вычислений , стр. 396–402, doi : 10.1145/1060590.1060650 , S2CID 17089806 .
^ Гоеманс, М .; Уильямсон, П. (1992), «Общий метод аппроксимации для задач леса с ограничениями», SIAM Journal on Computing , 24 (2): 296–317, CiteSeerX 10.1.1.55.7342 , doi : 10.1137/S0097539793242618 , S2CID 1796896 .
^ Арора, Санджив (1998), «Схемы аппроксимации полиномиального времени для евклидова коммивояжера и других геометрических задач», Journal of the ACM , 45 (5): 753–782, doi : 10.1145/290179.290180 , S2CID 3023351 .

Внешние ссылки

Минимальное k-остовное дерево в «Сборнике задач оптимизации NP»
KCTLIB , KCTLIB — библиотека для задачи взвешенного по ребрам дерева K-мощности

[lz-1] Jump up to: ^а ^б Лозовану, Д.; Зеликовский, А. (1993), «Задачи о минимальных и ограниченных деревьях», Tezele Congresului XVIII al Academiei Romano-Americane, Кишниев , с. 25 . Как цитируют Рави и др. (1996) .

[rsmr-2] Jump up to: ^а ^б ^с ^д ^и Рави, Р.; Сундарам, Р.; Марат, М.; Розенкранц, Д.; Рави, С. (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] Гоеманс, М .; Уильямсон, П. (1992), «Общий метод аппроксимации для задач леса с ограничениями», SIAM Journal on Computing , 24 (2): 296–317, CiteSeerX 10.1.1.55.7342 , doi : 10.1137/S0097539793242618 , S2CID 1796896 .

[6] Арора, Санджив (1998), «Схемы аппроксимации полиномиального времени для евклидова коммивояжера и других геометрических задач», Journal of the ACM , 45 (5): 753–782, doi : 10.1145/290179.290180 , S2CID 3023351 .

[1]

[2]

[3]

[4]

[5]

[6]