Encontrar arañas

¿Existe un algoritmo de tiempo polinómico para encontrar, si existe, una araña de expansión de un gráfico dado ? Una araña es un árbol con a lo sumo un nodo con un grado mayor que 2: sé que varias condiciones de grado en (esencialmente, grados de nodo suficientemente grandes) garantizan la existencia de una araña que se extiende. Pero me pregunto si hay un algoritmo para arbitrario . ¡Gracias! $G$
ingrese la descripción de la imagen aquí
$G$ $G$

ds.algorithms reference-request graph-theory graph-algorithms Joseph O'Rourke
fuente

Las "arañas que abarcan NP-completas" en Google mostraron una versión del artículo de Gargano, Hammar, Hell, Stacho y Vaccaro 2004 como primer resultado. La Proposición 1 establece que es NP-completo. ¿Responde esto a tu pregunta?

Tsuyoshi Ito

Parece que uno puede reducir fácilmente el problema del camino hamiltoniano a esto. Dado

, haga dos copias

y para algún vértice arbitrario

agregue un borde

que une las dos copias de

. Cualquier araña de expansión en el gráfico resultante

tiene que cruzar

y ser un camino hamiltoniano en una de las dos copias.

G

$G$

G_{1}, G_{2}

$G_1,G_2$

v \in G

$v \in G$

e

$e$

v

$v$

H

$H$

e

$e$

Chandra Chekuri

Gracias, Tsuyoshi y Chandra! Sí, eso responde mi pregunta. Encontré una referencia al documento de Gargano, pero no por la integridad de NP, sino por su condición suficiente para la existencia de una araña que se extiende.

Joseph O'Rourke

idealmente habrían publicado sus comentarios como respuestas :), pero su solución también funciona

Suresh Venkat

@Suresh: En caso de que no lo sepa, no lo publiqué como respuesta porque no pensé que esta pregunta debería haberse hecho aquí en primer lugar.

Tsuyoshi Ito

Encontrar arañas

Respuestas: