フィードバック頂点集合

赤い頂点とそれらに接続するすべての辺を削除すると、グラフには閉路がなくなります。したがって、頂点の集合はグラフのフィードバック頂点集合（FVS）です。これより小さいFVSは存在しないため、これは最小のFVSであり、FVSの数はサイズ3です

数学の分野であるグラフ理論において、グラフのフィードバック頂点集合（FVS）とは、グラフから頂点を除去すると閉路がなくなる頂点の集合である（「除去」とは、頂点とそれに隣接するすべての辺を削除することを意味する）。同様に、各FVSには、グラフ内の任意の閉路の頂点が少なくとも1つ含まれる。グラフのフィードバック頂点集合数は、最小のFVSのサイズである。最大でkのサイズのフィードバック頂点集合が存在するかどうかはNP完全問題であり、 NP完全であることが示された最初の問題の一つである。これは、オペレーティングシステム、データベースシステム、VLSIチップ設計など、幅広い分野に応用されている。

定義

FVS決定問題は次のとおりです

インスタンス: (無向または有向)グラフ と正の整数。 ${\displaystyle G=(V,E)}$ ${\displaystyle k}$

質問:のすべての頂点とそれらの隣接辺を から削除したときに、残りに循環がない となるようなのサブセットはありますか? ${\displaystyle X\subseteq V}$ ${\displaystyle |X|\leq k}$ ${\displaystyle X}$ ${\displaystyle G}$

からを取り除いた後に残るグラフは誘導フォレスト（有向グラフの場合は誘導有向非巡回グラフ）です。したがって、グラフ内の最小FVSを見つけることは、最大誘導フォレスト（有向グラフの場合は最大誘導有向非巡回グラフ）を見つけることと等価です。 ${\displaystyle G[V\setminus X]}$ ${\displaystyle X}$ ${\displaystyle G}$

NP完全性

Karp (1972)は、有向グラフにおいてサイズのフィードバック頂点集合を見つけることはNP完全であることを示しました。この問題は、最大入次数と最大出次数が2である有向グラフ、および最大入次数と最大出次数が3である有向平面グラフではNP完全のままです。^{[ 1 ]} ${\displaystyle \leq k}$

カープの縮約は、無向グラフ上のフィードバック頂点集合問題のNP完全性も示唆する。この問題は、最大次数が4のグラフでもNP完全である。フィードバック頂点集合問題は、マトロイドパリティ問題に基づくアルゴリズムを用いることで、最大次数が3以下のグラフ上で多項式時間で解くことができる。^{[ 2 ]}

正確なアルゴリズム

最小フィードバック頂点集合の大きさを求める 対応するNP最適化問題は、グラフの頂点数nとすると、時間O（1.7347n ^）で 解くことができる。 ^{[ 3 ]}このアルゴリズムは、実際には最大誘導フォレストを計算し、そのようなフォレストが得られると、その補完が最小フィードバック頂点集合である。グラフ内の最小フィードバック頂点集合の数は、O（1.8638n ^）に制限される。^{[ 4 ]}有向フィードバック頂点集合問題は、与えられた有向グラフの頂点数nとすると、時間O*（1.9977n ^）で解くことができる。 ^{[ 5 ]}有向問題と無向問題のパラメータ化されたバージョンは、どちらも固定パラメータで扱える。^{[ 6 ]}

最大次数3の無向グラフでは、フィードバック頂点集合問題は、線形マトロイドのマトロイドパリティ問題の例に変換することで、多項式時間で解くことができます。^{[ 7 ]}

有向グラフ内のすべてのフィードバック頂点（すべての有向サイクル上に存在する頂点）を見つけるという特殊なケースは、GareyとTarjanによるDFSベースのアルゴリズムを使用して線形時間で解決できます。^{[ 8 ]}

近似

無向問題はAPX完全である。これは以下の事実から導かれる

• 頂点被覆問題のAPX完全性; ^{[ 9 ]}
• 頂点カバー問題からそれへのL 削減を保存する近似の存在。
• 既存の定数係数近似アルゴリズム。^{[ 10 ]}

無向グラフにおける最もよく知られている近似アルゴリズムは2倍の近似値である。^{[ 11 ]}

対照的に、有向グラフ版の問題は近似がはるかに困難であるように思われる。未証明ではあるものの一般的に用いられる計算困難性仮定であるユニークゲーム予想によれば、多項式時間で任意の定数倍以内で問題を近似することはNP困難である。この困難性は、密接に関連するフィードバックアークセット問題に対して最初に証明されたが^{[ 12 ]}、有向グラフにおけるフィードバックアークセット問題とフィードバック頂点セット問題は解のサイズを維持しながら互いに縮約可能であるため^{[ 13 ]} 、後者にも当てはまる。

境界

エルデシュ・ポーザ定理によれば、最小フィードバック頂点集合の大きさは、与えられたグラフ内の頂点分離閉路の最大数の対数係数以内である。^{[ 14 ]}

