誘導パス

無向グラフ"G"中の誘導パスは， "G"の誘導グラフかつ道であるグラフのことである．
つまり，誘導パスは
そのパス上で隣接している任意の頂点対は"G"中で隣接しており，
かつ，
隣接していない任意の頂点対は"G"中で隣接していないような，"G"中の頂点の列である．
誘導パスは，スネークとも呼ばれ，
超立方体上の最長誘導パスを発見する問題は，
en:Snake-in-the-box問題として知られている．
また，
誘導サイクルは，
en:閉路をなす"G"の誘導グラフのことである．
また，誘導サイクルは，
コードレスサイクルや，その長さが4以上のとき，ホールとも呼ばれる．
アンチホールは，
"G"の補グラフにおけるホールである．
グラフ中の最長誘導パスの長さは，
そのグラフのう回路数と呼ばれる． 
任意のen:疎グラフに対して，
う回路数が固定された時は，:w:tree-depthが固定されている時と等価である．
グラフ"G"の誘導パス数とは，
グラフを分割するのに必要な最小の誘導パスの数である．
また，
"G"のパス被覆は，"G"のすべての頂点を覆うために必要な誘導パスの最小数である．
グラフ"G"の内周は，
"G"中の最小のサイクルの長さであるが，
そのサイクルは，誘導サイクルである．
同様に，奇内周は，
グラフにおける奇数長の最短な誘導サイクルの長さのことである．
例.
図は，
8個の頂点と12本の辺からなるグラフと，
このグラフにおける長さ4の誘導パスの例である．
図の超立方体は，
これより長い誘導パスを持たないが，
長さ6の誘導サイクルを持つ．
超立方体上の最長誘導パスまたは，最長誘導サイクルを求める問題は，
en:Snake-in-the-box問題として知られており，
符号理論や工学分野で広く研究されている．
グラフクラスの特徴付け.
多くの重要なグラフクラスは，
誘導パスや誘導サイクルの観点で特徴づけする事ができる．
アルゴリズム.
グラフ"G"とパラメタ"k"が与えられたとき，
"G"が少なくとも長さ"k"の誘導パスが存在するかを決定する問題は，NP完全である．
この結果は，Mihalis Yannakakisの未発表の結果としてが紹介している．
しかし，この問題は"G"が特定のグラフクラスであるときに，
たとえば，asteroidal-triple-free graphs や長いホールのないグラフであるときに，
多項式時間で解けることが知られている．
また，グラフ中の頂点が2つの誘導パスや誘導サイクルに分割できるかどうかを決定する問題も，
NP完全であることが知られている．
その系として，
グラフの誘導パス数を求める問題はNP困難であることがわかる．
最長誘導パスや最長誘導サイクルの近似アルゴリズムは，
次に与える還元から，
最大独立点集合を求める問題と関係があることがわかる． 
"n"個の頂点からなる任意のグラフ"G"に対して，
"2n"個の頂点からなる別のグラフ"H"を次のように構築する: 
2個の隣接頂点をもつ，かつ，一方が"G"中の頂点であるような，
"n"("n" − 1)/2個の頂点を"G"に加える．
次に，
"G"が"k"個の独立点集合を持つならば，
その独立点集合の頂点を"I"と入れ替えることで，
"H"は，必ず長さ2"k"の誘導パスまたは誘導サイクルを持つことがわかる．
一方，
"H"が長さ"k"の誘導パスまたは誘導サイクルを持つならば，
これらのパスまたはサイクルから得られる隣接していない頂点の極大集合から，
"G"は，サイズが少なくとも"k"/3の独立点集合を持つことがわかる．
よって，"G"の最大独立点集合のサイズは，"H"の最大誘導パスと最大誘導サイクルのサイズの定数倍以内である．
による独立点集合の近似不可能性の結果から，
NP=ZPPでない限り，
最適解のO("n"1/2-ε)以内の最長誘導パスまたは最長誘導サイクルを求める多項式時間アルゴリズムは存在しない．
"n"個の頂点と"m"個の辺からなるグラフのホールと，長さ5の誘導サイクルを含まないグラフのアンチホールは，
O(n+m2)時間で求められる．
アトミックサイクル.
アトミックサイクルは，"n"-弦を1つも持たないサイクルであり，
誘導サイクルの一般化である．
ここで，
"n"-弦とは，
与えられたあるサイクルに対して，
そのサイクル上のある2頂点を結ぶ結ぶ長さ"n"の道である．
ただし，"n"は，そのサイクルにおけるそれらの頂点の距離よりも小さい値である．
もし，サイクルが"n"-弦を持たなければ，
そのサイクルは，より小さなサイクルに分割することができないため，
そのサイクルをアトミックサイクルと呼ぶ．
"m"をグラフ"G"の辺の数とすると，
"G"中のすべてのアトミックサイクルを列挙するのに必要な時間は，
O("m"2)である．