フィードバックアークセット

グラフ理論とグラフアルゴリズムにおいて、有向グラフのフィードバックアークセットまたはフィードバックエッジセットは、グラフのすべてのサイクルから少なくとも 1 つのエッジを含むグラフのエッジのサブセットです。これらのエッジをグラフから削除すると、すべてのサイクルが切断され、指定されたグラフの非巡回サブグラフが生成されます。これは、有向非巡回グラフと呼ばれることがよくあります。可能な限りエッジの少ないフィードバックアークセットは最小フィードバックアークセットであり、これを削除すると最大非巡回サブグラフが残ります。これらの最適化問題の重み付きバージョンも使用されます。フィードバックアークセットが最小である場合、つまり、エッジを削除すると、フィードバックアークセットではないサブセットが生成される場合、そのフィードバックアークセットには追加のプロパティがあります。つまり、すべてのエッジを削除するのではなく反転すると、有向非巡回グラフが生成されます。

フィードバック アーク セットは、回路解析、化学工学、デッドロックの解決、順位付け投票、スポーツ イベントの競技者の順位付け、数理心理学、動物行動学、グラフ描画に応用されています。最小フィードバック アーク セットと最大非巡回サブグラフを見つけることはNP 困難です。指数時間で正確に解くことも、固定パラメータの扱いやすい時間で解くこともできます。多項式時間では、最小フィードバック アーク セットは多重対数近似比内で近似でき、最大非巡回サブグラフは定数倍内で近似できます。どちらも、ある定数倍よりも近くに近似することは困難であり、この近似不可能性の結果は、ユニーク ゲーム予想によって強化されます。トーナメント グラフの場合、最小フィードバック アーク セットをより正確に近似でき、平面グラフの場合、両方の問題とも多項式時間で正確に解くことができます。

密接に関連する問題であるフィードバック頂点集合は、有向グラフまたは無向グラフの各サイクルから少なくとも 1 つの頂点を含む頂点の集合です。無向グラフでは、全域木が最大の非巡回サブグラフであり、全域木を形成する際に削除されるエッジの数は回路ランクです。

ランキングや順序付けに関するいくつかの問題は、トーナメント グラフ (各頂点のペアの間に 1 つのエッジがある有向グラフ) 上のフィードバック アーク セットを見つけることで解決できます。フィードバック アーク セットのエッジを反転すると、有向非巡回グラフが生成され、その固有の位相順序を目的のランキングとして使用できます。この方法の用途には、次のものがあります。

• 総当たり戦のスポーツ競技では、各試合の敗者から勝者へエッジを向けることで、各試合の結果を記録することができる。結果として得られるグラフで最小フィードバックアークセットを見つけ、そのエッジを反転し、位相順序付けすることで、すべての競技者のランキングが得られる。ランキングを選択するさまざまな方法の中で、これは番狂わせ、つまり下位ランクの競技者が上位ランクの競技者に勝つ試合の総数を最小化する。^{[2] [3] [4]多くのスポーツでは、}グループトーナメントのランキングシステムに、各試合に与えられるポイントに基づくより単純な方法を使用している。 ^[5]これらの方法は、番狂わせが最小のランキングに一定の近似値を提供できる。^[6]
• 霊長類学、そしてより一般的には動物行動学において、優位性の階層は、観察された優位性行動の逆転が最も少ない順序を探すことによって決定されることが多く、これは最小フィードバックアークセット問題の別の形である。^{[7] [8] [9]}
• 数理心理学では、被験者の好みや大きさの認識など、与えられた基準に従って、すべての物体のペア間の一対比較に基づいて物体セットの順位を決定することが興味深い。トーナメントグラフの最小フィードバックアークセットは、可能な限り少ないペアの結果と一致しない順位付けを提供する。^{[2] [10]}あるいは、これらの比較の結果、各ペアの順序付けに対して独立した確率が得られる場合、これらの確率を対数尤度に変換し、結果として得られるトーナメントで最小重みのフィードバックアークセットを見つけることで、全体の順位付けの最大尤度推定を得ることができる。 ^{[2] [3]}
• 同じ最大尤度順序付けは、統計学や探索的データ分析において、要素間の一対比較が可能なデータがある場合に、要素を線形順序に並べる問題である系列化にも使用できる。 ^{[3] [11] [12]}
• 順位付け投票において、ケメニー・ヤング法は、候補者のペアについて、そのペアに対して反対の順位付けを好む投票者の数の合計を最小にする順位付けを求める方法であると説明できます。^[13]これは、最小重みフィードバックアークセット問題として定式化して解くことができます。この問題では、頂点は候補者を表し、辺は各直接対決の勝者を表すように方向付けられ、各辺のコストは、直接対決で敗者に高い順位を与えることで不満を抱く投票者の数を表します。^[14]

