Problemas "dirigidos" que son más fáciles que su variante "no dirigida".

28

Estaba presentando una conferencia sobre la clasificación de panqueques , y mencioné que:

Lo que me hizo pensar. Hay un sentido en el que la clasificación "firmada" está "dirigida": puede ver el signo como una dirección (y de hecho, esta es la motivación de la biología evolutiva). ¡Pero es un problema más fácil! Esto es inusual porque generalmente (al menos en gráficos) los problemas dirigidos son más difíciles (o al menos tan difíciles) como sus contrapartes no dirigidas.

Suponiendo una definición generosa de "dirigido", ¿hay ejemplos de problemas dirigidos que sean más fáciles que sus contrapartes no dirigidas?

ds.algorithms Suresh Venkat
fuente

2

Puede considerar Horn 3SAT (cada cláusula puede representarse como (A Y B)

C) como cláusulas dirigidas, ya que pueden verse como implicaciones. Entonces, aquí el caso dirigido es fácil mientras que el 3SAT no dirigido es difícil.

\to

$\to$

Mohammad Al-Turkistany

1

Me he preguntado una pregunta similar para una clase que estaba enseñando (donde se utilizó LP para aproximar la solución IP): ¿hay una clase de problemas en los que encontrar una solución entera era más fácil que encontrar una solución rationnal

Gopi

17

El recuento de circuitos eulerianos para gráficos dirigidos es factible en tiempo polinómico usando el teorema BEST , mientras que aparentemente, el mismo problema para los gráficos no dirigidos es # P-completo .

Timothy Sun
fuente

Todas las respuestas son geniales, pero si tengo que aceptar una, es porque la brecha es grande y el problema es muy claro.

Suresh Venkat

15

Un caso interesante y no tan conocido es el siguiente. Supongamos que tenemos un gráfico borde ponderado y un nodo raíz $G$ . Queremos el gráfico secundario de costo mínimo de modo que haya rutas de borde de a cada nodo en el gráfico. Cuando este es el problema de arborescencia de costo mínimo en gráficos dirigidos y en gráficos no dirigidos, es equivalente al problema MST. Ambos pueden resolverse en tiempo polivinílico, aunque el caso no dirigido es más fácil. Sin embargo, el problema es el tiempo polisoluble en gráficos dirigidos para cualquier mientras que es NP-Hard en gráficos no dirigidos para (ya que captura el costo mínimo $r$ $G$ $k$ $r$ $k=1$ $k$ $k=2$ Problema de subgrafo conectado a bordes). $2$

Chandra Chekuri
fuente

13

Tal vez este no sea el mejor ejemplo, pero considere la Cubierta de ciclo (dirigida), donde la tarea es cubrir todos los vértices por ciclos de vértice-disjunto (dirigido). En el caso dirigido, esto puede reducirse a coincidencia bipartita y resolverse en tiempo polinómico. En el caso no dirigido, el problema puede reducirse a una coincidencia no bipartita (y viceversa), que es un problema más difícil, pero que aún puede resolverse en tiempo polinómico.

Daniel Marx
fuente

10

Un ejemplo similar más impresionante es el siguiente: dejemos que

sea un gráfico ponderado dirigido (los pesos pueden ser negativos). Podemos verificar si hay un ciclo negativo en

usando el algoritmo Ford-Bellman. Pero si

G

$G$

G

$G$

G

$G$ no está dirigido, entonces el problema se vuelve mucho más difícil (pero aún puede resolverse en el tiempo múltiple).

ilyaraz

Este es definitivamente un buen ejemplo, y en la línea de lo que estaba pensando cuando hice la pregunta.

Suresh Venkat

2

Siempre tuve la impresión de que los "problemas relacionados con los ciclos" son más fáciles en los gráficos dirigidos. Tal vez hay algún principio detrás de esto, como que los componentes conectados a 2 tienen "menos estructura" que los componentes fuertemente conectados ("problemas que involucran ciclos" = aquellos que pueden resolverse mirando por separado cada componente).

Diego de Estrada

3

Diego: si una caminata cerrada dirigida atraviesa un vértice v, entonces hay un ciclo dirigido que atraviesa v. La afirmación análoga no es cierta para los gráficos no dirigidos. Por lo tanto, en los gráficos dirigidos, a menudo podemos razonar sobre caminatas en lugar de ciclos. Las caminatas son más robustas y menos gráficas teóricas que los ciclos, lo que podría ser una ventaja. Tal vez esta sea una explicación formal de tu impresión.

Daniel Marx

9

Aquí hay un problema que, como me di cuenta recientemente, se ve realmente más difícil en los gráficos no dirigidos que en los dirigidos.

$m\sqrt{n}\log C$ $m$ $n$ $C$ $n^3, mn\log n$

$m\sqrt{n}\log C$ $n^3, mn\log n$

virgi
fuente

pero aquí 'duro' solo significa con respecto a los tiempos de ejecución (polinomiales) de los algoritmos que conocemos; podría ser que nos falta alguna técnica, por supuesto

virgi

2

Ese es otro ejemplo interesante. Y ps felicitaciones por el sorprendente nuevo resultado.

Suresh Venkat

1

Gracias Suresh! En otra nota, me di cuenta de que ilyaraz tenía mi respuesta en un comentario a la respuesta de Daniel Marx ... perdón por el duplicado.

virgi

Problemas "dirigidos" que son más fáciles que su variante "no dirigida".

Respuestas: