Доказательство полноты NP проблемы связующего дерева

23

Я ищу некоторые подсказки в вопросе, заданном моим инструктором.

Итак, я только что выяснил, что это решение проблемы :NP-complete

На графе есть ли связующее дерево в которое содержит точный набор качестве листьев. Я понял, что мы можем доказать, что это , уменьшив гамильтонов путь к этой задаче решения.G S = { х 1 , х 2 , ... , х п } Н Р - с о м п л е т еGGS={x1,x2,,xn}NP-complete

Но мой преподаватель также спросил нас в классе:

было бы также если вместо "точного набора " мы сделаем SNP-completeS

«включать весь набор и, возможно, другие листья» или «подмножество »SSS

Я думаю, что "подмножество S" было бы , но я просто не могу доказать это, я не знаю, какую проблему я могу свести к этому. Что касается «включить множество ...», я думаю, что это может быть решено за полиномиальное время. SNP-completeS

Initialize
источник
Можете ли вы объяснить, почему вы думаете, что одна версия может быть решена за полиномиальное время?
Рафаэль
@pad: «Мой преподаватель спросил в классе» - это не задание, а головоломка. Также посмотрите эту мета-дискуссию по тегу домашней работы.
Рафаэль

Ответы:

13

Короче, ваши догадки верны. Для целей этого ответа, давайте назовем эти три проблемы следующим образом:

  • Версия равенства: Учитывая график и набор S V , решить , следует ли G имеет связующее дерево T такой , что множество листьев в Т равна S . Как вы заявили, это NP-полная за счет сокращения из задачи о гамильтоновом пути.граммзнак равно(В,Е)SВграммTTS
  • Версия Подмножества: Учитывая , и S , как указано выше, решить , следует ли G имеет связующее дерево T такой , что множество листьев в T является подмножеством S .граммSграммTTS
  • Superset версия: Учитывая и S , как указано выше, решить , будет ли G имеет охватывающее дерево T такое , что множество листьев в T является подмножеством S .граммSграммTTS

Чтобы доказать, что версия подмножества является NP-полной, вы все равно можете свести к ней проблему гамитонианского пути. Попробуйте изменить доказательство NP-полноты версии равенства.

Чтобы доказать, что версия надмножества может быть решена за полиномиальное время, попытайтесь найти необходимое и достаточное условие существования такого дерева T

Обе версии (а также некоторые другие проблемы с остовными деревьями) изучаются в [SK05]. Но я думаю, что лучше, если вы попытаетесь решить проблемы самостоятельно, прежде чем смотреть на доказательства в газете, потому что просмотр бумаги может быть большим спойлером. К сожалению, я посмотрел на статью, прежде чем пытаться найти алгоритм полиномиального времени для версии суперсета!


[SK05] Мухаммед Сохель Рахман и Мохаммад Кайкобад. Сложности некоторых интересных задач на остовных деревьях. Письма Обработки Информации , 94 (2): 93–97, апрель 2005. [ doi ] [ авторская копия ]

Цуёси Ито
источник
Рад видеть тебя здесь! Обратите внимание, что у нас здесь есть MathJax.
Рафаэль
1
Спасибо за руководство! Хотелось бы, чтобы я прочитал это до того, как я пошел на урок, сегодня он все испортил, ха-ха. В случае, если кто-то заинтересован в полиномиальном алгоритме версии над множеством, другой совет - построить новый граф с V \ L.
инициализировать
0

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

Что произойдет, если вы удалите все вершины из S из G, (VS), а затем найдете остовное дерево T с DFS? Если в G есть какие-то еще не связанные вершины, скажем, v1; Что это говорит о роли по крайней мере одной из вершин в S, которая была удалена? Что он лежит на пути к v1 из некоторой вершины, которая в настоящее время находится в остовном дереве. Таким образом, это не может быть лист (так как у листьев нет детей). Если нет несвязанных узлов, это означает, что каждая вершина в S может быть листом, если у нее есть ребро, ведущее к остовному дереву. Вершины в S, которые соединяются только с другими вершинами в S, разумеется, не будут иметь связи с остовным деревом и будут нарушать это условие. Итак, есть два случая, чтобы проверить:

  1. Если все узлы не в S соединены после удаления S из G и поиска связующего дерева
  2. Если каждый узел в S может быть подключен непосредственно к связующему дереву.
DanGoodrick
источник