フィードバックアークセットの別の初期の応用は、信号が常に入力から出力に進むのではなく、回路を循環的に伝搬できる順次論理回路の設計に関するものでした。このような回路では、最小フィードバックアークセットは、信号が情報の損失なしに伝搬できるようにするために増幅が必要なポイントの数を特徴付けます。 ^{[15]非同期コンポーネントで作成された}同期回路では、フィードバックアークセットのエッジにクロックゲートを配置することで同期を実現できます。^[16]さらに、フィードバックアークセットで回路を切断すると、残りの回路が組み合わせ論理に縮小されて分析が簡素化され、フィードバックアークセットのサイズによって、切断後の回路の動作を理解するために必要な追加分析の量が制御されます。^[15]同様に、化学工学のプロセスフローシートでは、プロセスフロー図のエッジをフィードバックアークセットで分割し、それらのエッジの値のすべての可能性を推測または試すと、その非循環性により、プロセスの残りの部分を体系的に分析できます。このアプリケーションでは、このようにエッジを分割するアイデアは「ティアリング」と呼ばれます。^[17]

階層化グラフ描画では、与えられた有向グラフの頂点が順序付けられた一連のサブセット（描画のレイヤー）に分割され、各サブセットはこの描画の水平線に沿って配置され、これらのレイヤー間でエッジが上下に伸びます。このタイプの描画では、描画の到達可能性関係が視覚的にわかりやすくなるように、上向きと下向きのエッジを混在させるのではなく、ほとんどまたはすべてのエッジが一貫して下向きになっていることが望ましいです。これは、最小または最小のフィードバックアークセットを見つけ、そのセット内のエッジを反転し、結果として得られる非巡回グラフの位相順序と一致する方法でレイヤーへの分割を選択することにより実現されます。^{[18] [19]}フィードバックアークセットは、レイヤーの連続ペア内の頂点の順序という、階層化グラフ描画の別のサブ問題にも使用されています。^[20]

オペレーティングシステムのデッドロック解決において、デッドロックを解消するために最小限の依存関係を削除する問題は、最小フィードバックアークセットを見つける問題としてモデル化できます。^{[21] [22]}ただし、このセットを見つける計算上の難しさと、オペレーティングシステムコンポーネント内での速度の必要性から、このアプリケーションでは正確なアルゴリズムではなくヒューリスティックがよく使用されます。^[22]

最小フィードバックアークセットと最大非巡回サブグラフは、一方が他方の補集合であるため、正確な最適化の目的においては同等である。しかし、パラメータ化された複雑性と近似に関しては、それらは異なる。なぜなら、これらの種類のアルゴリズムに使用される分析は、入力グラフのサイズだけでなくソリューションのサイズにも依存し、最小フィードバックアークセットと最大非巡回サブグラフのサイズは互いに異なるからである。^[23]