関連概念

• 頂点の代わりに、フィードバック辺集合を考えることができます。これは無向グラフの辺の集合で、これを削除するとグラフは非巡回になります。グラフ内の最小のフィードバック辺集合のサイズは、グラフの回路ランクと呼ばれます。FVS数とは対照的に、回路ランクは簡単に計算できます。それは で、Cはグラフの連結成分の集合です。最小のフィードバック辺集合を見つける問題は、全域森 を見つけることと同等であり、これは多項式時間で実行できます ${\displaystyle |E|-|V|+|C|}$
• 有向グラフにおける類似の概念は、フィードバックアーク集合（FAS）である。これは、グラフを非巡回化する有向アークの集合である。最小のFASを求めることはNP困難問題である。^{[ 10 ]}

応用

• オペレーティングシステムにおいて、フィードバック頂点集合はデッドロック回復の研究において重要な役割を果たします。オペレーティングシステムの待機グラフでは、各有向サイクルがデッドロック状況に対応します。すべてのデッドロックを解決するには、ブロックされているプロセスの一部を中止する必要があります。このグラフにおける最小フィードバック頂点集合は、中止する必要があるプロセスの最小数に対応します。^{[ 15 ]}
• フィードバック頂点集合問題はVLSIチップ設計に応用されている。^{[ 16 ]}
• もう一つの応用は計算量理論である。グラフ上の計算問題の中には一般にNP困難であるものもあるが、FVS数が有限であるグラフでは多項式時間で解けるものがある。例としては、グラフ同型性^{[ 17 ]}やパス再構成問題^{[ 18 ]が挙げられる。}

注記

1. GareyとJohnsonによる未発表の結果。Garey & Johnson (1979) : GT7を
2. 上野・梶谷・後藤 (1988) ;リーとリュー (1999)
3. フォミン＆ヴィランジェ（2010）
4. Fomin et al. (2008) .
5. ラズゴン (2007) .
6. チェンら（2008） .
7. 上野・梶谷・後藤 (1988)。
8. Garey, Michael R.; Tarjan, Robert E. (1978). 「すべてのフィードバック頂点を見つけるための線形時間アルゴリズム」. Information Processing Letters . 7 (6): 274--276. doi : 10.1016/0020-0190(78)90015-7 .
9. ディヌール＆サフラ 2005
10. カープ（1972）
11. Becker & Geiger (1996) .同じ近似比を持つ代替近似アルゴリズムについては、 Bafna, Berman & Fujito (1999)も参照
12. Guruswami, Venkatesan; Manokaran, Rajsekar; Raghavendra, Prasad (2008). 「ランダム順序付けの克服は困難：最大非巡回部分グラフの近似不可能性」2008年第49回IEEEコンピュータサイエンス基礎シンポジウム. pp.  573– 582. doi : 10.1109/FOCS.2008.51 . ISBN 978-0-7695-3436-7. S2CID  8762205 .
13. Even, G.; (Seffi) Naor, J.; Schieber, B.; Sudan, M. (1998). 「有向グラフにおける最小フィードバック集合とマルチカットの近似」 . Algorithmica . 20 ( 2): 151– 174. doi : 10.1007/PL00009191 . ISSN 0178-4617 . S2CID 2437790  
14. エルデシュ＆ポサ（1965年）。
15. シルバーシャッツ、ガルビン、ガニア (2008)。
16. フェスタ、パルダロス、レゼンデ (2000)。
17. クラッシュ, ステファン; シュバイツァー, パスカル (2010). 「有界フィードバック頂点集合数のグラフの同型性」 . カプラン, ハイム (編).アルゴリズム理論 - SWAT 2010 . コンピュータサイエンス講義ノート. 第6139巻. ベルリン, ハイデルベルク: シュプリンガー. pp.  81– 92.書誌コード: 2010LNCS.6139...81K . doi : 10.1007/978-3-642-13731-0_9 . ISBN 978-3-642-13731-0.
18. アルゴリズムとデータ構造(PDF) . コンピュータサイエンス講義ノート. 第11646巻. 2019年. doi : 10.1007/978-3-030-24766-9 . ISBN 978-3-030-24765-2. S2CID  198996919 .

参考文献

研究論文

