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

双向图的优化问题及其应用

基本信息

批准号：
11780326
负责人：
田村明久
金额：
$ 1.54万
依托单位：
Kyoto University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Encouragement of Young Scientists (A)
财政年份：
1999
资助国家：
日本
起止时间：
1999 至 2000
项目状态：
已结题

项目摘要

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

研究最多的组合优化问题之一是无向图上的稳定集问题。通常，此问题属于NP完整类，并且可能没有多项式时间解决方案。但是，对于某些图形类，例如完美的图和crowfrey图，存在多项式时间解决方案。特别是，多项式时间解的特征是完美的图形是稳定的设置问题与其半阳性的确定放松问题一致。 Grotschel-Lovasz-Schrijver也证明了反相反的命题。也就是说，表明无方向的图是稳定性设置问题所必需和充分条件，使其与半阳性的确定放松问题匹配。今年的研究结果有两个：他们提供了Grotschel-Lovaz-Schrijver结果的单独证明，他们将此结果扩展到了广义稳定的集合问题。他们的证明使用互补图的概念和反向图形的抗块。通过利用半阳性确定编程问题的二次规划问题表示形式，我们给出了一个替代证明，该证明不引入诸如补充图之类的概念。另一方面，普遍的稳定集问题是稳定集问题的自然扩展到双向图，但是对于双向图，没有补充图的概念。因此，很难扩展他们的证明方法，以证明“双向图是完美的”命题，并且“广义稳定的集合问题及其半积极的确定放松是一致的”是等效的，但是我们的证明方法甚至不使用补充图的概念，甚至可以应用于扩展的概念性的扩展主张。这些结果是在国际会议上提出的，并作为学术期刊的论文汇编。