Gracias por tus respuestas. Como foo maestro señalado , el segundo problema - dado un grafo dirigido y tres vértices distintos y , decidir si existe un camino simple de a pasando por - es de hecho NP-completo.s , tyostyo
Del artículo The Directed Subgraph Homeomorphism Problem de Steven Fortune, John E. Hopcroft y James Wyllie, queda claro que el gráfico de patrón es uno para el cual el problema de homeomorfismo del subgrafo fijo fijo es NP-completo ya que Es un árbol de profundidad dos.s → i → t
Aquí hay algunas definiciones de este documento:
El problema del homeomorfismo del subgrafo es determinar: si un gráfico de patrón p es homeomorfo a un subgráfico de un gráfico de entrada G. El homeomorfismo asigna nodos de P a nodos de G y arcos de P a senderos simples en G. Los gráficos P y G son ya sea ambos dirigidos o ambos no dirigidos. Las rutas en G que corresponden a los arcos en P deben ser pares por nodo. La asignación de nodos en P a nodos en G puede especificarse o dejarse arbitraria. Este problema puede verse como un problema generalizado de búsqueda de ruta. Por ejemplo, si el gráfico de patrón consta de dos arcos disjuntos y se proporciona el mapeo de nodos, entonces el problema es equivalente a encontrar un par de caminos disjuntos entre los vértices especificados en el gráfico de entrada.
Básicamente, solo los gráficos de patrones que son árboles de profundidad uno y sus gráficos inversos (posiblemente con arcos de bucles en la raíz) se pueden resolver en tiempo polinómico.
Sea C la colección de todos los gráficos dirigidos con un nodo distinguido llamado raíz que posee la propiedad de que la raíz es la cabeza de cada arco o la raíz es la cola de cada arco. Tenga en cuenta que la raíz puede ser la cabeza y la cola de algunos arcos y, por lo tanto, se permiten bucles en la raíz. De manera equivalente, un gráfico está en C si, cuando se eliminan todos los bucles en la raíz y se combinan múltiples arcos entre pares de nodos en arcos individuales, el gráfico resultante es un árbol de altura como máximo.
[...]
A continuación mostramos que para cada patrón P que no está en C, el problema de homeomorfismo del subgrafo fijo con el patrón P es NP-completo.
Todavía no he leído la prueba, así que me detendré aquí.
También hay una estrecha conexión con el problema que acabo de mencionar y el problema de las dos rutas disjuntas como lo señaló uno de mis colegas. El problema de las dos rutas dijsoint es:
Dado un gráfico dirigido y cuatro vértices distintos , decida si existen dos nodos por pares que rutas simples de a y de a .s1,t1,s2,t2s1t2s2t2
Es bien sabido que este problema para los gráficos dirigidos es NP-completo. Sin embargo, hay una transformación simple del problema de las dos rutas disjuntas al problema . Para hacer eso, necesitamos agregar un nodo adicional y los dos bordes adicionales e .s → i → tyot1→ ii →s2
Si hubiera un algoritmo polinomial para resolver el problema , podríamos usarlo para resolver el problema de las dos rutas disjuntas en tiempo polinomial con la transformación simple anterior y resolver así el problema .s → i → ts → i → t
Este es un problema NP-difícil.
fuente