Feedback Arc Set と巡回除去

有向グラフを DAG（有向非巡回グラフ）に変換するために「どの辺・頂点を取り除くか」を扱う一連の問題群。本ヴォルトでは serigraph（相互リンク文書をトポロジカルソートして PDF 化する自作ツール）の中核理論として深掘りされている。

関連する問題

• Feedback Arc Set (FAS) — 削除すると DAG が残る辺集合。各サイクルの少なくとも 1 辺を含む。
• Minimum Feedback Arc Set — どの辺を抜いてもサイズが減らない極小集合。集合内の辺は削除でなく 反転 しても Acyclic を保てる。できるだけ少ない辺で実現したいが NP困難なので近似解が提案されている。
• Feedback Vertex Set — 辺ではなく頂点を削除して巡回を断つ版。
• Maximum Acyclic Subgraph — 残す辺を最大化する双対的な定式化。NP困難。
• DAG vertex deletion — パス長を制約する頂点削除。UG-hard。

向き付けの等価性（タスク割当への応用）

論文 The Reduction of Directed Cyclic Graph for Task Assignment では、各頂点の out-degree を保つ向き付けは強連結成分が一致する（等価な orientation）ことを用い、巡回集合に沿った辺を反転して循環を消すアルゴリズムを示す。

serigraph の素朴アルゴリズム

1. サイクルを探索し、各サイクル内で重み（被参照数）最小の 1 辺を削除
2. サイクルが無くなるまで繰り返す
3. トポロジカルソートして直列化

サイクル数が頂点数に対し指数的に増えるため遅く、MST や PageRank による重み付け、DFS で訪問順を木にする近似が検討されている。

関連: strongly-connected-components / serigraph / _moc-algorithm