6J-01
フィードバック独立点集合問題の計算複雑性
○田村祐馬，伊藤健洋，周　　暁（東北大）
本稿では，フィードバック独立点集合問題に対し，グラフ構造を基にした困難性の解析と，近似アルゴリズムの提案を行う．無向グラフGに対し，削除するとグラフが森となるような独立点集合をフィードバック独立点集合と呼ぶ．フィードバック独立点集合問題とは，与えられたグラフの最小のフィードバック独立点集合を求める問題である．この問題は，一般にはNP困難であることが知られているが，本稿ではグラフ構造に着目して，問題の計算複雑性の解析を行う．また，最大次数Δの二部グラフに対しては，多項式時間(Δ-1)倍近似アルゴリズムを提案する．
footer 著作権について 倫理綱領 プライバシーポリシー セキュリティ 情報処理学会