Полнота охватывающих деревьев

10

Покрывающее дерево графа называется деревом полноты, если множество его листьев индуцирует полный подграф в графе хоста. Учитывая граф и целое число , какова сложность определения, содержит ли дерево полноты с максимум листами?гКгК

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

Другая причина - этот вопрос (и соответствующие ответы). Оказывается, что каждое остовное дерево в является деревом полноты тогда и только тогда, когда является полным графом или циклом. гг

VB Le
источник

Ответы:

12

В графе без треугольников дерево полноты должно быть гамильтоновым циклом (минус одно из его ребер). ISGCI говорит, что гамильтонов цикл является NP-полным в графах без треугольников. Следовательно, так же происходит поиск дерева полноты (независимо от какого-либо ограничения на максимальное количество листьев).

Дэвид Эппштейн
источник
О, это хорошее наблюдение, спасибо!
VB Le
8

Я не могу победить Дэвида в элегантности его ответа. Но потратив много времени на обдумывание этой проблемы, я бы хотел предать вам свое решение;)

Пусть - фиксированное целое число. Для заданного построим следующим образом: возьмем две копии , и клику на вершинах , новой вершине , зафиксируем вершину и вершина . получается из и , соединяя с , соединяя с и соединяя всех соседейG H G 1 G 2 Q k x , x 1 , x 2 , , x k - 1 y v 1G 1 v 2G 2 H G 1 , G 2 , Q y x v 1 x 1 , х 2 , , х к - 1 ВК2гЧАСг1г2QКИкс,Икс1,Икс2,...,ИксК-1Yv1г1v2г2ЧАСг1,г2,QYИксv1Икс1,Икс2,...,ИксК-1v2v1в и всех соседей в к .г1v2г2Y

Тогда легко видеть, что имеет гамильтонов цикл, если и только если имеет дерево полноты с не более чем листьями.гЧАСК

user13136
источник