与えられたグラフのフィードバックアーク集合は、 の有向線グラフのフィードバック頂点集合と同じである。ここで、フィードバック頂点集合は、フィードバックアーク集合と同様に、グラフの頂点の部分集合として定義され、その部分集合を削除するとすべてのサイクルが除去される。有向グラフの線グラフには、 の各辺に対して頂点が 1 つ、 の各 2 辺パスに対して辺が 1 つある。逆に、与えられたグラフの最小フィードバック頂点集合は、の各頂点を 2 つの頂点に分割して得られるグラフ上の最小フィードバックアーク集合問題の解から得ることができる。2 つの頂点は入力辺用、もう 1 つは出力辺用である。これらの変換により、フィードバックアーク集合とフィードバック頂点集合の正確なアルゴリズムを、それらの複雑性境界を適切に変換して相互に変換することができる。ただし、この変換では、最大非巡回部分グラフ問題の近似品質は維持されない。^{[21] [24]}${\displaystyle G}$ ${\displaystyle G}$${\displaystyle G}$${\displaystyle G}$${\displaystyle G}$${\displaystyle G}$${\displaystyle G}$

フィードバックアークセット問題の正確な解法と近似解法の両方において、与えられたグラフのそれぞれの強く連結された成分を別々に解き、これらの強く連結された成分を連結頂点で分割してさらに二連結成分に分解すれば十分である。これらのサブ問題のいずれかにおける解の選択は他の問題には影響せず、これらの成分のいずれにも現れない辺はフィードバックアークセットに含めるのに役に立たない。^{[25]これらの成分の1つを2つの頂点を削除することで2つの切断されたサブグラフに分割できる場合、より複雑な分解が適用され、その強く連結された成分の}三連結成分から派生したサブ問題に問題を分割することができる。^[26]

最小フィードバックアーク集合を見つける方法の 1 つは、順序付けにおいて後ろの頂点から前の頂点に向かう辺ができるだけ少なくなるように頂点の順序付けを探すことです。^[27] -頂点グラフのすべての順列を検索するには時間がかかりますが、ヘルド・カープアルゴリズムに基づく動的計画法では、指数関数的な量の空間を使用して、時間で最適な順列を見つけることができます。 ^{[28] [29]頂点を 2 つの等しい部分集合に分割し、各部分集合内で再帰する}分割統治アルゴリズムでは、多項式空間を使用して、時間で問題を解決できます。^[29]${\displaystyle n}$${\displaystyle O(n!)}$${\displaystyle O(n2^{n})}$${\displaystyle O(4^{n}/{\sqrt {n}})}$

パラメータ化された複雑性では、アルゴリズムの時間は入力グラフのサイズだけでなく、グラフの別のパラメータによっても測定されます。特に、最小フィードバックアークセット問題の場合、いわゆる自然パラメータは最小フィードバックアークセットのサイズです。自然パラメータの頂点を持つグラフでは、フィードバックアークセット問題は、それを同等のフィードバック頂点セット問題に変換し、パラメータ化されたフィードバック頂点セットアルゴリズムを適用することで、時間で解決できます。このアルゴリズムの の指数はに依存せず定数であるため、このアルゴリズムは固定パラメータで扱いやすいと言われています。^[30 ]${\displaystyle n}$${\displaystyle k}$${\displaystyle O(n^{4}4^{k}k^{3}k!)}$${\displaystyle n}$${\displaystyle 4}$${\displaystyle k}$

自然パラメータ以外のパラメータも研究されている。動的計画法を用いた固定パラメータの扱いやすいアルゴリズムは、最小フィードバックアークセットを の時間で見つけることができる。${\displaystyle O(2^{r}m^{4}\log m)}$ここで、 は基礎となる無向グラフの回路ランクである。回路ランクは、フィードバックアークセットの無向類似物であり、接続されたグラフを全域木に縮小するためにグラフから削除する必要がある最小のエッジ数である。これは、最小フィードバックアークセットを計算するよりもはるかに簡単である。^[24]木幅のグラフの場合、グラフの木分解に対する動的計画法は、グラフサイズ の多項式時間および の指数時間で最小フィードバックアークセットを見つけることができます。指数時間仮説の下では、 へのより優れた依存性は不可能である。^[31]${\displaystyle r}$ ${\displaystyle t}$${\displaystyle O(t\log t)}$${\displaystyle t}$

