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

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

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

На графе есть ли связующее дерево в которое содержит точный набор качестве листьев. Я понял, что мы можем доказать, что это , уменьшив гамильтонов путь к этой задаче решения.G S = { х 1 , х 2 , ... , х п } Н Р - с о м п л е т $G$$G$$S=\{x_1, x_2,\ldots, x_n\}$$\sf{NP\text{-}complete}$

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

было бы также если вместо "точного набора " мы сделаем$\sf{NP\text{-}complete}$$S$

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

Я думаю, что "подмножество S" было бы , но я просто не могу доказать это, я не знаю, какую проблему я могу свести к этому. Что касается «включить множество ...», я думаю, что это может быть решено за полиномиальное время.$\sf{NP\text{-}complete}$$S$

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

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

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

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

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

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

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

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

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