Была ли эта проблема изучена раньше?
Учитывая метрический неориентированный граф G (длины ребер удовлетворяют неравенству треугольника), найдите множество S вершин, таких что MST (G [S]) максимизировано, где MST (G [S]) - минимальное остовное дерево подграфа, индуцированное С. Была ли эта проблема изучена ранее? Это NP-жесткий? Большое спасибо.
Ответы:
Это NP-полный путем сокращения от вершины покрытия.
Пусть - граф, в котором трудно найти оптимальное покрытие вершин. Создайте новый граф с вдвое большим числом вершин, путем присоединения новой степени одной вершины к каждой вершине . Превратите в метрическое пространство, сделав расстояние между соседними вершинами равным а расстояние между несмежными вершинами равным . Для этого метрического пространства вес минимального остовного дерева индуцированного подграфа равен количеству вершин плюс число связанных компонент подграфа минус один.G H G H 1 2
Можно предположить, что подграф с самым тяжелым MST включает в себя все вершины степени один, потому что добавление одной из этих вершин в подмножество никогда не уменьшит количество компонентов. Таким образом, вершины , которые были удалены , чтобы сформировать подграф являются подмножеством . Можно также предположить , что эти удаленные вершины образуют вершину крышку . Поскольку, если какой-то другой индуцированный подграф сформирован путем удаления вершин, которые не образуют покрытие вершины, а - ребро, которое не покрыто, то удаление приводит к индуцированному подграфу, который по крайней мере так же хорош: у него на одну вершину меньше но еще один связанный компонент, созданный вершиной степени 1 в который был присоединен к .G G uv v H v
Таким образом, оптимальная подграф образуется путем удаления вершины крышки с . Такой подграф будет иметь ровно компонентов (по одной для каждой вершины степени один, добавленной в , либо сам по себе, либо соединенной с вершиной из ), и число вершин, равное гдеи - размер обложки. Таким образом, вес его MST будет . Чтобы максимизировать это, мы должны минимизировать .H G n H G 2n−k n=|V(G)| k 3n−k+1 k
источник