立方体グラフ
何人かの研究者は、立方体グラフに限定された指数関数時間アルゴリズムの計算量についての研究を行っている。例えば、グラフのパス分解(英語版)に動的計画法を適用することにより、Fomin と Høie は時間 O(2) 内に彼らの最大独立集合を見つける方法を示した。巡回セールスマン問題は、立方体グラフによって時間 O(1.251) 内に解くことが出来る。
いくつかの重要なグラフ最適化問題はAPX困難である。すなわち、それらには近似率がある定数で評価されるような近似アルゴリズムが存在するが、(P=NPでない限り)近似率が 1 へと向かうような多項式時間近似スキームは存在しない。そのような問題には、最小の頂点被覆を見つける問題や最大独立集合、最小支配集合問題、最大カットを見つける問題などが含まれる。立方体グラフの交叉数(英語版)(任意のグラフ描画において交叉する辺の最小数)もまた、NP困難であるが、近似出来ることもある。