Трудно ли NP найти минимальное доминирующее множество, содержащее желаемые вершины?

Question

Для связного неориентированного графа G = (V, E)

И желаемый набор вершин D, D is a subset of V (т.е. D \in V)

Это NP-hard найти minimum dominating set, содержащий желаемый набор вершин D?

Answer 1

Да, это NP-hard проблема. Пожалуйста, обратитесь к следующему документу, чтобы прочитать сокращение. Не стесняйтесь спрашивать, есть ли у вас проблемы с пониманием доказательства.

http://www.cs.iastate.edu/~chaudhur/cs611/Sp07/notes/lec22.pdf

Чтобы объяснить немного больше о вашей проблеме, то есть добавить ограничение D это подмножество V..... думай так - когда пытаешься доказать свою проблему NPВы уменьшаете известный NP проблема в конкретном случае вашей проблемы. Ваш конкретный случай проблемы может быть случай, когда D=V... и вы можете доказать свою проблему также NP, Надеюсь это поможет.