Problemas gráficos que son NP-Completo en gráficos dirigidos pero polinomio en gráficos no dirigidos

16

Estoy buscando problemas que se sabe que son NPC para gráficos dirigidos pero tienen un algoritmo polinomial para gráficos no dirigidos.

He visto la pregunta sobre los problemas "dirigidos" al revés que son más fáciles que su variante "no dirigida" , pero estoy buscando dureza en el lado dirigido.

Por ejemplo, se sabe que el conjunto de bordes de retroalimentación es NPC en tiempo dirigido pero polinómico solucionable en gráficos no dirigidos.

¿Qué otros problemas naturales tienen la misma propiedad?

cc.complexity-theory ds.algorithms graph-theory graph-algorithms np-hardness RB
fuente
2
La conectividad st es un ejemplo interesante para clases análogas de nivel inferior: L para el caso no dirigido versus NL-complete para el caso dirigido.
Huck Bennett

Respuestas:

18

El primer problema que me viene a la mente es el problema de 2 rutas (o más generalmente, el problema de k-rutas). Dado y ( s 2 , t 2 ) , encuentre dos caminos disjuntos de s 1 a t 1 y s 2 a t 2 , respectivamente. El problema es NPC para gráficos dirigidos, pero polinomial en tiempo solucionable para gráficos no dirigidos (aunque no trivial).(s1,t1)(s2,t2)s1t1s2t2

Bangye
fuente
1
¿Podría por favor proporcionar una cita para este NPC?
Austin Buchanan
8
Ver [ND40] "Rutas de conexión disjuntas" en Garey y Johnson. Pero el estado en los Comentarios está desactualizado. El NPC para cualquier fijo se puede encontrar en: S. Fortune, JE Hopcroft, J. Wyllie, The subgraph dirigido problema de homeomorfismo, Theoret. Comput Sci. 10 (1980) 111-121. El estado de complejidad de la versión no dirigida también se ha actualizado varias veces. Se demostró que para cualquier k fija, la versión no dirigida es polinómica. N. Robertson, PD Seymour, Gráfico de menores. XIII El problema de los caminos disjuntos, J. Combin. Teoría Ser. B 63 (1) (1995) 65–110. k≥2k
Bangye
Muy lindo @Bangye!
RB
10

Decidir la existencia de una cobertura de 3 ciclos es -completonortePAG en gráficos dirigidos, mientras que es polinomial solucionable en gráficos no dirigidos mediante una reducción a una coincidencia perfecta.

Mohammad Al-Turkistany
fuente
3

En el problema Path Coloring, se nos da un árbol T y una colección de rutas en ese árbol (la idea es que T es una red de comunicación y las rutas son solicitudes de comunicación). Queremos colorear las rutas con un número mínimo de colores para que dos rutas que comparten un borde tomen colores distintos.

Se sabe que este problema puede resolverse en tiempo polinómico si T es un árbol no dirigido de grado acotado. Sin embargo, es NP completo si T es un árbol binario bidireccional. Creo que ambos resultados se dan en el siguiente documento.

[1] T. Erlebach y K. Jansen. "La complejidad de la coloración de ruta y la programación de llamadas". Informática teórica, 255 (1-2): 33–50, 2001.

Michael Lampis
fuente
1

Si no me equivoco, obtener una aproximación de factor constante para el árbol de Steiner es NP-duro en los gráficos dirigidos, pero es el tiempo P en los gráficos no dirigidos.

Suresh Venkat
fuente