¿Qué tan costoso puede ser destruir todos los caminos largos en un DAG?

Consideramos DAG (gráficos acíclicos dirigidos) con un nodo fuente $s$ un nodo objetivo $t$ ; Se permiten bordes paralelos que unen el mismo par de vértices. A $k$ - corte es un conjunto de bordes cuya eliminación destruye todas las $s$ - $t$ caminos de más de $k$ ; ¡las rutas $s$ - $t$ cortas así como las rutas "internas" largas (aquellas que no están entre $s$ y $t$ ) pueden sobrevivir!

Pregunta: ¿Es suficiente eliminar como máximo una porción de $1/k$ de los bordes de un DAG para destruir todas rutas $s$ - $t$ más largas que $k$ ?

Es decir, si denota el número total de aristas en G , ¿entonces cada DAG G tiene un corte k con a lo sumo aproximadamente e ( G ) / k aristas? Dos ejemplos:$e(G)$$G$$G$$k$$e(G)/k$

1. Si todas rutas s - t tienen una longitud > k , entonces existe un corte k con ≤ e ( G ) / k aristas. Esto es porque entonces debe haber k disjuntos k -cuts: solo la capa de los nodos de G de acuerdo a su distancia desde el nodo fuente s . $s$$t$$> k$$k$$\leq e(G)/k$$k$$k$$G$$s$
2. Si es un torneo transitivo (un DAG completo), entonces también un corte k con ≤ k ( n /$G=T_n$$k$existen bordes: arregla un orden topológicode los nodos, divide los nodos en kintervalos consecutivos de longitudn/k, y elimina todos los bordes que unen los nodos del mismo intervalo; esto destruirá todosloscaminoss-tmás largos quek. $\leq k\binom{n/k}{2} \approx e(G)/k$$k$$n/k$$s$$t$$k$

Nota 1: Un intento ingenuo para dar una respuesta positiva (que yo también probé como la primera) sería para tratar de demostrar que cada DAG debe tener acerca de disjuntos k -cuts. Desafortunadamente, el Ejemplo 2 muestra que este intento puede fallar gravemente: a través de un argumento agradable, David Eppstein ha demostrado que, para k, aproximadamente $k$ $k$$k$ , ¡el gráficoTnno puede tener más de cuatrok-cortesdisjuntos! $\sqrt{n}$$T_n$ $k$

Observación 2: Es importante que un -cut solo necesite destruir todas las rutas s - t largas , y no necesariamente todas las rutas largas. Es decir, existen ¹ DAG en el que cada "puro" k -cut (evitando aristas incidentes a s o t ) debe contener casi todos los bordes. Entonces, mi pregunta en realidad es: ¿puede la posibilidad de eliminar también bordes incidentes con s o t reducir sustancialmente el tamaño de un corte k ? Lo más probable es que la respuesta sea negativa, pero todavía no pude encontrar un contraejemplo. $k$$s$$t$$k$$s$$t$$s$$t$$k$

Motivación: Mi pregunta está motivada por probar límites inferiores para redes monótonas de conmutación y rectificación. Dicha red es solo un DAG, algunos de cuyos bordes están etiquetados por las pruebas "¿es ?" (no hay pruebas x i = 0 ). El tamaño de una red es el número de bordes etiquetados. Se acepta un vector de entrada, si hay una ruta s - t , todas cuyas pruebas son consistentes con este vector. Markov ha demostrado que, si una función booleana monótona f no tiene minterms más cortos que l y no maxterms más cortos que w ⋅ $x_i=1$$x_i=0$$s$$t$$f$$l$$w$ , entonces el tamaño $l\cdot w$es necesario. Una respuesta positiva a mi pregunta implicaría que las redes de tamaño sobre son necesarias, si al menos las variables w k deben establecerse en 0 para destruir todos los minterms más largos que $k\cdot w_k$$w_k$$0$$k$ .

¹ La construcción se da en este documento. Tome un árbol binario completo de profundidad log n . Eliminar todos los bordes. Para cada nodo interno v , dibuje un borde hacia v desde cada hoja del subárbol izquierdo de T v , y un borde desde v hasta cada hoja del subárbol derecho de T v . Por lo tanto, cada dos hojas de T están conectadas por una ruta de longitud 2 en el DAG. El DAG en sí tiene ~ n nodos y ~ n log n bordes, pero $T$$\log n$$v$$v$$T_v$$v$$T_v$$T$$2$$\sim n$$\sim n\log n$ √ bordes deben eliminarse para destruir todos los caminos más largos que$\Omega(n\log n)$ .$\sqrt{n}$

[Respuesta propia; esta es una versión abreviada, la antigua se puede encontrar aquí ]

Nos dimos cuenta con Georg Schnitger de que la respuesta a mi pregunta es muy negativa : hay DAG (incluso de grado constante), donde cada corte debe tener una fracción constante de todos los bordes, no solo una fracción de aproximadamente 1 / k , como en mi pregunta. (Se puede obtener un resultado ligeramente más débil de que puede ser necesaria una fracción 1 / log k utilizando una construcción mucho más simple mencionada en la nota al pie de página anterior.$k$$1/k$$1/\log k$ Aquí se )

A saber, en el documento "Sobre reducción de profundidad y rejillas" , Georg construyó una secuencia de gráficos acíclicos dirigidos de grado máximo constante d en n = m 2 m nodos con la siguiente propiedad:$H_n$$d$$n=m2^m$

• Para cada constante hay una constante c > 0 tal que, si algún subconjunto de a lo sumo c n nodos se elimina de H n , el gráfico restante contiene una ruta de longitud de al menos 2 ϵ m . $0\leq \epsilon < 1$$c > 0$$cn$$H_n$$2^{\epsilon m}$

Toma ahora dos nuevos nodos y t , y dibujar un borde de s a cada nodo de H n , y un borde de cada nodo de H n a t . El gráfico resultante G n todavía tiene como máximo 2 n + d n = O ( n $s$$t$$s$$H_n$$H_n$$t$$G_n$$2n+dn=O(n)$ aristas.

Por cada constante , hay una constante c ′ > 0 tal que, si se elimina cualquier subconjunto de c ' n bordes como máximo de G n , el gráfico restante contiene una ruta s - t con 2 ϵ $0\leq \epsilon < 1$$c ' > 0$$c'n$$G_n$$s$$t$$2^{\epsilon m}$ o Más aristas.

Prueba: llame a los nodos de nodos internos de G n . Elimine cualquier subconjunto de a lo sumo c ' n bordes de G n , donde c ' = c / 2 . Después de eso, elimine un nodo interno si fue incidente a un borde eliminado. Tenga en cuenta que a lo sumo 2 c ′ n = c n nodos internos se eliminan. Ninguno de los bordes incidentes con los nodos sobrevivientes fue eliminado. En particular, cada nodo interno sobrevivido está todavía conectado a ambos nodos s y $H_n$ $G_n$$c'n$$G_n$$c'=c/2$$2c'n=cn$$s$$t$. Por la propiedad anterior de , debe quedar un camino de longitud 2 ϵ m que consiste completamente en nodos internos sobrevividos. Como los puntos finales de cada uno de estos caminos sobrevivieron, cada uno de ellos se puede extender a un camino s - t en G $H_n$$2^{\epsilon m}$$s$$t$$G_n$ . QED

Una consecuencia es triste: no existe ningún análogo del lema de Markov para funciones con muchos plazos cortos , a pesar de que el conjunto de términos largos tiene una estructura "complicada": no se puede probar el uso de límites inferiores superlineales en el tamaño de la red utilizando este argumento "largo por ancho".

PD Este argumento "largo por ancho" (cuando todas rutas s - t son lo suficientemente largas) fue utilizado anteriormente por Moore y Shannon (1956). La única diferencia es que no permiten rectificaciones (bordes sin etiquetar). Entonces, este es, de hecho, un "argumento de Moore-Shannon-Markov".$s$$t$