有向グラフ実現問題

有向グラフ実現問題は、グラフ理論における決定問題です。この問題は、非負の整数のペアが与えられたときに、各頂点が入次数と出次数を持つようなラベル付き単純有向グラフが存在するかどうかを問うものです。 ${\displaystyle ((a_{1},b_{1}),\ldots ,(a_{n},b_{n}))}$ ${\displaystyle v_{i}}$ ${\displaystyle a_{i}}$ ${\displaystyle b_{i}}$

この問題は複雑性クラスPに属します。これを証明するためのアルゴリズムは 2 つ知られています。最初のアプローチは、再帰アルゴリズムを使用して特別なソリューションを構築するKleitman-Wang アルゴリズムによって与えられます。2 つ目はFulkerson-Chen-Anstee 定理による特徴付けであり、不等式の正しさを検証する必要があります。 ${\displaystyle n}$

この問題は、0-1行列で表現することもできます。各有向グラフには、列の合計と行の合計がおよびに対応する隣接行列があることに気づけば、その関連性がわかります。行列の対角線にはゼロのみが含まれることに注意してください。この場合、問題は、行の合計と列の合計が与えられた場合の 0-1 行列で表すことがよくあります。古典的な文献では、この問題は分割表のコンテキストで、与えられた周辺 を持つ分割表で表現されることがありました。 ${\displaystyle (a_{1},\cdots ,a_{n})}$${\displaystyle (b_{1},\ldots ,b_{n})}$

同様の問題として、単純グラフ、ループ付きの単純有向グラフ、単純二部グラフの次数列が記述されます。最初の問題は、いわゆるグラフ実現問題です。2番目と3番目の問題は同等であり、二部実現問題として知られています。Chen (1966) は、与えられた次数列に対する、限られた数の平行アークとループを持つ有向マルチグラフの特徴付けを与えています。有向グラフの非巡回性という追加の制約は、dag実現として知られています。Nichterlein & Hartung (2012) は、この問題のNP 完全性を証明しました。Berger & Müller-Hannemann (2011) は、反対のシーケンスのクラスがPに含まれることを示しました。有向グラフを固定次数列に均一サンプリングする問題は、各ソリューションが同じ確率で来るという追加の制約を付けて、有向グラフ実現問題のソリューションを構築することです。この問題は、 Catherine Greenhill (2011)によって正規のシーケンスのFPTASで示されましたが、 一般的な問題はまだ解決されていません。

• 陳偉凱（1966）「規定次数を持つ（p、s）有向グラフの実現について」フランクリン研究所誌、103：406-422
• ニヒテルライン、アンドレ; ハルトゥング、セップ (2012)、「有向非巡回グラフによる次数列の実現の NP 困難性と固定パラメータの扱いやすさ」、フランクリン研究所ジャーナル、7318 : 283– 292
• Berger, Annabell; Müller-Hannemann, Matthias (2011)、「有向次数列の Dag 実現」、第 18 回計算理論基礎国際会議の議事録: 264– 275
• グリーンヒル、キャサリン（2011）、「正規有向グラフをサンプリングするためのマルコフ連鎖の混合時間の多項式境界」、電子ジャーナルオブコンビナトリクス、18