В поисках пауков

Существует ли алгоритм полиномиального времени, чтобы найти - если он существует - остовный паук данного графа ? Паук - это дерево с не более чем одним узлом со степенью больше 2: я знаю, что различные условия степеней на (по существу, достаточно большие степени узлов) гарантируют существование остовного паука. Но мне интересно , если есть алгоритм для произвольных . Спасибо! $G$
введите описание изображения здесь
$G$ $G$

ds.algorithms reference-request graph-theory graph-algorithms Джозеф О'Рурк
источник

В качестве первого результата поиск «паучьих пауков в поисках гуглов» показал версию статьи Gargano, Hammar, Hell, Stacho и Vaccaro 2004 . Предложение 1 утверждает, что оно NP-полно. Отвечает ли это на ваш вопрос?

Tsuyoshi Ito

Кажется, что к этому легко можно свести гамильтонову задачу о пути. Для данного

сделайте две копии

и для некоторой произвольной вершины

добавьте ребро

которое соединяет две копии

. Любой охватывающий паук в результирующем графе

должен пересекать

и быть гамильтоновым путем на одной из двух копий.

G

$G$

G_{1}, G_{2}

$G_1,G_2$

v \in G

$v \in G$

e

$e$

v

$v$

H

$H$

e

$e$

Чандра Чекури

Спасибо, Цуёси и Чандра! Да, это отвечает на мой вопрос. Я встречал ссылку на статью Гаргано, но не на NP-полноту, а скорее на их достаточное условие существования остовного паука.

Джозеф О'Рурк

в идеале они бы разместили свои комментарии в качестве ответов :), но ваше решение также работает

Suresh Venkat

@Suresh: В случае, если вы не знаете, я не разместил его как ответ, потому что я не думал, что этот вопрос должен был быть задан здесь в первую очередь.

Цуёси Ито

В поисках пауков

Ответы: