フィードバック頂点集合

グラフ理論と計算機科学におけるフィードバック頂点集合（Feedback Vertex Set, FVS）問題は、無向グラフにおいて最小の頂点部分集合を見つける問題です。これらの頂点を削除することで、サイクルが存在しないグラフ（つまり、森）が得られます。FVS問題の目的は、フィードバック頂点集合のサイズを最小化することであり、この問題はNP困難であるため、最適解を見つける計算量は非常に高いです。有向グラフの場合、フィードバック頂点集合とは、その頂点を削除することで有向非循環グラフ（Directed Acyclic Graph, DAG）になるような頂点の部分集合を指します。FVS問題は、ネットワーク構造の最適化やシステムの循環依存関係の削減に重要な応用価値があります。