誘導パス
グラフGとパラメタkが与えられたとき, Gが少なくとも長さkの誘導パスが存在するかを決定する問題は,NP完全である. この結果は,Mihalis Yannakakisの未発表の結果としてGarey & Johnson (1979)が紹介している. しかし,この問題はGが特定のグラフクラスであるときに, たとえば,asteroidal-triple-free graphs や長いホールのないグラフであるときに, 多項式時間で解けることが知られている.
また,グラフ中の頂点が2つの誘導パスや誘導サイクルに分割できるかどうかを決定する問題も, NP完全であることが知られている. その系として, グラフの誘導パス数を求める問題はNP困難であることがわかる.
最長誘導パスや最長誘導サイクルの近似アルゴリズムは, 次に与える還元から, 最大独立点集合を求める問題と関係があることがわかる. n個の頂点からなる任意のグラフGに対して, 2n個の頂点からなる別のグラフHを次のように構築する: 2個の隣接頂点をもつ,かつ,一方がG中の頂点であるような, n(n − 1)/2個の頂点をGに加える.