Algoritmo para encontrar un núcleo irreducible de un DAG en tiempo O(V*e), donde e es el número de aristas en la salida

Question

Un núcleo irreducible es el término utilizado en el Manual de Informática Teórica (HTCS), Volumen A "Algoritmos y Complejidad" en el capítulo sobre algoritmos gráficos.Dado un gráfico dirigido $G=(V,E)$, un núcleo irreducible es un gráfico $G'=(V,E')$ dónde $E'$ es un subconjunto de $E$, y ambos $g$ y $G'$ tener la misma accesibilidad (es decir,sus cierres transitivos son los mismos), y eliminando cualquier borde de $E'$ no cumpliría esta condición, es decir $E'$ es mínimo (aunque no necesariamente el tamaño mínimo posible).

Un gráfico equivalente mínimo es similar, excepto que también tiene el menor número de aristas entre todos esos gráficos.Ambos conceptos son similares a una reducción transitiva, pero no iguales porque a una reducción transitiva se le permite tener aristas que no están en $E$.Dicho esto, [1] demuestra que para cada DAG, tiene un núcleo irreducible único, que también es su gráfico equivalente mínimo único y su reducción transitiva única y, por lo tanto, no hay ningún beneficio en la reducción transitiva al usar aristas que no están en el original. gráfico (hay una diferencia entre el gráfico equivalente mínimo y la reducción transitiva para algunos gráficos con ciclos, pero no para los DAG).

HTCS dice que existe un algoritmo para calcular un núcleo irreducible de un gráfico acíclico dirigido en $O(V*e)$ tiempo, donde $v$ es el número de vértices, y $e$ es el número de aristas en el núcleo irreducible, es decirel producción del algoritmo.La referencia proporcionada para esto es el siguiente artículo, para el cual aún no he podido encontrar una fuente en línea (se aceptan enlaces u otras fuentes; pronto puedo preguntar en una biblioteca de investigación si no aparece nada).

Noltemeier, H., "Reducción de gráficos dirigidos a núcleos irreducibles", Documento de debate 7505, Lehrstuhl f.Mathematische Verfahrensforschung u.Datenverarbeitung (Investigación de operaciones y procesamiento de datos), Univ.Gotinga, Gotinga, 1975.

¿Alguien sabe qué es este algoritmo?Me sorprende un poco que incluya el número de aristas en el gráfico de salida, ya que eso significaría que debería ejecutarse en $O(n^2)$ tiempo dado un gráfico de entrada con $O(n^2)$ bordes que representan un orden total, p.e.A todos los nodos se les asignan números enteros desde 1 hasta $n$, y hay una ventaja desde el nodo $yo$ a $j$ si $yo <j$.Eso no parece imposible, claro está, simplemente sorprendente.

[1] Aho, Garey y Ullman, "La reducción transitiva de un gráfico dirigido", 1972 https://epubs.siam.org/doi/10.1137/0201008

Answer 1

No conozco su algoritmo, pero el problema es fácil de resolver en $\mathcal{O}(V \cdot e)$ tiempo.La idea es simplemente hacer un DFS desde cada nodo para encontrar vértices que puedan alcanzarlo.Normalmente esto toma $\mathcal{O}(E)$ tiempo, pero podemos usar el núcleo irreductible que ya hemos construido para hacerlo en $\mathcal{O}(e)$ tiempo.

Primero tenga en cuenta que $e \geq n-1$ si la gráfica es conexa.Si no es así, solucione los componentes conectados individualmente.

Comience haciendo una clasificación topológica en los vértices, con los vértices con grado cero primero.Vértices del bucle del primero al último.cuando en el vértice $yo$, primero marque todos los vértices como inalcanzables.Luego recorre los vértices desde $i-1$ a $1$.En cada vértice $j$, si $j$ es inalcanzable y tiene una ventaja para $yo$ en el gráfico de entrada, agregue el borde $(j,i)$ al núcleo irreducible y marcar $j$ accesible.Entonces sí $j$es accesible, recorra todos los bordes $(t,j)$ en nuestro kernel, y marcar $t$ accesible.

El tipo topológico toma $\mathcal{O}(V + E)$ tiempo, y el DFS tarda $\mathcal{O}(E + V \cdot e)$ tiempo, entonces desde $e = \mathcal{\Omega}(V)$, el tiempo de ejecución es $\mathcal{O}(V \cdot e)$.

El DAG producido tiene la misma accesibilidad que el gráfico original, ya que usamos un subconjunto de los bordes originales y solo omitimos agregar el borde. $(j,i)$ si $yo$ es accesible desde $j$ incluso sin él.

Asume cierta ventaja $(j,i)$se puede eliminar manteniendo la accesibilidad.Pero por cierto, hicimos el DFS, $yo$ no era accesible desde $j$sin el borde (tenga en cuenta que cualquier camino entre ellos solo puede visitar los vértices entre ellos en el orden topológico).Por tanto, el DAG producido es irreducible.