フィードバックアークセットのサイズを最小化する代わりに、研究者は任意の頂点から削除されるエッジの最大数を最小化することにも着目しました。この問題のバリエーションは線形時間で解決できます。^{[32]すべての最小フィードバックアークセットは、セットごとに}多項式遅延を持つアルゴリズムによってリストできます。^[33]

フィードバックアークセットの最もよく知られている多項式時間近似アルゴリズムは、非定数近似比を持っています 。これは、それが見つけるフィードバックアークセットのサイズが、最適値よりも最大でこの係数だけ大きいことを意味します。^[21]フィードバックアークセットが定数比近似アルゴリズムを持っているかどうか、または非定数比が必要なのかどうかを判断することは、未解決の問題です。^[34]${\displaystyle O(\log n\log \log n)}$

最大非巡回部分グラフ問題には、次の近似比を達成する簡単な近似アルゴリズムがあります。${\displaystyle {\tfrac {1}{2}}}$

• 頂点の任意の順序を修正する
• エッジを 2 つの非巡回サブグラフに分割します。1 つは順序と一致する方向のエッジで構成され、もう 1 つは順序と反対の方向のエッジで構成されます。
• 2 つのサブグラフのうち大きい方を返します。

これは、貪欲アルゴリズムを使用して順序付けを選択することにより改善できます。このアルゴリズムは、入ってくるエッジの数と出ていくエッジの数が最も離れている頂点を見つけて削除し、残りのグラフを再帰的に順序付けしてから、削除した頂点を結果の順序の一方の端に配置します。エッジと頂点を持つグラフの場合、これは線形時間でエッジを持つ非巡回サブグラフを生成し、近似比は になります。^[35]もう1つのより複雑な多項式時間近似アルゴリズムは、最大次数 のグラフに適用され、エッジを持つ非巡回サブグラフを見つけて、形式の近似比を与えます。^{[36] [37]}のとき、近似比 を達成できます。^[38]${\displaystyle m}$${\displaystyle n}$${\displaystyle m/2+n/6}$${\displaystyle {\tfrac {1}{2}}+\オメガ (n/m)}$${\displaystyle \Delta }$${\displaystyle m/2+\Omega (m/{\sqrt {\Delta }})}$${\displaystyle {\tfrac {1}{2}}+\オメガ (1/{\sqrt {\Delta }})}$${\displaystyle \Delta =3}$${\displaystyle 8/9}$

有向平面グラフでは、フィードバック弧集合問題は、一組の辺（双対）を縮小して、結果として得られるグラフを強く連結する問題と双対である。^[39]この双対問題は多項式で解けるため、^[40] 平面最小フィードバック弧集合問題も多項式で解ける。[ ^{41] [40]これは}時間で解ける。^[42]問題の重み付きバージョンは時間で解ける。^[39]または重みが最大で数 の正の整数である場合は時間で解ける。^[42]これらの平面アルゴリズムは、これらのグラフの三連結成分が平面であるかサイズが制限されているという事実を利用して、ユーティリティグラフをグラフマイナーとして持たないグラフに拡張できる。 ^[26]平面グラフは、フィードバック弧集合に関連付けられた特定の多面体の整式性によって定義される、弱非巡回有向グラフと呼ばれる有向グラフのクラスにも異なる方法で一般化されている。この意味では、すべての平面有向グラフは弱非巡回であり、フィードバック弧集合問題はすべての弱非巡回有向グラフに対して多項式時間で解くことができる。^[43]${\displaystyle O(n^{5/2}\log n)}$${\displaystyle O(n^{3})}$${\displaystyle N}$${\displaystyle O(n^{5/2}\log nN)}$ ${\displaystyle K_{3,3}}$

