1．は　じ　め　に

　計算機性能の向上に伴い，複雑な構造を持ったデータを大量に保有することが可能となった．それに伴い，これまで，有用な知識を発見するために多くの技法が開発されてきた．部分構造を用いた構造データの機械学習⁽¹⁾や，生命情報学における遺伝子制御ネットワークや食物網の解析⁽²⁾，クリーク検出によるネットワーク解析⁽³⁾などがその一例である．本稿では，これらを支える基盤的技術の一つである部分グラフ列挙アルゴリズムに着目する．列挙アルゴリズムは，次に与える問題を解くアルゴリズムである：

［問題1（部分グラフ列挙問題）]　グラフと制約が与えられたときに，を満たす中の部分グラフ全てを漏れなく重複なく出力せよ．

　列挙問題としては，ほかに，実行可能解の総数を求める問題や2分決定図（BDD）⁽⁴⁾のように実行可能解を索引可能な構造に圧縮して出力する問題等があるが，本稿では扱わない^(注1)．以下では，部分グラフ列挙問題を単に列挙問題と呼ぶ．

　列挙問題に関する研究は，1950年代後半から連綿と続いてきた．その対象は，全域木や，パス，サイクル，クリーク，マッチング，カットなど多岐にわたる（網羅的なリストは文献(５)）．本稿では，列挙アルゴリズムに共通する時間計算量の評価方法と列挙問題の困難性（2．），並びに，現在頻繁に用いられる技法（3．）について，その現状を述べる．