グラフ同型写像の数え上げ問題に対するアルゴリズム

概要

論文の詳細を見る
本論文では、2つのpartial k-tree G, Hと、GからHへの部分同型写像ψが与えられたとき、GからHへのψに矛盾しない同型写像の数を求めるための多項式時間アルゴリズムを示す。また、M.R.Jerrum, L.G.Valiant, V.V.Vazirani〔Theoretical Computer Science, 43:169-188, 1986〕は、self-reducibleな問題に対しては、数え上げ問題に対する多項式時間アルゴリズムが存在すれば、各入力に対する解を、多項式時間でランダムに生成できることを証明した。GからHへのψに矛盾しない同型写像の数を求める問題はself-reducibleであるから、数え上げのアルゴリズムを用いて、GからHへのψに矛盾しない同型写像全体から、ランダムに1つを選び出力する多項式時間アルゴリズムが構成できる。上記のことから、2つのpartial k-tree G, Hが与えられたとき、GからHへの同型写像の数を数え上げる多項式時間アルゴリズムが存在することが分かる。この問題はself-reducibleであるかどうかは分かっていない。しかし、この場合にも、GからHへの同型写像全体から、ランダムに1つを選び出力する多項式時間アルゴリズムを構成できる。
社団法人電子情報通信学会の論文
1998-07-23