Reducción transitiva de DAG

Estoy buscando el algoritmo O (V + E) para encontrar la reducción transitiva dado un DAG.

Es decir, elimine tantos bordes como sea posible para que si pudiera alcanzar v desde u, para v y u arbitrarios, aún pueda alcanzar después de eliminar los bordes.

Si este es un problema estándar, indíqueme alguna solución modelo.

Podemos resolver este problema simplemente haciendo DFS desde cada vértice.

1. Para cada vértice , inicie el DFS desde cada vértice v de modo que v sea ​​el descendiente directo de u , es decir. ( u , v ) es una ventaja.$u \in G$$v$$v$$u$$(u,v)$
2. Para cada vértice accesible por el DFS desde v , elimine el borde ( u , v ' ) .$v'$$v$$(u, v')$

La complejidad general de lo anterior es la complejidad de ejecutar DFS ', que es O ( N ( N + M ) ) .$N$$O(N(N+M))$

No es lo que estas buscando. Pero solo para compartir conocimientos, puede hacerlo con mensajes si supone que cada vértice actúa como un procesador . Tenga en cuenta que cada vértice tiene un valor comparable. Por lo tanto, existen algunos vértices tales que son más grandes que todos sus vecinos. Estos vértices hacen lo siguiente:$O(|E|)$

1. Sea el vecino máximo más pequeño de v ,$u$$v$
2. enviar un mensaje a e incluir edge ( v , u ) en la salida.$u$$(v,u)$
3. Para cada vecino de u y v (y más pequeño que ambos), no incluya ( v , w ) en la salida.$w$$u$$v$$(v,w)$
4. Repita los pasos hasta que todo el borde para un vecino más pequeño v ' del vértice v esté incluido o no incluido en la salida.$(v,v')$$v'$$v$

Ahora, si un nodo recibió un mensaje de cada vecino más grande (es decir, todos los bordes ( v ' , v ) están incluidos o no incluidos, entonces el nodo v actúa como si fuera el más grande en su vecindario. Es decir, realiza el 4 pasos mencionados anteriormente.$v$$(v',v)$$v$

Este algoritmo termina en mensajes en un entorno distribuido. Sé que esto no es lo que estás pidiendo.$O(|E|)$

Lema: Si hay un borde V -> Y e Y también es un sucesor indirecto de V (por ejemplo, V -> W -> + Y), entonces el borde V -> Y es transitivo y no forma parte de la raíz transitiva.

Método: realice un seguimiento del cierre transitivo de cada vértice, trabajando desde los vértices terminales a los iniciales en orden topológico inverso. El conjunto de sucesores indirectos de V es la unión de los cierres transitivos de los sucesores inmediatos de V. El cierre transitivo de V es la unión de sus sucesores indirectos y sus sucesores inmediatos.

Algoritmo:

    Initialise Visited as the empty set.
    For each vertex V of G, 
        Invoke Visit(V).

    Visit(V):
        If V is not in Visited,
            Add V to Visited, 
            Initialise Indirect as the empty set,
            For each edge V -> W in G,
                Invoke Visit(W),
                Add Closure(W) to Indirect.
            Set Closure(V) to Indirect.
            For each edge V -> W in G,
                Add W to Closure(V),
                If W is in the set Indirect,
                    Delete the edge V -> W from G.

Esto supone que tiene una forma eficiente de realizar un seguimiento de los conjuntos de vértices (por ejemplo, mapas de bits), pero creo que esta suposición también se realiza en otros algoritmos O (V + E).

Un efecto secundario potencialmente útil es que encuentra el cierre transitivo de cada vértice de G.

Resolví el mismo problema, pero no era exactamente el mismo: solicitó el número mínimo de aristas en el gráfico después de la reducción, de modo que los vértices conectados originalmente todavía estén conectados y no se realicen nuevas conexiones. Como está claro, no dice encontrar el gráfico reducido, sino cuántos bordes redundantes están presentes. Este problema se puede resolver en O (V + E). El enlace a la explicación es https://codeforces.com/blog/entry/56326 . Pero creo que para hacer el gráfico en realidad, tendrá una alta complejidad que O (N)