Bloqueando caminos dirigidos en un DAG con un número lineal de defectos de vértice.

Question

Sea $G=(V,E)$ un grafo dirigido acíclico. Define el conjunto de todos los caminos dirigidos en $G$ como $\Gamma$. Dado un subconjunto $W\subseteq V$, sea $\Gamma_W\subseteq \Gamma$ el conjunto de todos los caminos $\gamma\in\Gamma$ soportados en $V\backslash W$ (es decir, todos los vértices en $\gamma$ pertenecen a $V\backslash W$). Ahora define $l(W)$ como: $$l(W)=\max_{\gamma\in \Gamma_W} |\gamma|$$ Donde $|\gamma|$ es el número de vértices en $\gamma$.

Quiero demostrar (o refutar) la siguiente afirmación:

${\bf Afirmación:}$ Para todo $\epsilon>0$ y todo $k>0$, existen constantes $L$ y $N$ tal que para cualquier grafo dirigido acíclico $G=(V,E)$ que cumple $|V|>N$ con la suma de grados de entrada y salida limitada por $k$, existe un subconjunto $W\subseteq V$ tal que $\frac{|W|}{|V|}<\epsilon$ y $l(W).

La afirmación es verdadera para árboles dirigidos (ver edit 1 para una prueba) pero la misma idea de prueba falla al trabajar en grafos dirigidos acíclicos más generales. Además, la declaración deja de ser verdadera si eliminamos el requisito de grado constante para $G$. De hecho, el orden topológico máximo en vértices indexados de 1 a n no puede ser "bloqueado" por ningún conjunto $W$ de tamaño lineal en $n$ para cualquier $\epsilon>0$.

Cualquier dirección o idea sería bienvenida.

Edit 1:

Para los árboles, una prueba estándar sería así: Para $0\leq i\leq L-1$, Definir $W_L^i$ como el conjunto de todos los vértices alcanzables desde la raíz con un camino dirigido de longitud $i \pmod L$. Dado que el grafo es un árbol, dicho camino está únicamente definido para cada vértice y por lo tanto, para un $L$ dado, el conjunto $\{W_L^i\}_{0\leq i\leq L-1}$ da una partición de $V$. Por lo tanto, al elegir $L=\frac{1}{\epsilon}$, existe algún $i_0$ tal que $|W_L^{i_0}|$ es a lo sumo $\frac{|V|}{L}=\epsilon |V|$. Queda demostrar que cada $W_L^i$ es efectivamente bloqueante de $L$, pero esto es trivial ya que cualquier paso en un camino dirigido hacia abajo del árbol incrementa la distancia desde la raíz exactamente en 1, por lo que el camino más largo que no contiene vértices de $W_L^i$ debe tener una longitud de a lo sumo $L-1$ (Conectando 2 pisos adyacentes en $W_L^i$)

Edit 2:

En general, la afirmación es verdadera para cualquier DAG para el caso especial de $\epsilon = \frac{2k}{2k+1}$ y $L=1$. Para ver esto, considera el siguiente algoritmo:

1- elige un vértice $v$ en el grafo que todavía tiene vecinos. Mantén a $v$, y elimina todos sus vecinos (en ambas direcciones) del grafo

2 - si queda algún vértice no aislado, regresa al paso 1. De lo contrario, termina.

El grafo resultante está completamente desconectado ($L=1$) y hemos eliminado a lo sumo una fracción de $\epsilon=\frac{2k}{2k+1}$ de los vértices del grafo. La afirmación sigue.

Edit 3:

Como Misha Lavrov demostró, el límite anterior puede ser más ajustado y podemos probar la afirmación para $\epsilon=\frac{k}{k+1}$. Descubrí que este límite no es ajustado cuando el DAG tiene un grado total limitado por 3. En este caso, demostraré la afirmación para cualquier $\epsilon>\frac{1}{2}$ donde el límite anterior es solo $\epsilon=\frac{2}{3}$. Define el grado de entrada y el grado de salida de un vértice $v$ en $G$ como $in(v)$ y $out(v)$ respectivamente. A partir de la suposición, para todo $v \in V$, $in(v)+out(v)\leq 3$. Define 4 conjuntos: $\{V_i\}_{i=0}^3$ por: $$V_i=\{v\in V | in(v)=i\}$$

Obviamente, $\{V_i\}_{i=0}^3$ forma una partición de $V$. Por lo tanto, uno de los conjuntos $V_1$ o $V_2$ tiene cardinalidad a lo sumo $\frac{n}{2}$. Sin pérdida de generalidad, asumamos que es $V_1$. Sea $G'$ el subgrafo de $G$ inducido por $V_2$. Obviamente, para todo $v\in V_2$, $out(v)\leq 1$ y por lo tanto, $G'$ es una unión disjunta de árboles dirigidos con un vértice sumidero. Usando la prueba para árboles, para cualquier $\epsilon>0$, podemos encontrar un subconjunto $W\subseteq V_2$ tal que $\frac{|W|}{|V_2|}<\epsilon$ y $W$ es $\frac{1}{\epsilon}$-bloqueante en $G'$. Finalmente, define $W'= V_1 \cup W$. Por un lado, $|W'|$ está acotado por arriba por $(\frac{1}{2}+\epsilon)n$ y por otro lado $W'$ es de $(\frac{1}{\epsilon}+2)$-bloqueante ya que un camino dirigido en $G$ puede permanecer en $V_2$ y ser bloqueado por $W$ o salir de $V_2$ y ser bloqueado por $V_1$ o dar un último paso de $V_0$ a $V_3$ o ambos.

Esto demuestra la afirmación.

PD. Publicado en MO.

Answer 1

Sé que es un mal estilo, pero ahora no tengo tiempo para escribir correctamente (quizás lo haga más tarde), así que aquí tienes un conjunto de notas escritas a mano con un contraejemplo. Las preguntas son bienvenidas, como siempre :)