- 著者
-
朝廣 雄一
伊藤 健洋
江藤 宏
宮野 英次
- 出版者
- 一般社団法人電子情報通信学会
- 雑誌
- 電子情報通信学会技術研究報告. COMP, コンピュテーション
- 巻号頁・発行日
- vol.113, no.198, pp.43-50, 2013-08-27
本稿では,グラフG=(V, E)と指定次数γが与えられたとき,頂点部分集合S によって誘導される部分グラフG[S]が指定した次数rの正則グラフであり,頂点数が最大となるようなSを見つけ出す最適化問題を考える.また,グラフG[S]がr-正則,かつ連結グラフである場合についても考える.両問題は,ある定数rについて,近似することさえNP困難であることが知られている.本稿では,入力を特別なグラフクラスに限定した問題について考える.rをある定数とし,入力グラフを二部グラフまたは平面グラフに限定したとしても,本稿で考える連結性を条件とする正則誘導連結部分グラフ探索問題と必要としない正則誘導部分グラフ探索問題が近似することさえNP困難のままであることを示す.一方,以下のような木構造を持つグラフを入力とした場合には,両問題が簡単になることを示す.まず,木幅限定グラフを入力としたとき,両問題に対する最適解を線形時間で求めるアルゴリズムを示す.ここで,計算時間に隠れている係数は木幅の単一指数である.更に,入力を弦グラフとしたときには,両問題の最適解を多項式時間で求めることができることを示す.