Tenemos un DAG Tenemos una función en los nodos (en términos generales, numeramos los nodos). Nos gustaría crear un nuevo gráfico dirigido con estas reglas:
- Solo los nodos con el mismo número pueden contraerse en el mismo nodo nuevo. . (Sin embargo, .)
- Agregamos todos los bordes antiguos entre los nuevos nodos: .
- Este nuevo gráfico sigue siendo un DAG.
¿Cuál es el mínimo? ¿Qué es un algoritmo que crea un gráfico nuevo mínimo?
Respuestas:
Un enfoque para resolver este problema sería utilizar la programación lineal entera (ILP). Abordemos la versión de decisión del problema: dado , ¿hay alguna forma de contraer vértices del mismo color para obtener un DAG de tamaño ≤ k ?k ≤k
Esto puede expresarse como una instancia de ILP utilizando técnicas estándar. Se nos da el color de cada vértice en el gráfico original. Sugiero que etiquetemos cada vértice con una etiqueta en ; se contraerán todos los vértices con la misma etiqueta y el mismo color. Entonces, el problema de decisión se convierte en: ¿existe un etiquetado, de modo que la contratación de todos los vértices del mismo color produzca un DAG?{1,2,…,k}
Para expresar esto como un programa lineal entero, introduzca una variable entera para cada vértice v , para representar la etiqueta en el vértice v . Suma la desigualdad 1 ≤ ℓ v ≤ k .ℓv v v 1≤ℓv≤k
El siguiente paso es expresar el requisito de que el gráfico contratado debe ser un DAG. Tenga en cuenta que si hay un etiquetado del formulario mencionado anteriormente, sin pérdida de generalidad, existe un etiquetado en el que las etiquetas inducen una clasificación topológica en el gráfico contratado (es decir, si → w en el gráfico inicial donde v , wv precede a en el gráfico contratado, entonces la etiqueta de v es más pequeño que la etiqueta de w ). Entonces, para cada borde v → w en el gráfico original, agregaremos la restricción de que v y w tienen la misma etiqueta y el mismo color, o de lo contrario la etiqueta de v es más pequeña que la etiqueta de w . Específicamente, para cada borde vw v w v→w v w v w v→w v,w tiene el mismo color, agregue la desigualdad . Para cada arista v → w donde v , w tiene diferentes colores, agregue la desigualdad ℓ v < ℓ w .ℓv≤ℓw v→w v,w ℓv< ℓw
Ahora vea si hay alguna solución factible para este programa lineal entero. Habrá una solución factible si y solo si el etiquetado es de la forma deseada (es decir, contraer todos los vértices del mismo color produce un DAG). En otras palabras, habrá una solución factible si y solo si hay una manera de contraer el gráfico original a un DAG de tamaño . Podemos usar cualquier solucionador de programación lineal de enteros; Si el solucionador de ILP nos da una respuesta, tenemos una respuesta al problema de decisión original.≤ k
Por supuesto, no se garantiza que esto se complete en tiempo polinómico. No hay garantías Sin embargo, los solucionadores de ILP se han vuelto bastante buenos. Esperaría que, para un gráfico de tamaño razonable, tenga una posibilidad decente de que un solucionador de ILP pueda resolver este problema en un período de tiempo razonable.
También es posible codificar esto como una instancia SAT y usar un solucionador SAT. No sé si eso sería más efectivo. Sin embargo, es probable que sea más fácil pensar en la versión ILP.
(Espero que esto sea correcto. No he revisado todos los detalles con cuidado, ¡así que por favor revise mi razonamiento! Espero no haber salido mal en alguna parte).
Actualización (21/10): Parece que los ILP de esta forma se pueden resolver en tiempo lineal, procesando el DAG en orden ordenado topológicamente y haciendo un seguimiento del límite inferior en la etiqueta para cada vértice. Esto me hace sospechar de mi solución: ¿he cometido un error en alguna parte?
fuente
NOTA: AFAICT, DW encontró un agujero en esta reducción y está mal (ver comentarios). Manteniéndolo aquí por razones históricas.
Introducción : primero reduciré el problema Monotone 3SAT a nuestro problema. Aunque el problema de Monotone 3SAT es trivialmente satisfactorio, nuestro problema puede resolver aún más el problema de True Monotone 3SAT mínimo , que es NP-hard; Por lo tanto, este problema es NP-duro.
Reducción de Monotone 3SAT a nuestro problema
Tenemos una fórmula booleana monótona expresada como una secuencia de variables y una secuencia de cláusulas. El CNF tiene la forma tal que:Φ = ( V, C)
y
Conversión
Construimos un gráfico, . Cada vértice en G ' tiene una etiqueta; los vértices con la misma etiqueta son elegibles para contracción.sol′= V′, E′ sol′
Primero construimos el gráfico de la siguiente manera: para cada , hacemos dos nodos, cada uno etiquetado como x i , y un borde dirigido de uno a otro (haga clic en las imágenes para una vista de alta resolución).Xyo∈ V Xyo
Por supuesto, estos nodos pueden contraerse porque tienen la misma etiqueta. Consideraremos que las variables / nodos que se contratan se valoran como falsos, y los que no se contraen se valoran como verdaderos :
Aquí hay otra visualización, desenrollando la restricción de la cláusula:
Por lo tanto, cada restricción de cláusula requiere que al menos una de las variables que contiene permanezca sin contraer; Como los nodos no contratados se valoran como verdaderos, esto requiere que una de las variables sea verdadera; exactamente lo que Monotone SAT requiere para sus cláusulas.
Reducción del mínimo verdadero monótono 3SAT
Monotone 3SAT es trivialmente satisfactorio; simplemente puede establecer todas las variables en verdadero.
Sin embargo, dado que nuestro problema de minimización de DAG es encontrar la mayoría de las contracciones, esto se traduce en encontrar la asignación satisfactoria que produce la mayoría de las variables falsas en nuestro CNF; que es lo mismo que encontrar las variables mínimas verdaderas. Este problema a veces se llama Mínimo Verdadero Monótono 3SAT o aquí (como un problema de optimización o problema de decisión), o k-True Monotone 2SAT (como un problema de decisión más débil); ambos problemas NP-difíciles. Por lo tanto, nuestro problema es NP-hard.
Referencias
Fuentes de gráficos:
fuente
Con cada reemplazo (excepto los reemplazos directos padre-hijo), agrega nuevas relaciones ancestro-descendiente que hacen que no sea trivial determinar cuál realmente vale la pena a largo plazo. Por lo tanto, un algoritmo codicioso simple fallará en el caso general. Sin embargo, si realiza un enfoque de fuerza bruta, puede determinar el gráfico más pequeño:
Python-ish (no probado):
No estoy seguro de si realmente es un problema difícil, pero jugar con algunos gráficos manualmente parece muy combinatorio. Tengo curiosidad por saber si algo difícil puede reducirse a este problema, o si hay un algoritmo con mejor tiempo de ejecución.
fuente