Algorithmus zum Finden eines irreduziblen Kernels einer DAG in O (v * E), wobei E Anzahl der Kanten in der Ausgabe ist

Question

Ein irreduzibierbarer Kernel ist der Begriff, der im Handbuch der theoretischen Informatik (HTCs), Volume A "Algorithmen und Komplexität" im Kapitel über Diagrammalgorithmen verwendet wird. Angesichts eines gerichteten Graphen $ g= (v, e) $ ist ein irreduzibierbarer Kernel ein Diagramm $ g '= (v , E ') $ wobei $ e' $ eine Teilmenge von $ E $ ist, und sowohl $ G $ und $ g '$ haben die gleiche Erreichbarkeit (dh ihre transitiven Verschlüsse sind gleich ), und das Entfernen einer Kante von $ E '$ würde diesen Zustand nicht erfüllen, dh $ E' $ ist minimal (obwohl nicht unbedingt die minimale Größe möglich ist).

Eine minimale äquivalente Grafik ist ähnlich, außer dass es auch die geringste Anzahl von Kanten zwischen allen derartigen Grafiken hat. Beide Konzepte sind ähnlich zu einer transitiven Reduktion, aber nicht dasselbe, weil eine transitive Reduktion Kanten aufweisen darf, die nicht in $ E $ sind. Das heißt, [1] beweist, dass es für jeden DAG einen einzigartigen irreduziblen Kernel hat, der auch sein einzigartiger Mindestgleichsgraph und seine einzigartige transitive Reduktion ist, und somit gibt es keinen Nutzen bei der transitiven Reduktion, um Kanten nicht im Original zu verwenden Graph (Es gibt einen Unterschied zwischen minimal äquivalenter Grafik und transitiven Reduktion für einige Grafiken mit Zyklen, jedoch nicht für DAGS).

htcs sagt, dass es ein Algorithmus gibt, um einen irreduziblen Kernel eines gerichteten azyklischen Diagramms in $ o (v * e) $ Time, wobei $ V $ ist die Anzahl der Scheitelpunkte und $ E $ ist die Anzahl der Kanten im irreduziblen Kernel, dh der < EM> Ausgang des Algorithmus. Die hier angegebene Referenz ist das folgende Papier, das ich noch nicht in der Lage bin, noch keine On-Line-Quelle zu finden (Links oder andere Quellen willkommen - ich kann bald in einer Forschungsbibliothek fragen, wenn nichts auftaucht).

Noltemeier, H., "Reduktion von gerichteten Diagrammen zu irreduziblen Kernels", Diskussionspapier 7505, Lehrstuhl f. Mathematische verbrahrensforschung u. Datenverarbeitung (Operations Research & Data-Verarbeitung), Univ. Göttingen, Göttingen, 1975.

weiß jemand, was dieser Algorithmus ist? Es überrascht mich ein wenig, dass es die Anzahl der Kanten in der Ausgabegrafik beinhaltet, da dies bedeuten würde, dass es in $ O (N ^ 2) $ Zeit ausgegeben wird Eingabediagramm mit $ O (N ^ 2) $ Kanten, die eine Gesamtbestellung darstellt, z Alle Knoten werden Ganzzahlen von 1 bis $ N $ zugewiesen, und es gibt eine Kante von Knoten $ i $ in $ J $ Wenn $ i . Das scheint nicht unmöglich, denken Sie, einfach überraschend.

[1] AHO, Garey und Ullman, "Die transitive Reduktion eines gerichteten Graphen", 1972 https://epubs.siam.org/doi/10.1137/0201008

Answer 1

Ich weiß nicht über ihren Algorithmus, aber das Problem ist einfach, in $ \ Mathcal {O} (v \ cdot e) $ Zeit zu lösen. Die Idee besteht darin, nur ein DFS von jedem Knoten zu tun, um Scheitelpunkte zu finden, die es erreichen können. Normalerweise nimmt dies $ \ Mathcal {O} (e) $ Zeit, aber wir können den irreduziblen Kernel verwenden, den wir bereits in $ \ mathcal {o} (e) $ Zeit.

Erster Hinweis darauf, dass $ e \ geq n-1 $ wenn der Graph angeschlossen ist. Wenn dies nicht der Fall ist, lösen Sie die angeschlossenen Komponenten einzeln.

Beginnen Sie mit topologischer Sortierung auf den Scheitelpunkten, mit Scheitelpunkten mit Indeye Null zuerst. Schleifenscheitelpunkte Erstletzt. Wenn bei Scheitelpunkt $ I $ , markieren Sie zunächst alle Scheitelpunkte als unerreichbar. Anschließend Schleifenscheitelpunkte von $ I-1 $ bis $ 1 $ . Bei jedem Vertex $ J $ , wenn $ J $ nicht erreichbar ist und eine Kante zu $ i $ In der Eingabediagramm, fügen Sie die Kante $ (j, i) $ in den irreduziblen Kernel und Markieren Sie $ J $ Erreichbar. Wenn dann $ J $ erreichbar ist, schleifen Sie alle Kanten $ (t, j) $ in unserem Kernel, und Mark $ T $ erreichbar.

Die topologische Sorte nimmt $ \ Mathcal {O} (V + E) $ Zeit, und die DFS nimmt $ \ mathcal {o} (e + v \ cdot e) $ Zeit, also seit $ e=mathcal {\ omega} (v) $ , Die Laufzeit ist $ \ Mathcal {O} (v \ cdot e) $ .

Der produzierte DAG hat die gleiche Erreichbarkeit wie das ursprüngliche Graph, da wir eine Teilmenge der ursprünglichen Kanten verwenden, und nur das Hinzufügen der Kante $ (j, i) $ Wenn $ i $ von $ J $ Auch ohne ihn erreichbar ist.

Nehmen Sie an, etwas Kanten $ (j, i) $ kann gelöscht werden, während er die Erreichbarkeit aufrechterhalten kann. Aber übrigens waren wir die DFS, $ I $ war nicht aus $ J $ ohne den Rand erreichbar (Beachten Sie, dass jeder Weg zwischen ihnen nur Scheitelpunkte zwischen ihnen in der topologischen Reihenfolge besuchen kann). Daher ist der produzierte Dag tatsächlich irreduzibel.