バーテックスカバー問題は、与えられたグラフのエッジのうち少なくとも一方に
粒子を置く制約充足問題である。この問題の複雑性クラスはNP完全である事が示
されており、直接的にバーテックスカバーの条件を満たす解を見つける事は難し
い。先行研究では、化学ポテンシャルを導入し分配関数を考えることで統計力学
的に研究されている[1]。それによると、頂点の被覆率とグラフの結合数のパラ
メータ平面で、Cover-Uncover相の相境界が現れることが分かっている。
しかし、Uncover相内部でも、うまくグラフを作るとバーテックスカバーの条件を満
たす配置を作ることができる。これが埋め込み型バーテックスカバー問題で、そ
の解が、埋め込んでいない問題の解とどういう違いが現れるのかをモンテカルロ
法で調べた[2]。
なお、本発表は東大総合文化の千葉康一氏の日本物理学会第65回年次大会での発
表の紹介である。
本発表の為、千葉氏には多大な協力をしていただいた事を、この場を借りて感謝
申し上げたいと思います。
[1]
Alexander K Hartmann and Martin Weight 2003 J. Phys. A : Math. Gen.
36 11069-11093.
[2] 日本物理学会講演概要集 第65回年次大会 第2分冊 p345