フィードバックアークセット
良い記事ですね。詳しくはこちらをクリックしてください。

有向グラフを最小フィードバックアークセット（赤い破線）と最大非巡回サブグラフ（青い実線）に分割する

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

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

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

アプリケーション

2016年オリンピック男子ビーチバレーボール（プールF）のスコアと、これらのスコアにおける最小番狂わせランキング。矢印は各試合の敗者から勝者へと向けられており、結果がランキングと一致する場合は青、順位と一致しない番狂わせの場合は赤で表示されている。このランキングでは、アメリカがQATを破った試合のみが番狂わせとなった。オリンピックで実際に使用されたランキングは異なり、セット比率でESPがQATを上回ったため、この試合は別の番狂わせとしてランク付けされた。[ 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 ]

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

3つの強連結成分を持つ有向グラフ。右端の成分は、連結頂点において2つの二連結成分に分割でき、それぞれが2つの頂点からなる閉路となる。フィードバック弧集合問題は、各強連結成分ごとに、また強連結成分の各二連結成分ごとに個別に解くことができる。d{\displaystyle d}

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

ちょうど

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

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

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

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

近似

数学における未解決問題
フィードバックアークセット問題には、近似比が一定の近似アルゴリズムがありますか?
数学におけるさらなる未解決問題

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

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

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

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

制限された入力

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

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

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

硬度

NP困難性

KarpとLawlerによるNP完全性縮約は、大きな黄色のグラフの頂点被覆から小さな青色のグラフの最小フィードバック弧集合へと展開され、黄色の各頂点を隣接する2つの青色のグラフ頂点に、黄色の各無向辺を2つの反対向きの有向辺に拡張します。最小頂点被覆（左上と右下の黄色の頂点）は、赤色の最小フィードバック弧集合に対応します。

