Algoritmo per trovare un kernel irriducibile di un DAG in tempo O(V*e), dove e è il numero di archi in output

Question

Un kernel irriducibile è il termine usato nel Manuale di Informatica Teorica (HTCS), Volume A "Algorithms and Complexity" nel capitolo sugli algoritmi dei grafi.Dato un grafo orientato $G=(V,E)$, un kernel irriducibile è un grafo $G'=(V,E')$ Dove $E'$ è un sottoinsieme di $E$, ed entrambi $G$ E $G'$ hanno la stessa raggiungibilità (cioèle loro chiusure transitive sono le stesse) e rimuovendo qualsiasi bordo da $E'$ non soddisferebbe questa condizione, ad es. $E'$ è minima (anche se non necessariamente la dimensione minima possibile).

Un grafo equivalente minimo è simile, tranne che ha anche il minor numero di archi tra tutti questi grafi.Entrambi questi concetti sono simili a una riduzione transitiva, ma non uguali perché una riduzione transitiva può avere bordi che non sono in $E$.Detto questo, [1] dimostra che per ogni DAG ha un unico kernel irriducibile, che è anche il suo unico grafo equivalente minimo e la sua unica riduzione transitiva, e quindi non vi è alcun vantaggio nella riduzione transitiva all'utilizzo di archi non nell'originale grafico (c'è una differenza tra grafico equivalente minimo e riduzione transitiva per alcuni grafi con cicli, ma non per DAG).

HTCS afferma che esiste un algoritmo per calcolare un nucleo irriducibile di un grafo aciclico diretto $O(V*e)$ tempo, dove $V$ è il numero di vertici e $e$ è il numero di archi nel kernel irriducibile, cioèIL produzione dell'algoritmo.Il riferimento fornito per questo è il seguente articolo, per il quale non sono ancora riuscito a trovare una fonte in linea (link o altre fonti sono benvenuti - posso chiedere presto a una biblioteca di ricerca se non viene fuori nulla).

Noltemeier, H., "Riduzione dei grafi diretti a nuclei irriducibili", Documento di discussione 7505, Lehrstuhl f.Mathematische Verfahrensforschung u.Datenverarbeitung (Ricerca operativa ed elaborazione dati), Univ.Gottinga, Gottinga, 1975.

Qualcuno sa cos'è questo algoritmo?Mi sorprende un po' che includa il numero di archi nel grafico di output, poiché ciò significherebbe che dovrebbe essere eseguito $O(n^2)$ tempo dato un grafico di input con $O(n^2)$ bordi che rappresentano un ordine totale, ad es.a tutti i nodi vengono assegnati numeri interi da 1 fino a $n$, e c'è un bordo dal nodo $i$ A $j$ Se $i < j$.Ciò non sembra impossibile, sia chiaro, semplicemente sorprendente.

[1] Aho, Garey e Ullman, "La riduzione transitiva di un grafico diretto", 1972 https://epubs.siam.org/doi/10.1137/0201008

Answer 1

Non conosco il loro algoritmo, ma il problema è facile da risolvere $\mathcal{O}(V \cdot e)$ tempo.L'idea è semplicemente fare un DFS da ogni nodo per trovare i vertici che possono raggiungerlo.Normalmente questo richiede $\mathcal{O}(E)$ tempo, ma possiamo usare il kernel irriducibile che abbiamo già creato per farlo $\mathcal{O}(e)$ tempo.

Innanzitutto notalo $e \geq n-1$ se il grafico è connesso.In caso contrario, risolvere singolarmente i componenti collegati.

Inizia eseguendo l'ordinamento topologico sui vertici, iniziando prima dai vertici con grado zero.Vertici del ciclo dal primo all'ultimo.Quando al vertice $i$, contrassegnare innanzitutto tutti i vertici come irraggiungibili.Quindi esegui il ciclo dei vertici da $i-1$ A $1$.Ad ogni vertice $j$, Se $j$ è irraggiungibile e ha un vantaggio $i$ nel grafico di input, aggiungi il bordo $(j, i)$ al nocciolo irriducibile e al segno $j$ raggiungibile.Allora se $j$è raggiungibile, avvolgere tutti i bordi $(t, j)$ nel nostro kernel e mark $t$ raggiungibile.

L'ordinamento topologico richiede $\mathcal{O}(V + E)$ tempo e il DFS impiega $\mathcal{O}(E + V \cdot e)$ tempo, quindi da allora $e = \mathcal{\Omega}(V)$, il tempo di esecuzione è $\mathcal{O}(V \cdot e)$.

Il DAG prodotto ha la stessa raggiungibilità del grafico originale, poiché utilizziamo un sottoinsieme degli archi originali e saltiamo solo l'aggiunta dell'arco $(j, i)$ Se $i$ è raggiungibile da $j$ anche senza.

Assumi un certo vantaggio $(j, i)$può essere eliminato mantenendo la raggiungibilità.Ma comunque abbiamo realizzato il DFS, $i$ non era raggiungibile da $j$senza il bordo (nota che qualsiasi percorso tra loro può visitare solo i vertici tra loro nell'ordine topologico).Quindi il DAG prodotto è effettivamente irriducibile.