¿Qué problemas de gráficos son -Hard en gráficos dirigidos (/ ponderados) pero FPT en gráficos no dirigidos (/ no ponderados)?

10

Siguiendo las preguntas equivalentes sobre NP-Completeness (ver la pregunta de peso y la pregunta dirigida ), me preguntaba cómo los problemas parametrizados se ven afectados por estos atributos.

  • ¿Qué gráficos duros son -Hard en gráficos dirigidos, pero parámetros fijos manejables en gráficos no dirigidos?NPW[1]
  • ¿Qué gráficos duros son -Hard en gráficos ponderados, pero parámetros fijos manejables en gráficos no ponderados?NPW[1]

Bien, entonces tenemos problemas que se vuelven más difíciles en la versión dirigida. ¿Qué hay de las pesas? ¿Pueden hacer el problema parametrizado más difícil?

cc.complexity-theory graph-algorithms parameterized-complexity fixed-parameter-tractable RB
fuente
Hay algunos casos que no son exactamente iguales y no se conocen. por ejemplo, calcular el ancho del árbol en gráficos no dirigidos es fpt pero no se sabe calcular el ancho del árbol dirigido si es fpt. pero en el trabajo de johnson etal hay una aproximación fpt 3.
Saeed
2
U otro caso si jugamos al juego de ancho DAG en gráficos no dirigidos obtenemos una descomposición de árbol. Pero calcular el ancho del árbol es FPT pero calcular el ancho de dag es completo para PSPACE .
Saeed

Respuestas:

9

El problema de las rutas disjuntas: dados los pares de nodos y , ¿existen rutas disjuntas de nodos que conectan los pares dados? Parametrizado por , en FPT cuando no está dirigido del trabajo seminal de Robertson y Seymour. NP-Hard para cuando se dirige - del trabajo de Fortune, Hopcroft y Wylie (1980).GkkGk=2G

Chandra Chekuri
fuente
3

Calcular el ancho del árbol y la descomposición del árbol en gráficos no dirigidos es el parámetro FPT wrt width. Muchas medidas de ancho de dígrafo (o su juego correspondiente) son equivalentes al ancho del árbol en gráficos no dirigidos. La clase de complejidad exacta de muchos de ellos no se conoce, pero recientemente se demostró que DAG-Width es PSPACE-complete .

Saeed
fuente