講演者は，グラフ最適化問題についての計算複雑性について研究を行っている．グラフ最適化問題の中で，特徴Pをもつ最大誘導部分グラフ探索問題 (Maximum Induced Subgraph with Property P) がある．例えば，特徴が独立集合であるとき，この問題は最大独立頂点集合問題としてみることができる．グラフGが特徴Pを持ち，グラフGにおいてどの誘導部分グラフも特徴Pを持つとき，その特徴Pは遺伝性があるという．この最大誘導部分グラフ探索問題は，特徴Pが遺伝性を持つとき，一般グラフにおいて近似困難であることが知られている．本講演では，遺伝性を持たない正則性などを特徴とした最大誘導部分グラフ探索問題に対して，入力グラフの構造を制限したときの計算複雑性について紹介する．