¿Cuántos cortes de bordes disjuntos debe tener un DAG?

La siguiente pregunta se relaciona con la optimalidad de Bellman-Ford - t corta algoritmo de programación dinámica ruta (ver este post para una conexión). Además, una respuesta positiva implicaría que el tamaño mínimo de un programa de ramificación no determinista monótono para el problema STCONN es Θ ( n 3 ) . $s$$t$$\Theta(n^3)$

Sea un DAG (gráfico acíclico dirigido) con un nodo fuente sy un nodo objetivo t . A k - corte es un conjunto de aristas, cuya eliminación destruye todas las s - t caminos de longitud ≥ k ; suponemos que existen tales caminos en G . Tenga en cuenta que las rutas s - t más cortas no necesitan ser destruidas.$G$$s$$t$$k$$s$$t$$\geq k$$G$$s$$t$

Pregunta: ¿El debe tener al menos (aproximadamente) k disjuntos k -cuts? $G$$k$ $k$

Si no hay rutas - t más cortas que k , la respuesta es SÍ, porque tenemos el siguiente hecho conocido de min-max (un dual al teorema de Menger ) atribuido a Robacker ^∗ . Un corte s - t es un corte k para k = 1 (destruye todas las rutas s - t ).$s$$t$$k$^$\ast$$s$$t$$k$$k=1$ $s$$t$

Realidad: en cualquier gráfico dirigido, el número máximo de cortes - t de arista disjunta es igual a la longitud mínima de una ruta s - t . $s$$t$$s$$t$

Tenga en cuenta que esto se cumple incluso si el gráfico no es acíclico.

Prueba: Trivialmente, el mínimo es al menos el máximo, ya que cada ruta - t se cruza con cada corte s - t en un borde. Para ver la igualdad, deje que d ( u ) sea ​​la longitud de un camino más corto de s a u . Sea U r = { u : d ( u ) = r } , para r = 1 , ... , d ( t ) , y sea E $s$$t$$s$$t$$d(u)$$s$$u$$U_r=\{u\colon d(u)=r\}$$r = 1,\ldots, d(t)$$E_r$ser el conjunto de aristas que salen de . Está claro que los conjuntos E r son disjuntos, porque los conjuntos U r son tales. Por lo tanto, queda por demostrar que cada E r es un corte s - t . Para mostrar esto, tomar un arbitraria s - t trayectoria p = ( u 1 , u 2 , ... , u m ) con u 1 = s y u m = t . Desde $U_r$$E_r$$U_r$$E_r$$s$$t$$s$$t$$p=(u_1, u_2, \ldots,u_m)$$u_1=s$$u_m=t$ , la secuencia de distancias d ( u 1 ) , ... , d ( u m ) debe alcanzar el valor d ( u m ) = d ( t ) comenzando en d ( u 1 ) = d ( s ) = 0 y aumentando el valor como máximo$d(u_{i+1})\leq d(u_i)+1$$d(u_1),\ldots,d(u_m)$$d(u_m)=d(t)$$d(u_1)=d(s)=0$$1$en cada paso Si algún valor disminuye, entonces debemos alcanzar el valor d ( u i ) más adelante . Entonces, debe haber una j donde un salto de d ( u j ) = r a d ( u j + 1 ) = r + 1 ocurre, lo que significa que el borde ( u j , u j + 1 ) pertenece a E r , como deseado. QED $d(u_i)$$d(u_i)$$j$$d(u_j)=r$$d(u_{j+1})=r+1$$(u_j,u_{j+1})$$E_r$

Pero, ¿qué pasa si también hay caminos más cortos (que )? ¿Alguna pista / referencia? $k$

---

JT Robacker, Min-Max Theorems on Shortest Chains and Disjoint Cuts of a Network, Research Memorandum RM-1660, The RAND Corporation, Santa Mónica, California, [12 de enero] 1956. $^{\ast}$

---

EDITAR (un día después): a través de un argumento breve y muy agradable, David Eppstein respondió negativamente a la pregunta original anterior : ¡el DAG T n completo (un torneo transitivo ) no puede tener más de cuatro k- cortes disjuntos ! De hecho, demuestra el siguiente hecho estructural interesante , para k sobre √$T_n$$k$$k$ . Un corte espurasi no contiene aristas incidentes asot.$\sqrt{n}$$s$$t$

Cada corte puro en T n contiene una ruta de longitud k . $k$$T_n$$k$

¡Esto, en particular, implica que cada dos cortes puros deben cruzarse! Pero quizás todavía hay muchos cortes k puros que no se superponen "demasiado". Por lo tanto, una pregunta relajada (las consecuencias para STCONN serían las mismas ):$k$$k$

Pregunta 2: Si cada corte puro tiene bordes ≥ M , ¿la gráfica debe tener unos bordes Ω ( k ⋅ M ) ? $k$$\geq M$$\Omega(k\cdot M)$

La conexión con la complejidad de STCONN proviene del resultado de Erdős y Gallai de que uno tiene que eliminar todos los bordes excepto de K m (sin dirigir) para destruir todos los caminos de longitud k . $(k-1)m/2$$K_m$$k$

---

EDIT 2: ahora hice la pregunta 2 en mathoverflow .

Respuesta corta: no.

$G$$n$$s$$t$$k=\sqrt{n/3}$$n/3$$s$$n/3$$t$$C$$s$$t$

$X$$G$$x$$sx$$xt$$C$$X$$n/3$$C$$s$$t$$X\setminus C$$k$$s$$t$$G\setminus C$$X\setminus C$$k$$(n/3)/k=k$$X\setminus C$$C$$C$$P$$k$

$C$$s$$P$$P$$t$$s$$P$$t$$C$$C$$n/3$$s$$t$$k$