максимизировать MST (G [S]) по всем индуцированным подграфам G [S] в метрическом графе

11

Была ли эта проблема изучена раньше?

Учитывая метрический неориентированный граф G (длины ребер удовлетворяют неравенству треугольника), найдите множество S вершин, таких что MST (G [S]) максимизировано, где MST (G [S]) - минимальное остовное дерево подграфа, индуцированное С. Была ли эта проблема изучена ранее? Это NP-жесткий? Большое спасибо.

цзянь
источник
Есть ли прямое использование этого подграфа в теории или на практике?
Саид
1
Если вы удалите условие метрики, легко ли доказать, что проблема NP-трудна?
Игорь Шинкарь
Взятие для включения всех вершин дает аппроксимацию. S0.5
Нил Янг

Ответы:

3

Это NP-полный путем сокращения от вершины покрытия.

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

Можно предположить, что подграф с самым тяжелым MST включает в себя все вершины степени один, потому что добавление одной из этих вершин в подмножество никогда не уменьшит количество компонентов. Таким образом, вершины , которые были удалены , чтобы сформировать подграф являются подмножеством . Можно также предположить , что эти удаленные вершины образуют вершину крышку . Поскольку, если какой-то другой индуцированный подграф сформирован путем удаления вершин, которые не образуют покрытие вершины, а - ребро, которое не покрыто, то удаление приводит к индуцированному подграфу, который по крайней мере так же хорош: у него на одну вершину меньше но еще один связанный компонент, созданный вершиной степени 1 в который был присоединен к .GGuvvHv

Таким образом, оптимальная подграф образуется путем удаления вершины крышки с . Такой подграф будет иметь ровно компонентов (по одной для каждой вершины степени один, добавленной в , либо сам по себе, либо соединенной с вершиной из ), и число вершин, равное гдеи - размер обложки. Таким образом, вес его MST будет . Чтобы максимизировать это, мы должны минимизировать .HGnHG2nkn=|V(G)|k3nk+1k

Дэвид Эппштейн
источник