還元可能フローグラフは、フィードバックアークセット問題を多項式時間で解くことができる有向グラフの別のクラスです。これらのグラフは、多くのプログラミング言語の構造化プログラムにおける制御の流れを記述します。構造化プログラムは平面の有向フローグラフを生成することがよくありますが、還元可能性の定義ではグラフが平面である必要はありません。^[44]

最小フィードバックアークセット問題がトーナメントに制限されている場合、多項式時間の近似スキームがあり、これは問題の重み付きバージョンに一般化されます。^[45]トーナメント上の重み付きフィードバックアークセットのサブ指数パラメータ化アルゴリズムも知られています。^[14]密なグラフの最大非巡回部分グラフ問題にも多項式時間の近似スキームがあります。その主なアイデアは、問題の線形計画緩和にランダム化された丸めを適用し、エクスパンダーグラフ上のウォークを使用して結果のアルゴリズムを非ランダム化することである。^{[34] [46]}

NP完全性の理論を最小フィードバックアークセットに適用するには、問題を最適化問題（すべてのサイクルを破るためにどれだけのエッジを削除できるか）から、yesまたはnoの回答（エッジを削除できるかどうか）を持つ同等の決定バージョンに変更する必要があります。したがって、フィードバックアークセット問題の決定バージョンは、有向グラフと数値の両方を入力として受け取ります。最大で 個のエッジを削除することですべてのサイクルを破ることができるかどうか、または同等に、少なくとも 個のエッジを持つ非循環サブグラフがあるかどうかを尋ねます。この問題はNP完全であり、この問題も最適化問題も多項式時間アルゴリズムを持つことが期待されないことを意味します。これは、リチャード・M・カープの21のNP完全問題の最初のセットの1つでした。そのNP完全性は、別の難しい問題である頂点カバー問題の入力が、フィードバックアークセット決定問題への同等の入力に変換（「縮小」）できることを示して、カープとユージン・ローラーによって証明されました。 ^{[47] [48]}${\displaystyle k}$${\displaystyle k}$${\displaystyle k}$${\displaystyle |E(G)|-k}$

いくつかのNP完全問題は、入力を特殊なケースに制限すると簡単になることがあります。しかし、フィードバックアークセット問題の最も重要な特殊なケースであるトーナメントの場合、問題はNP完全のままです。^{[49] [50]}

複雑性クラスAPX は、一定の近似比 を達成する多項式時間近似アルゴリズムを持つ最適化問題で構成されると定義される。フィードバックアークセット問題に対するそのような近似は知られていないが、この問題はAPX 困難であることが知られている。つまり、この問題の正確な近似を使用して、APX の他のすべての問題に対して同様に正確な近似を達成できる。困難性の証明の結果として、P = NPでない限り、1.3606 より優れた多項式時間近似比はない。これは、頂点カバーに対して知られている近似の困難性のしきい値と同じであり、証明では、近似の品質を維持する、頂点カバーからフィードバックアークセットへのKarp–Lawler還元を使用している。 ^{[34] [51] [52] [53]}別の還元により、最大非巡回サブグラフ問題も APX 困難であり、最適値の 65/66 倍以内に近似することは NP 困難である。^[38]

これらの問題の近似の困難さは、計算複雑性理論では標準的だが P ≠ NP より強い、証明されていない計算困難性の仮定の下でも研究されてきた。ユニークゲーム予想が正しい場合、任意のに対して、最小フィードバックアークセット問題を任意の定数倍以内に多項式時間で近似することは困難であり、最大フィードバックアークセット問題をの倍数以内に近似することは困難である${\displaystyle {\tfrac {1}{2}}+\varepsilon }$。^[54]近似アルゴリズムの多項式時間を超えて、指数時間仮説が正しい場合、任意${\displaystyle \epsilon >0}$の に対して、最小フィードバックアークセットには、指数時間未満の範囲 で計算できる倍数以内の近似が存在しない。^[55]${\displaystyle \epsilon >0}$${\displaystyle {\tfrac {7}{6}}-\varepsilon }$${\displaystyle O(2^{n^{1-\varepsilon }})}$

