Redução transitiva de DAG

Eu estou procurando o algoritmo O (V + E) para encontrar a redução transitiva dado um DAG.

Isso remove o maior número possível de arestas, para que, se você puder alcançar v de u, para v e u arbitrários, ainda possa alcançá-lo após a remoção das arestas.

Se este for um problema padrão, indique-me alguma solução de modelo.

Podemos resolver esse problema apenas com o DFS de cada vértice.

1. Para cada vértice , inicie o DFS a partir de cada vértice v, de modo que v seja o descendente direto de u , ie. ( u , v ) é uma vantagem.$u \in G$$v$$v$$u$$(u,v)$
2. Para cada vértice alcançável pelo DFS a partir de v , remova a aresta ( u , v ′ ) .$v'$$v$$(u, v')$

A complexidade geral do exposto acima é a complexidade da execução de DFS ', que é O ( N ( N + M ) ) .$N$$O(N(N+M))$

Não é o que você está procurando. Mas, apenas com o objetivo de compartilhar conhecimento, você pode fazer isso com mensagens se assumir que cada vértice atua como um processador . Observe que cada vértice tem um valor comparável. Portanto, existem alguns vértices que são maiores que todos os seus vizinhos. Esses vértices fazem o seguinte:$O(|E|)$

1. Seja o vizinho menor máximo de v ,$u$$v$
2. envie uma mensagem para e inclua a borda ( v , u ) na saída.$u$$(v,u)$
3. Para cada vizinho de u e v (e menor do que ambos), não incluem ( v , w ) na saída.$w$$u$$v$$(v,w)$
4. Repita as etapas até que toda a aresta para um vizinho menor v ′ do vértice v seja incluída ou não na saída.$(v,v')$$v'$$v$

Agora, se um nó recebeu uma mensagem de todo vizinho maior (ou seja, todas as arestas ( v ′ , v ) foram incluídas ou não, o nó v age como se fosse o maior da vizinhança. mencionado anteriormente 4 etapas.$v$$(v',v)$$v$

Esse algoritmo termina em mensagens em um ambiente distribuído. Eu sei que não é isso que você está pedindo.$O(|E|)$

Lema: Se existe uma aresta V -> Y e Y é também um sucessor indireto de V (por exemplo, V -> W -> + Y), então a aresta V -> Y é transitiva e não faz parte da raiz transitiva.

Método: Acompanhe o fechamento transitivo de cada vértice, trabalhando do terminal ao inicial, em ordem topológica inversa. O conjunto de sucessores indiretos de V é a união dos fechamentos transitivos dos sucessores imediatos de V. O fechamento transitivo de V é a união de seus sucessores indiretos e seus sucessores imediatos.

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.

Isso pressupõe que você tenha alguma maneira eficiente de acompanhar conjuntos de vértices (por exemplo, mapas de bits), mas acho que essa suposição também é feita em outros algoritmos O (V + E).

Um efeito colateral potencialmente útil é que ele encontra o fechamento transitivo de cada vértice de G.

Eu resolvi o mesmo problema, mas não era exatamente o mesmo. Pedi o número mínimo de arestas no gráfico após a redução, para que os vértices originalmente conectados ainda estivessem conectados e nenhuma nova conexão fosse feita. Como está claro, não é necessário encontrar o gráfico reduzido, mas quantas arestas redundantes estão presentes. Este problema pode ser resolvido em O (V + E). O link para a explicação é https://codeforces.com/blog/entry/56326 . Mas eu acho que para fazer o gráfico, ele terá alta complexidade que O (N)