¿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 G (esencialmente, grados de nodo suficientemente grandes) garantizan la existencia de una araña que se extiende. Pero me pregunto si hay un algoritmo para G arbitrario . ¡Gracias!
ds.algorithms
reference-request
graph-theory
graph-algorithms
Joseph O'Rourke
fuente
fuente
99
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
13
Parece que uno puede reducir fácilmente el problema del camino hamiltoniano a esto. Dado , haga dos copias G 1 , G 2 y para algún vértice arbitrario v ∈ G agregue un borde e que une las dos copias de v . Cualquier araña de expansión en el gráfico resultante H tiene que cruzar e y ser un camino hamiltoniano en una de las dos copias.
Chandra Chekuri
1
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
1
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