平面有向グラフでは、フィードバックアークセット問題は最小最大定理に従います。つまり、フィードバックアークセットの最小サイズは、グラフ内で見つかる辺が互いに素な有向サイクルの最大数に等しくなります。^{[41] [56]}これは他のグラフには当てはまりません。たとえば、最初の図は、フィードバックアークセットの最小サイズが2であるのに対し、辺が互いに素な有向サイクルの最大数は1つだけである、非平面グラフの有向バージョンを示しています。 ${\displaystyle K_{3,3}}$

すべてのトーナメント グラフにはハミルトン パスがあり、ハミルトン パスは、対応するパスとは互いに素な最小フィードバック アーク セットと 1 対 1 で対応します。フィードバック アーク セットのハミルトン パスは、そのアークを反転し、結果として得られる非巡回トーナメントの位相順序を見つけることで見つかります。順序のすべての連続するペアは、フィードバック アーク セットと互いに素でなければなりません。そうでないと、そのペアを反転することで、より小さなフィードバック アーク セットを見つけることができるためです。したがって、この順序付けにより、元のトーナメントのアークを通るパスが得られ、すべての頂点がカバーされます。逆に、どのハミルトン パスからでも、パス内の後の頂点を前の頂点に接続するエッジの集合は、フィードバック アーク セットを形成します。フィードバック アーク セットが最小であるのは、その各エッジが、他のすべてのそのようなサイクルとは互いに素なハミルトン パス エッジを持つサイクルに属しているためです。^[57]トーナメントでは、最小フィードバック アーク セットと最大非巡回サブグラフの両方がエッジの半分に近い場合があります。より正確には、すべてのトーナメントグラフにはサイズ のフィードバックアークセットがあり、一部のトーナメントではサイズ が必要です。^[58]ほとんどすべてのトーナメントでは、サイズは少なくとも です。^[59]すべての有向非巡回グラフは、 がトーナメントの唯一の最小フィードバックアークセットであるような方法で、より大きなトーナメントグラフのサブグラフとして埋め込むことができます。このトーナメントのサイズはの「反転数」として定義されており、同じ頂点数の有向非巡回グラフの中で が（非巡回）トーナメントであるときに最大になります。^{[60] [61]}${\displaystyle {\tbinom {n}{2}}/2-\Omega (n^{3/2})}$${\displaystyle {\tbinom {n}{2}}/2-O(n^{3/2})}$${\displaystyle {\tbinom {n}{2}}/2-1.73n^{3/2}}$ ${\displaystyle D}$${\displaystyle D}$${\displaystyle D}$${\displaystyle D}$

有向グラフは、強く連結されていて、各頂点の入力エッジと出力エッジの数が等しい場合は常にオイラー巡回を持ちます。エッジと頂点を持つこのようなグラフでは、最小フィードバックアークセットのサイズは常に 個以上です。この境界が厳密なオイラー有向グラフは無限に存在します。^[62]有向グラフに頂点があり、頂点ごとに最大 3 つのエッジがある場合、最大 個のエッジのフィードバックアークセットを持ち、一部のグラフではこの数が必要です。有向グラフにエッジがあり、頂点ごとに最大 4 つのエッジがある場合、最大 個のエッジのフィードバックアークセットを持ち、一部のグラフではこの数が必要です。^[63]${\displaystyle m}$${\displaystyle n}$${\displaystyle (m^{2}+mn)/2n^{2}}$${\displaystyle n}$${\displaystyle n/3}$${\displaystyle m}$${\displaystyle m/3}$