Ищет похожие известные проблемы

Question

Я пытаюсь доказать компьютерную сложность этой задачи оптимизации:
Для заданного связного графа G = (V, E) и множества S ⊊ V. Найдите связный подграф G'= (V', E '), который:

Min f(G')
Min |V'|

Подчинить:

S ⊊ V’
V’ ⊆ V

Это выглядит как обобщение задачи о минимальном остовном дереве, когда не все вершины должны быть включены в дерево. Есть ли известная проблема, которая может быть использована для доказательства сложности этой проблемы путем сокращения?

Answer 1

Ваша формулировка проблемы не говорит о том, что вы оптимизируете - сначала f(G') и в пределах этого Min|V'|, или наоборот, или и то, и другое вместе каким-то образом объединены.

если вы оптимизируете границы затрат, это проблема минимального дерева Штейнера (SMT) как есть и NP-полная. если вы оптимизируете | V '|, вы можете уменьшить SMT к нему за полиномиальное время следующим образом:

Пусть ребро (u,v) между узлами u и v будет стоить k. Замените этот край следующим путем:

(u, i_1), (i_1, i_2), ..., (i_k, v) 

так что стоимость каждого ребра на этом пути равна 1. Вы заменили ребро стоимости (u,v) на путь с k-1 промежуточными узлами на нем, и каждое ребро имеет стоимость 1.

Сделайте это для каждого ребра на графике. Это уменьшает SMT к вашей проблеме и доказывает, что вы оптимизируете | V '| является NP-полным. Ваше сокращение занимает

O(C*|V|^2) 

время, где C - верхняя граница стоимости ребер в графе.

Просто увидел проблему. Надеюсь, поможет.