• Bafna, Vineet; Berman, Piotr; Fujito, Toshihiro (1999)、「無向フィードバック頂点集合問題に対する2近似アルゴリズム」、SIAM Journal on Discrete Mathematics、12 (3): 289–297 (電子版)、doi : 10.1137/S0895480196305124、MR  1710236.
• Becker, Ann; Bar-Yehuda, Reuven; Geiger, Dan (2000)「ループカットセット問題に対するランダム化アルゴリズム」、Journal of Artificial Intelligence Research、12 : 219– 234、arXiv : 1106.0225、doi : 10.1613/jair.638、MR  1765590、S2CID  10243677
• ベッカー、アン; ガイガー、ダン (1996)、「頂点フィードバック集合問題に対するパール法の調整法と貪欲近似アルゴリズムの最適化」人工知能、83 (1): 167– 188、CiteSeerX  10.1.1.25.1442、doi : 10.1016/0004-3702(95)00004-6
• Cao, Yixin; Chen, Jianer; Liu, Yang (2010)、「フィードバック頂点集合について：新たな尺度と新たな構造」、Kaplan, Haim (編)、Proc. 12th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2010)、ベルゲン、ノルウェー、2010年6月21日～23日、Lecture Notes in Computer Science、vol. 6139、pp.  93– 104、arXiv : 1004.1672、Bibcode : 2010LNCS.6139...93C、doi : 10.1007/978-3-642-13731-0_10、ISBN 978-3-642-13730-3
• Chen, Jianer; Fomin, Fedor V.; Liu, Yang; Lu, Songjian; Villanger, Yngve (2008)、「フィードバック頂点集合問題のための改良アルゴリズム」、Journal of Computer and System Sciences、74 (7): 1188– 1198、doi : 10.1016/j.jcss.2008.05.002、MR  2454063
• Chen, Jianer; Liu, Yang; Lu, Songjian; O'Sullivan, Barry; Razgon, Igor (2008)「有向フィードバック頂点集合問題に対する固定パラメータアルゴリズム」、Journal of the ACM、55 (5)、Art. 21、doi : 10.1145/1411509.1411511、MR  2456546、S2CID  1547510
• Dinur, Irit ; Safra, Samuel (2005)、「最小頂点被覆近似の困難性について」（PDF）、Annals of Mathematics、Second Series、162 (1): 439– 485、doi : 10.4007/annals.2005.162.439、MR  2178966 、 2009年9月20日にオリジナル（PDF）からアーカイブ、2010年3月29日取得
• エルデシュ、ポール；ポサ、ラヨシュ（1965）「グラフに含まれる独立回路について」（PDF）、Canadian Journal of Mathematics、17：347–352、doi：10.4153/CJM-1965-035-8、S2CID  123981328
• Fomin, Fedor V.; Gaspers, Serge; Pyatkin, Artem; Razgon, Igor (2008)「最小フィードバック頂点集合問題について：厳密アルゴリズムと列挙アルゴリズム」、Algorithmica、52 (2): 293– 307、CiteSeerX  10.1.1.722.8913、doi : 10.1007/s00453-007-9152-0、S2CID  731997
• Fomin, Fedor V.; Villanger, Yngve (2010)、「最小三角測量による誘導部分グラフの探索」、Proc. 27th International Symposium on Theoretical Aspects of Computer Science (STACS 2010)、Leibniz International Proceedings in Informatics (LIPIcs)、vol. 5、pp.  383– 394、doi : 10.4230/LIPIcs.STACS.2010.2470、ISBN 9783939897163、S2CID  436224
• カープ、リチャード・M. (1972)、「組合せ問題における縮約可能性」、コンピュータ計算の複雑性に関するシンポジウム議事録、IBMトーマス・J・ワトソン研究センター、ニューヨーク州ヨークタウン・ハイツ、プレナム、pp.  85– 103
• Li, Deming; Liu, Yanpei (1999)、「3-正則単純グラフの最小フィードバック頂点集合を求める多項式アルゴリズム」、Acta Mathematica Scientia、19 (4): 375– 381、doi : 10.1016/s0252-9602(17)30520-9、MR  1735603
• Razgon, I. (2007)、「O*(1.9977 ⁿ )における最小有向フィードバック頂点集合の計算」、イタリア語版、Giuseppe F.、Moggi, Eugenio、Laura, Luigi（編）、第10回イタリア理論計算機科学会議議事録（PDF）、World Scientific、pp.  70– 81
• 上野 修一; 梶谷 洋二; 後藤 真也 (1988)「頂点次数が3を超えないグラフの非分離独立集合問題とフィードバック集合問題について」,離散数学, 72 ( 1– 3): 355– 360, doi : 10.1016/0012-365X(88)90226-9 , MR  0975556

教科書と調査記事

• Festa, P.; Pardalos, PM; Resende, MGC (2000)「フィードバック集合問題」、Du, D.-Z.; Pardalos, PM (編)『組合せ最適化ハンドブック 補足A』（PDF）、Kluwer Academic Publishers、pp.  209– 259
• ゲイリー、マイケル・R. ;ジョンソン、デイビッド・S. (1979)、「コンピュータとイントラクタビリティ：NP完全性理論へのガイド」、WHフリーマン、A1.1: GT7、p. 191、ISBN 978-0-7167-1045-5
• シルバーシャッツ、エイブラハム、ガルビン、ピーター・ベア、ガニエ、グレッグ（2008年）、オペレーティングシステムコンセプト（第8版）、John Wiley & Sons. Inc、ISBN 978-0-470-12872-5

「 https://en.wikipedia.org/w/index.php?title=Feedback_vertex_set&oldid=1336671991」より取得