次数指定した最大正則誘導部分グラフ探索問題(一般)

概要

論文の詳細を見る
本稿では,グラフG=(V, E)と指定次数γが与えられたとき,頂点部分集合S によって誘導される部分グラフG[S]が指定した次数rの正則グラフであり,頂点数が最大となるようなSを見つけ出す最適化問題を考える.また,グラフG[S]がr-正則,かつ連結グラフである場合についても考える.両問題は,ある定数rについて,近似することさえNP困難であることが知られている.本稿では,入力を特別なグラフクラスに限定した問題について考える.rをある定数とし,入力グラフを二部グラフまたは平面グラフに限定したとしても,本稿で考える連結性を条件とする正則誘導連結部分グラフ探索問題と必要としない正則誘導部分グラフ探索問題が近似することさえNP困難のままであることを示す.一方,以下のような木構造を持つグラフを入力とした場合には,両問題が簡単になることを示す.まず,木幅限定グラフを入力としたとき,両問題に対する最適解を線形時間で求めるアルゴリズムを示す.ここで,計算時間に隠れている係数は木幅の単一指数である.更に,入力を弦グラフとしたときには,両問題の最適解を多項式時間で求めることができることを示す.
一般社団法人電子情報通信学会の論文
2013-08-27