Это NP-жесткий? Я не могу доказать это.

У меня есть проблема, и я думаю, что это NP-трудно, но я не могу доказать это.

Вот график слоя, где слой 0 - самый высокий слой, а слой L - самый низкий.

Есть некоторые направленное ребро между слоями, где ребро (А, В) указывает на то, что узел А может [крышка] узла В. И когда А может охватывать B, каждый узел на любом пути от А к В может покрыть B, B может покрывать сам.

Наконец, вот набор узлов S. Мне нужно выбрать другой набор узлов ANS и убедиться, что для каждого узла q в S существует узел p в ANS и p покрывает q.

Для каждого узла есть стоимость, и мне нужно, чтобы общая стоимость набора ANS была минимальной.

Это NP-сложная проблема? Я так думаю, но не могу доказать это.

Не могли бы вы помочь мне?

Большое спасибо.

Да, эта проблема, безусловно, NP трудно. Я отправляю этот ответ, так как вам нужны доказательства.

Если вы перейдете по этой ссылке http://en.wikipedia.org/wiki/Set_cover_problem , то это говорит о том, что оптимизационной версией проблемы минимального покрытия является NP-Hard.

Проблема в ссылке:

Для заданного набора элементов {1,2, ..., m} (называемого юниверсом) и набора S из n множеств, объединение которых равно юниверсу, проблема покрытия множеств состоит в том, чтобы идентифицировать наименьшее подмножество S, объединение которого равно вселенная. Например, рассмотрим юниверс U = {1, 2, 3, 4, 5} и набор множеств S = {{1, 2, 3}, {2, 4}, {3, 4}, {4, 5}}. Ясно, что объединение S - это U. Однако мы можем покрыть все элементы следующим меньшим числом множеств: {{1, 2, 3}, {4, 5}}

Вы можете связать это с вашей проблемой следующим образом:

S - это набор узлов, которые охватывают как минимум один узел в вашем входном наборе. Это может быть найдено путем проведения DFS на узлах входного набора с обратным направлением ребер.

Теперь проблема, описанная в ссылке, является частным случаем вашей проблемы, когда стоимость каждого узла равна, и вы просто хотите минимизировать количество узлов (наборов).

Следовательно, вашу проблему еще сложнее решить в общем случае, и, следовательно, это NP Hard.