NP完全性の理論を最小フィードバックアーク集合に適用するには、問題を最適化問題（すべてのサイクルを破るためにどれだけのエッジを削除できるか）から、yesまたはnoで答えられる同等の決定バージョン（エッジを削除できるかどうか）へと修正する必要があります。したがって、フィードバックアーク集合問題の決定バージョンは、有向グラフと数値の両方を入力として受け取ります。これは、最大で 個のエッジを削除することですべてのサイクルを破ることができるかどうか、あるいは同値として、少なくとも 個のエッジを持つ非巡回サブグラフが存在するかどうかを問うものです。この問題はNP完全であり、この問題も最適化問題も多項式時間アルゴリズムを持つことは期待されません。これは、リチャード・M・カープが最初に提示した21個のNP完全問題のうちの1つでした。そのNP完全性は、カープとユージン・ローラーによって、別の難問である頂点被覆問題の入力が、フィードバックアーク集合決定問題への同等の入力に変換（「縮約」）できることを示して証明されました。[ 47 ] [ 48 ]け{\displaystyle k}け{\displaystyle k}け{\displaystyle k}|E（G）|−け{\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よりも強い、証明されていない計算困難性の仮定の下でも研究されてきた。ユニークゲーム予想が正しいとすれば、任意の に対して、最小フィードバックアークセット問題は多項式時間で任意の定数倍以内に近似することが困難であり、最大フィードバックアークセット問題は の倍数以内に近似することが困難である。12+ε{\displaystyle {\tfrac {1}{2}}+\varepsilon }[ 54 ]近似アルゴリズムの多項式時間を超えて、指数時間仮説が正しいとすれば、任意の に対して、最小フィードバックアークセットには指数時間境界 で計算できる倍数以内の近似が存在しない。[ 55 ]ε>0{\displaystyle \varepsilon >0}ε>0{\displaystyle \varepsilon >0}76−ε{\displaystyle {\tfrac {7}{6}}-\varepsilon }お（2n1−ε）{\displaystyle O(2^{n^{1-\varepsilon }})}

理論

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

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

有向グラフは、強く連結されていて、各頂点に出入りする辺の数が等しいときはいつでもオイラー巡回を持つ。そのようなグラフ（辺と頂点を持つ）では、最小フィードバックアークセットのサイズは常に少なくとも である。この境界が厳密なオイラー有向グラフは無限に多い。[ 62 ]有向グラフに頂点があり、頂点ごとに最大 3 辺がある場合、最大辺のフィードバックアークセットを持ち、グラフによってはこの数を必要とする。有向グラフに辺があり、頂点ごとに最大 4 辺がある場合、最大 辺のフィードバックアークセットを持ち、グラフによってはこの数を必要とする。[ 63 ]m{\displaystyle m}n{\displaystyle n}(m2+mn)/2n2{\displaystyle (m^{2}+mn)/2n^{2}}n{\displaystyle n}n/3{\displaystyle n/3}m{\displaystyle m}m/3{\displaystyle m/3}

参考文献

  1. ^ "Main draw – Men"、リオ2016、国際バレーボール連盟、2016年12月23日時点のオリジナルよりアーカイブ、 2021年11月14日閲覧。
  2. ^ a b cヒューバート、ローレンス（1976）、「非対称近接尺度を用いた系列化」、英国数学統計心理学誌、29（1）：32–52、doi：10.1111/j.2044-8317.1976.tb00701.x、MR 0429180 
  3. ^ a b c Remage, Russell Jr.; Thompson, WA Jr. (1966)、「最大尤度対比較ランキング」、Biometrika、53 ( 1– 2): 143– 149、doi : 10.1093/biomet/53.1-2.143、JSTOR 2334060、MR 0196854、PMID 5964054   
  4. ^ゴダード、スティーブン・T.（1983）、「トーナメントでのランキングと集団意思決定」、マネジメントサイエンス、29（12）：1384–139 ​​2、doi：10.1287/mnsc.29.12.1384、MR 0809110 ; ゴダードが提案した最小違反ランキングを見つけるためのアルゴリズムは間違っていることに注意してください
  5. ^ Vaziri, Baback; Dabadghao, Shaunak; Yih, Yuehwern ; Morin, Thomas L. (2018年1月) 「スポーツランキング手法の特性」(PDF) , Journal of the Operational Research Society , 69 (5): 776– 787, doi : 10.1057/s41274-017-0266-8 , S2CID 51887586 
  6. ^ Coppersmith, Don ; Fleischer, Lisa K.; Rurda, Atri (2010) 「重み付けされた勝利数による順序付けは、重み付けされたトーナメントの適切なランキングを与える」ACM Transactions on Algorithms、6 (3): A55:1–A55:13、doi : 10.1145/1798596.1798608、MR 2682624、S2CID 18416  
  7. ^ Seyfarth, Robert M. (1976年11月)、「成獣雌ヒヒ間の社会的関係」、Animal Behaviour、24 (4): 917–938、doi : 10.1016/s0003-3472(76)80022-x、S2CID 54284406 
  8. ^ Estep, DQ; Crowell-Davis, SL; Earl-Costello, S.-A.; Beatey, SA (1993年1月)「分娩期におけるドラフトホース（Equus caballus）牝馬の社会行動の変化」『応用動物行動科学』35 (3): 199– 213, doi : 10.1016/0168-1591(93)90137-e
  9. ^ Eickwort, George C. (2019年4月)、「ゴキブリ（ナウフォエタ）における優位性」、昆虫行動、CRC Press、pp.  120– 126、doi : 10.1201/9780429049262-18、ISBN 978-0-429-04926-2、S2CID  203898549
  10. ^スレーター、パトリック（1961）、「一対比較のスケジュールにおける不一致」、バイオメトリカ、48（3-4）：303-312、doi：10.1093/biomet/48.3-4.303、JSTOR 2332752 
  11. ^ Brunk, HD (1960)、「一対比較によるランキングの数学的モデル」、アメリカ統計学会誌、55 (291): 503– 520、doi : 10.2307/2281911、JSTOR 2281911、MR 0115242  ; ASTIA文書番号AD 206 573、米国空軍科学研究局、1958年11月、HDL：2027/mdp.39015095254010として暫定的に公開
  12. ^ Thompson, WA Jr.; Remage, Russell Jr. (1964)、「一対比較によるランキング」、Annals of Mathematical Statistics、35 (2): 739– 747、doi : 10.1214/aoms/1177703572、JSTOR 2238526、MR 0161419  
  13. ^ケメニー、ジョン・G.（1959年秋）「数のない数学」、ダイダロス、88（4）：577–591、JSTOR 20026529 
  14. ^ a b Karpinski, Marek ; Schudy, Warren (2010)、「フィードバックアークセットトーナメント、ケメニーランク集約、媒介性トーナメントのための高速アルゴリズム」、Cheong, Otfried ; Chwa, Kyung-Yong ; Park, Kunsoo (編)、アルゴリズムと計算 - 第21回国際シンポジウム、ISAAC 2010、済州島、韓国、2010年12月15日～17日、議事録、パートI、Lecture Notes in Computer Science、vol. 6506、Springer、pp.  3～ 14、arXiv : 1006.4396、doi : 10.1007/978-3-642-17517-6_3、ISBN 978-3-642-17516-9、S2CID  16512997
  15. ^ a b Unger, Stephen H. (1957年4月26日)、「非同期論理フィードバックネットワークの研究」、技術レポート、第320巻、マサチューセッツ工科大学、電子工学研究所、hdl : 1721.1/4763
  16. ^ Feehrer, John R.; Jordan, Harry F. (1995年12月)、「飛行時間型光電子回路におけるクロックゲートの配置」、Applied Optics、34 (35): 8125– 8136、Bibcode : 1995ApOpt..34.8125F、doi : 10.1364/ao.34.008125、PMID 21068927 
  17. ^ Rosen, Edward M.; Henley, Ernest J. (1968年夏)、「The New Stoichiometry」、Chemical Engineering Education、2 (3): 120– 125、2021年8月2日時点のオリジナルよりアーカイブ、 2021年8月2日取得
  18. ^ディ・バッティスタ、ジュゼッペ;イーデス、ピーター;タマシア、ロベルト; トリス、イオアニス G. (1998)、「有向グラフの階層的描画」、グラフ描画：グラフの視覚化アルゴリズム、プレンティス・ホール、pp.  265– 302、ISBN 978-0-13-301615-4
  19. ^ Bastert, Oliver; Matuszewski, Christian (2001)、「Layered drawing of digraphs」、Kaufmann, Michael; Wagner, Dorothea (eds.)、『Drawing Graphs: Methods and Models』、Lecture Notes in Computer Science、vol. 2025、Springer-Verlag、pp.  87– 120、doi : 10.1007/3-540-44969-8_5、ISBN 978-3-540-42062-0
  20. ^ Demetrescu, Camil; Finocchi, Irene (2001)、「正しい」サイクルを破り、「最良の」描画を得る」、ACM Journal of Experimental Algorithmics、6 : 171–182、MR 2027115 
  21. ^ a b c Even, G.; Naor, J .; Schieber, B .; Sudan, M. (1998)「有向グラフにおける最小フィードバックセットとマルチカットの近似」、Algorithmica、20 (2): 151– 174、doi : 10.1007/PL00009191、MR 1484534、S2CID 2437790  
  22. ^ a bミノウラ・トシミ (1982)、「デッドロック回避の再考」、Journal of the ACM、29 (4): 1023– 1048、doi : 10.1145/322344.322351、MR 0674256、S2CID 5284738  
  23. ^ Mishra, Sounaka; Sikdar, Kripasindhu (2004)、「グラフ上の線形順序付けと関連するNP最適化問題の近似可能性について」、Discrete Applied Mathematics、136 ( 2–3 ): 249– 269、doi : 10.1016/S0166-218X(03)00444-X、MR 2045215 
  24. ^ a b Hecht, Michael (2017)、「フィードバックセットの正確な局所化」、Theory of Computing Systems、62 (5): 1048– 1084、arXiv : 1702.07612、doi : 10.1007/s00224-017-9777-6、S2CID 18394348 
  25. ^ Park, S.; Akers, SB (1992)、「有向グラフにおける最小フィードバックアーク集合を見つけるための効率的な方法」、1992 IEEE国際回路・システムシンポジウム (ISCAS '92) の議事録、第4巻、pp.  1863– 1866、doi : 10.1109/iscas.1992.230449、ISBN 0-7803-0593-0、S2CID  122603659
  26. ^ a b Nutov, Zeev; Penn, Michal (2000)、「二環式パッキングとカバーの積分性、安定性、および構成について」、Journal of Combinatorial Optimization、4 (2): 235– 251、doi : 10.1023/A:1009802905533、MR 1772828、S2CID 207632524  
  27. ^ Younger, D. (1963)、「有向グラフの最小フィードバックアーク集合」、IEEE Transactions on Circuit Theory、10 (2): 238– 245、doi : 10.1109/tct.1963.1082116
  28. ^ Lawler, E. (1964)、「最小フィードバックアーク集合に関するコメント」、IEEE Transactions on Circuit Theory、11 (2): 296– 297、doi : 10.1109/tct.1964.1082291
  29. ^ a b Bodlaender, Hans L. ; Fomin, Fedor V.; Koster, Arie MCA; Kratsch, Dieter; Thilikos, Dimitrios M. (2012)「グラフ上の頂点順序付け問題に対する正確なアルゴリズムに関する注記」Theory of Computing Systems , 50 (3): 420– 432, doi : 10.1007/s00224-011-9312-0 , hdl : 1956/4556 , MR 2885638 , S2CID 9967521  
  30. ^ Chen, Jianer; Liu, Yang; Lu, Songjian; O'Sullivan, Barry; Razgon, Igor (2008)、「有向フィードバック頂点集合問題のための固定パラメータアルゴリズム」、Journal of the ACM、55 (5): 1– 19、doi : 10.1145/1411509.1411511、S2CID 1547510 
  31. ^ Bonamy, Marthe; Kowalik, Lukasz; Nederlof, Jesper; Pilipczuk, Michal; Socala, Arkadiusz; Wrochna, Marcin (2018)、「On directed feedback vertex set parameterized by treewidth」、Brandstädt, Andreas; Köhler, Ekkehard; Meer, Klaus (eds.)、『Graph-Theoretic Concepts in Computer Science - 44th International Workshop, WG 2018』、コトブス、ドイツ、2018 年 6 月 27 ～ 29 日、議事録、Lecture Notes in Computer Science、vol. 11159、シュプリンガー、pp.  65– 78、arXiv : 1707.01470、doi : 10.1007/978-3-030-00256-5_6、ISBN 978-3-030-00255-8、S2CID  8008855
  32. ^ Lin, Lishin; Sahni, Sartaj (1989)、「公平なエッジ削除問題」、IEEE Transactions on Computers、38 (5): 756– 761、doi : 10.1109/12.24280、MR 0994519 
  33. ^ Schwikowski, Benno; Speckenmeyer, Ewald (2002)、「フィードバック問題のすべての最小解の列挙について」、離散応用数学、117 ( 1–3 ): 253– 265、doi : 10.1016/S0166-218X(00)00339-5、MR 1881280 
  34. ^ a b cクレッシェンツィ、ピエルルイジ;カン、ヴィゴ。ハルドルソン、マグナス。Karpinski, マレク; Woeginger, Gerhard (2000)、「Minimum Feedback Arc Set」、NP 最適化問題の概要、オリジナルから 2021-07-29 にアーカイブ、2021-07-29 に取得
  35. ^ Eades, Peter ; Lin, Xuemin; Smyth, WF (1993)、「フィードバックアークセット問題に対する高速かつ効果的なヒューリスティック」、Information Processing Letters、47 (6): 319– 323、doi : 10.1016/0020-0190(93)90079-O、MR 1256786、2020年10月22日時点のオリジナルよりアーカイブ、 2021年8月1日取得 
  36. ^ Berger, Bonnie ; Shor, Peter W. (1997)、「最大非巡回部分グラフ問題の厳密な境界」、Journal of Algorithms、25 (1): 1– 18、doi : 10.1006/jagm.1997.0864、MR 1474592 
  37. ^ Hassin, Refael; Rubinstein, Shlomi (1994)、「最大非巡回部分グラフ問題の近似値」、Information Processing Letters、51 (3): 133– 140、doi : 10.1016/0020-0190(94)00086-7、MR 1290207 
  38. ^ a bニューマン、アランサ（2000年6月）、最大非巡回部分グラフの近似（修士論文）、マサチューセッツ工科大学、hdl：1721.1/86548Guruswami et al. (2011)による引用
  39. ^ a b Gabow, Harold N. (1995)、「重心、表現、およびサブモジュラーフロー」、Journal of Algorithms、18 (3): 586– 628、doi : 10.1006/jagm.1995.1022、MR 1334365 
  40. ^ a b Frank, András (1981)、「強く連結された有向グラフの作り方」、Combinatorica、1 (2): 145– 153、doi : 10.1007/BF02579270、MR 0625547、S2CID 27825518  
  41. ^ a b Lucchesi, CL; Younger, DH (1978)、「有向グラフのミニマックス定理」、ロンドン数学会誌、第2シリーズ、17 (3): 369– 374、doi : 10.1112/jlms/s2-17.3.369、MR 0500618 
  42. ^ a b Gabow, Harold N. (1993)、「サブモジュラーフロー問題のためのコストスケーリングアルゴリズムのフレームワーク」、第34回コンピュータサイエンスの基礎に関する年次シンポジウム、パロアルト、カリフォルニア州、米国、1993年11月3-5日、IEEEコンピュータ協会、pp.  449– 458、doi : 10.1109/SFCS.1993.366842、ISBN 0-8186-4370-6、MR  1328441、S2CID  32162097
  43. ^ Grötschel, Martin ; Jünger, Michael ; Reinelt, Gerhard (1985)、「非巡回部分グラフ多面体について」、数学プログラミング、33 (1): 28– 42、doi : 10.1007/BF01582009、MR 0809747、S2CID 206798683  
  44. ^ラマチャンドラン、ヴィジャヤ（1988）、「可約フローグラフにおける最小フィードバックアーク集合の探索」、アルゴリズムジャーナル、9（3）：299–313、doi：10.1016/0196-6774（88）90022-3、MR 0955140 
  45. ^ Kenyon-Mathieu, Claire ; Schudy, Warren (2007)、「少ないエラーで順位付けする方法：トーナメントに基づく重み付けフィードバックアークセットのためのPTAS」、Johnson, David S. ; Feige, Uriel (編)、第39回ACMコンピューティング理論シンポジウム論文集、サンディエゴ、カリフォルニア州、米国、2007年6月11日～13日、pp.  95～ 103、doi : 10.1145/1250790.1250806、S2CID 9436948、ECCC TR06-144  ;著者の拡張版 も参照。2009年1月15日アーカイブ、 Wayback Machine
  46. ^ Arora, Sanjeev ; Frieze, Alan ; Kaplan, Haim (2002)、「割り当て問題のための新しい丸め手順と稠密グラフ配置問題への応用」、数学プログラミング、92 (1): 1– 36、doi : 10.1007/s101070100271、MR 1892295、S2CID 3207086、2021年8月3日にオリジナルからアーカイブ、 2021年8月3日取得  
  47. ^ Karp, Richard M. (1972)、「組合せ問題における縮約可能性」、Complexity of Computer Computations、Proc. Sympos. IBM Thomas J. Watson Res. Center, Yorktown Heights, NY, New York: Plenum、pp.  85– 103
  48. ^ガリー、マイケル・R. ;ジョンソン、デビッド・S. (1979)、「A1.1: GT8」、コンピュータとイントラクタビリティ：NP完全性理論へのガイド、WHフリーマン、p. 192、ISBN 0-7167-1045-5
  49. ^ Alon, Noga (2006)、「ランキングトーナメント」、SIAM Journal on Discrete Mathematics、20 (1): 137– 142、doi : 10.1137/050623905、MR 2257251 
  50. ^ Charbit, Pierre; Thomassé, Stéphan; Yeo, Anders (2007)、「最小フィードバックアークセット問題はトーナメントに対してNP困難である」(PDF)、Combinatorics, Probability and Computing、16 (1): 1– 4、doi : 10.1017/S0963548306007887、MR 2282830、S2CID 36539840  
  51. ^ Ausiello, G. ; D'Atri, A.; Protasi, M. (1980)、「凸最適化問題における構造保存縮約」、Journal of Computer and System Sciences、21 (1): 136– 153、doi : 10.1016/0022-0000(80)90046-X、MR 0589808 
  52. ^ Kann, Viggo (1992), On the approximability of NP-complete Optimization Problems (PDF) (Ph.D. thesis), Department of Numerical Analysis and Computing Science, Royal Institute of Technology, Stockholm, archived (PDF) from the original on 2010-12-29 , retrieved 2007-10-11
  53. ^ Dinur, Irit ; Safra, Samuel (2005)、「最小頂点被覆近似の困難性について」(PDF)、Annals of Mathematics、162 (1): 439– 485、doi : 10.4007/annals.2005.162.439、2009年9月20日にオリジナルからアーカイブ(PDF) 、 2021年7月29日取得; 予備版はDinur, Irit ; Safra, Samuel (2002)「バイアスを持つことの重要性」、Reif, John H. (ed.)、Proceedings of the 34th Annual ACM Symposium on Theory of Computing、2002年5月19日～21日、モントリオール、ケベック、カナダ、pp.  33～ 42、doi : 10.1145/509907.509915、ISBN 1-58113-495-9、S2CID  1235048
  54. ^ Guruswami, Venkatesan ; Håstad, Johan ; Manokaran, Rajsekar ; Raghavendra, Prasad ; Charikar, Moses (2011)、「ランダム順序付けを打ち破ることは難しい：すべての順序付けCSPは近似耐性がある」（PDF）、SIAM Journal on Computing、40（3）：878– 914、doi：10.1137/090756144、MR 2823511、2021年7月31日にオリジナルからアーカイブ（PDF） 、 2021年7月31日取得 
  55. ^ Bonnet, Édouard; Paschos, Vangelis Th. (2018)、「スパース化と準指数近似」、Acta Informatica、55 (1): 1– 15、arXiv : 1402.2843、doi : 10.1007/s00236-016-0281-2、MR 3757549、S2CID 3136275  
  56. ^ Lovász, László (1976)、「グラフにおける2つのミニマックス定理について」、Journal of Combinatorial Theory、シリーズB、21 (2): 96– 103、doi : 10.1016/0095-8956(76)90049-6、MR 0427138 
  57. ^ Bar-Noy, Amotz; Naor, Joseph (1990)、「トーナメントにおけるソート、最小フィードバックセット、ハミルトンパス」、SIAM Journal on Discrete Mathematics、3 (1): 7– 20、doi : 10.1137/0403002、MR 1033709 
  58. ^ Spencer, J. (1980)、「ランク付け不可能なトーナメントの最適ランク付け」、Periodica Mathematica Hungarica、11 (2): 131– 144、doi : 10.1007/BF02017965、MR 0573525、S2CID 119894999  
  59. ^ Fernandez de la Vega, W. (1983)、「ランダムトーナメントにおける一貫性のある弧の集合の最大濃度について」、Journal of Combinatorial Theory、シリーズB、35 (3): 328– 332、doi : 10.1016/0095-8956(83)90060-6、MR 0735201 
  60. ^ Barthélémy, Jean-Pierre; Hudry, Olivier; Isaak, Garth; Roberts, Fred S. ; Tesman, Barry (1995)、「有向グラフの反転数」、Discrete Applied Mathematics、60 ( 1–3 ): 39– 76、doi : 10.1016/0166-218X(94)00042-C、MR 1339075 
  61. ^ Isaak, Garth; Narayan, Darren A. (2004)、「最小フィードバックアーク集合として非巡回トーナメントを持つトーナメントの分類」、Information Processing Letters、92 (3): 107– 111、doi : 10.1016/j.ipl.2004.07.001、MR 2095357 
  62. ^ Huang, Hao; Ma, Jie; Shapira, Asaf; Sudakov, Benny ; Yuster, Raphael (2013)、「オイラー有向グラフにおける大規模フィードバックアークセット、高最小次数サブグラフ、および長周期サイクル」、Combinatorics, Probability and Computing、22 (6): 859– 873、arXiv : 1202.2602、doi : 10.1017/S0963548313000394、hdl : 20.500.11850/73894、MR 3111546、S2CID 7967738  
  63. ^ハナウアー、キャサリン;ブランデンブルク、フランツ・ヨーゼフ。 Auer、Christopher (2013)、「正規グラフの最小フィードバック アーク セットの厳しい上限」、Brandstädt、Andreas。ヤンセン、クラウス。 Reischuk、Rüdiger (編)、コンピュータ サイエンスにおけるグラフ理論概念 - 第 39 回国際ワークショップ、WG 2013、ドイツ、リューベック、2013 年 6 月 19 ～ 21 日、改訂論文、コンピュータ サイエンスにおける講義ノート、vol. 8165、Springer、pp.  298–309、土井：10.1007/978-3-642-45043-3_26、ISBN 978-3-642-45042-6、MR  3139198
「 https://en.wikipedia.org/w/index.php?title=Feedback_arc_set&oldid=1328721344」から取得