Algoritmo para encontrar um kernel irredutível de um DAG em tempo O(V*e), onde e é o número de arestas na saída

Question

Um kernel irredutível é o termo usado no Handbook of Theoretical Computer Science (HTCS), Volume A "Algoritmos e Complexidade" no capítulo sobre algoritmos de grafos.Dado um gráfico direcionado $G=(V,E)$, um kernel irredutível é um gráfico $G'=(V,E')$ onde $E'$ é um subconjunto de $E$, e ambos $G$ e $G'$ têm a mesma acessibilidade (ou seja,seus fechamentos transitivos são os mesmos), e removendo qualquer aresta de $E'$ não satisfaria esta condição, ou seja, $E'$ é mínimo (embora não necessariamente o tamanho mínimo possível).

Um grafo mínimo equivalente é semelhante, exceto que também possui o menor número de arestas entre todos esses grafos.Ambos os conceitos são semelhantes a uma redução transitiva, mas não são iguais porque uma redução transitiva pode ter arestas que não estão em $E$.Dito isto, [1] prova que para cada DAG, ele possui um kernel irredutível único, que também é seu gráfico equivalente mínimo único e sua redução transitiva única e, portanto, não há benefício na redução transitiva ao uso de arestas que não estejam no original gráfico (há uma diferença entre gráfico mínimo equivalente e redução transitiva para alguns gráficos com ciclos, mas não para DAGs).

HTCS diz que existe um algoritmo para calcular um kernel irredutível de um gráfico acíclico direcionado em $O(V*e)$ tempo, onde $V$ é o número de vértices, e $e$ é o número de arestas no kernel irredutível, ou seja,o saída do algoritmo.A referência dada para isso é o seguinte artigo, para o qual ainda não consegui encontrar uma fonte on-line (links ou outras fontes são bem-vindos - posso perguntar em uma biblioteca de pesquisa em breve, se nada aparecer).

Noltemeier, H., "Redução de gráficos direcionados a núcleos irredutíveis", Documento de discussão 7505, Lehrstuhl f.Mathematische Verfahrensforschung u.Datenverarbeitung (Pesquisa Operacional e Processamento de Dados), Univ.Göttingen, Göttingen, 1975.

Alguém sabe o que é esse algoritmo?Surpreende-me um pouco que inclua o número de arestas no gráfico de saída, pois isso significaria que ele deveria ser executado em $O(n^2)$ tempo dado um gráfico de entrada com $O(n^2)$ arestas que representam uma ordem total, por ex.todos os nós recebem números inteiros de 1 até $n$, e há uma aresta do nó $i$ para $j$ se $i <j$.Isso não parece impossível, veja bem, simplesmente surpreendente.

[1] Aho, Garey e Ullman, "A redução transitiva de um gráfico direcionado", 1972 https://epubs.siam.org/doi/10.1137/0201008

Answer 1

Não conheço o algoritmo deles, mas o problema é fácil de resolver em $\mathcal{O}(V\cdot e)$ tempo.A ideia é apenas fazer um DFS de cada nó para encontrar vértices que possam alcançá-lo.Normalmente isso leva $\mathcal{O}(E)$ tempo, mas podemos usar o kernel irredutível que já construímos para fazer isso em $\mathcal{O}(e)$ tempo.

Primeiro observe que $e \geq n-1$ se o gráfico estiver conectado.Caso contrário, resolva os componentes conectados individualmente.

Comece fazendo a classificação topológica nos vértices, com os vértices com grau zero primeiro.Faça um loop dos vértices do primeiro ao último.Quando no vértice $i$, primeiro marque todos os vértices como inacessíveis.Em seguida, faça um loop nos vértices de $i-1$ para $1$.Em cada vértice $j$, se $j$ é inacessível e tem uma vantagem para $i$ no gráfico de entrada, adicione a aresta $(j, eu)$ para o kernel irredutível e marque $j$ alcançável.Então se $j$é alcançável, faça um loop em todas as arestas $(t, j)$ em nosso kernel e marque $t$ alcançável.

A classificação topológica leva $\mathcal{O}(V + E)$ tempo, e o DFS leva $\mathcal{O}(E + V \cdot e)$ tempo, então desde $e = \mathcal{\Omega}(V)$, o tempo de execução é $\mathcal{O}(V\cdot e)$.

O DAG produzido tem a mesma acessibilidade do gráfico original, pois usamos um subconjunto das arestas originais e apenas pulamos a adição da aresta $(j, eu)$ se $i$ é acessível a partir de $j$ mesmo sem isso.

Suponha alguma vantagem $(j, eu)$pode ser excluído enquanto mantém a acessibilidade.Mas a propósito, fizemos o DFS, $i$ não estava acessível de $j$sem aresta (observe que qualquer caminho entre eles só pode visitar vértices entre eles na ordem topológica).Conseqüentemente, o DAG produzido é de fato irredutível.