o（v * e）時間のDAGの既約カーネルを見つけるためのアルゴリズム。ここで、Eは出力のエッジ数

Question

既知のカーネルは、グラフアルゴリズムの章の「理論的コンピュータサイエンス（HTCS）、ボリュームの「アルゴリズムと複雑さ」で使用される用語です。有向グラフ $ g=（v、e）$ を考えると、refreduribleカーネルはグラフです $ g '=（v e '）$ ここで、 $ E' $ は、 $ e $ のサブセットです。そして、 $ G $ と $ g '$ と同じ到達可能性がある（つまり、それらの推移的な閉鎖は同じですこの条件、つまり $ e '$ から $ E $ に含まれていないエッジがあるため、同じではありません。述べた、[1]はDAGごとにそれが独自の最小同等のグラフである独自の既のカーネルとその独特の推移的な減少であることを証明しています。グラフ（最小同等のグラフとサイクルを備えたいくつかのグラフの推移的な縮小との間には違いがありますが、DAGの場合は違います）。

HTCSは、 $ o（v * e）$ 時刻、ここでの時刻を計算するためのアルゴリズムがあると言います。 "math-container"> $ v $ は頂点数、 $ E $ は、refredibleカーネルのエッジ数、つまり<アルゴリズムのEM>出力。このために与えられた参照は、まだ行われていません（リンクやその他の情報源は、何も起動しないとすぐに研究図書館で尋ねることができます）。

Noltemeier、H。、「既製カーネルへの有向グラフの還元」、ディスカッションペーパー7505、Lehrstuhl F。 Mathematische VerfahrensForschung u。 Datenverarbeitung（オペレーションズリサーチ＆データ処理）、大学。 Göttingen、Gottingen、1975年

誰かがこのアルゴリズムが何であるかを知っていますか？それはそれが出力グラフ内のエッジの数を含むことを少し驚かせます。 $ o（n ^ 2）$ の入力グラフ、合計順序を表すエッジすべてのノードには、1から $ n $ から整数が割り当てられ、ノード $ i $ $ j $ $ i 。それは不可能であるようではないように見えません、あなたを心に留めておく、単に驚くべきこと。

[1] Aho、Garey、Ullman、「有向グラフの推移的な削減」、1972 https://epubs.siam.org/doi/10.1137/0201008

Answer 1

私は彼らのアルゴリズムについて知らないが、問題は $ \ mathcal {o}（v \ cdot e）$ 時間で解決するのが簡単です。このアイデアは、到達できる頂点を見つけるためにすべてのノードからDFSを実行することです。通常、これは $ \ mathcal {o}（e）$ 時刻ですが、 $ \ mathcal {O}（e）$ 時間

最初に $ e \ geq n-1 $ に注意してください。そうでない場合は、接続されているコンポーネントを個別に解く。

頂点上のトポロジーソートを行うことから、最初に±ゼロの頂点を持ちます。最後にループ頂点。 vertex $ i $ で、最初にすべての頂点を到達不能にマークします。次に $ i-1 $ から $ 1 $ から頂点をループします。 vertex $ j $ で、 $ j $ が到達できない場合は $ i $ は、red $（j、i）$ をrefutibleカーネルとマーク $ j $ 到達可能です。その後、 $ j $ が到達可能である場合は、すべてのエッジ $（t、j）$ 、カーネルでループします。 $ t $ 到達可能な

トポロジのソートは $ \ mathcal {o}（v + e）$ 時間を受け取り、DFSは $を取ります。 \ mathcal {o}（E + V \ CDot e）$ 時刻以降、 $ E=Mathcal {\ omma}（v）$ 実行時間は $ \ mathcal {}（v \ cdot e）$ です。

生成されたDAGは、元のエッジのサブセットを使用し、Edge $（j、i）$の追加のみをスキップするため、元のグラフと同じ到達可能性があります。 SPAN> $ i $ の場合、 $ j $ から到達可能です。

到達可能性を維持しながら、エッジ $（j、i）$ を削除できます。しかし、DFSを作成したことによって、 $ i $ は $ j $ から到達できませんでした。 （それらの間の経路は、それらの間の頂点を位相順に訪問することができることに注意してください）。したがって、生成されたDAGは確かに既に難読化可能です。