双向グラフに対する最適化問題とその応用

点击翻译按钮获取中文摘要

組合せ最適化問題の中でも最も研究されているものの一つが無向グラフ上の安定集合問題である。一般にこの問題はNP完全クラスに属し、多項式時間解法はおそらく存在しないであろう。しかし、パーフェクトグラフ、クローフリーグラフなどの幾つかのグラフクラスに対しては多項式時間解法が存在する。特にパーフェクトグラフに対する多項式時間解法の特徴は、安定集合問題がその半正定値緩和問題と一致するところにある。またGrotschel-Lovasz-Schrijverは、その逆命題も成立することを証明した。すなわち、安定集合問題とその半正定値緩和問題が一致するための必要十分条件が無向グラフがパーフェクトであることを示した。本年度の研究成果は、このGrotschel-Lovaz-Schrijverの結果の別証明を与えたことと、この結果を一般化安定集合問題へと拡張したという2つである。彼らの証明では、無向グラフの補グラフとアンチブロッカーという概念を用いている。我々は、半正定値計画問題に対する2次計画問題表現を利用することで、補グラフなどの概念を導入しない別証明を与えた。一方、一般化安定集合問題は安定集合問題を双向グラフ上へと自然な形で拡張したものであるが、双向グラフに対しては補グラフという概念がない。そのため「双向グラフがパーフェクト」と「一般化安定集合問題とその半正定値緩和が一致」という命題が同値であることを示すには、彼らの証明法を拡張することは困難であるが、補グラフという概念を用いない我々の証明法は、拡張された命題の同値性証明まで適用できるものであった。これらの結果は国際会議において発表し、論文としてまとめ学術雑誌に投稿した。