細矢インデックス
細矢インデックスの計算複雑性は、グラフを平面グラフに限ったとしてもSharp-P完全(英語版)である。しかし、マッチング多項式(英語版)で引数を1としたときの値 mG として計算できることに基づけば、細矢インデックスの計算は木幅(英語版)(treewidth)の上限をパラメータとする固定パラメータ容易性(英語版)(fixed-parameter tractability,FPT)を持つ。さらに、クリーク幅(英語版)(clique-width)の上限を k とするとき次数が k に線形的に依存するような多項式時間で計算できる(つまりグラフの頂点数 n に対し計算量が O ( n f ( k ) ) {\displaystyle O({n^{f(k)}})} で済む)。