ランク幅

ランク幅は、グラフ理論とパラメータ化された複雑性で使用されるグラフ幅パラメータであり、線形代数を使用して定義されます。

これは、与えられたグラフの頂点の階層的クラスタリングから定義され、頂点を葉とする三分木として視覚化できます。このような木から任意の辺を削除すると、木は 2 つのサブツリーに切断され、頂点は 2 つのサブセットに分割されます。パーティションの一方から他方に渡るグラフの辺は、双方向隣接行列で記述できます。ランク幅の目的上、この行列は実数を使用するのではなく、有限体 GF(2)上で定義されます。グラフのランク幅は、双方向隣接行列のランクの最大値であり、この最大値を最小化するように選択されたクラスタリングです。^[1]

ランク幅はクリーク幅と密接に関係しています。ここで、はクリーク幅とランク幅です。しかし、クリーク幅は、クリーク幅が大きいグラフでは計算がNP困難であり、そのパラメータ化された複雑さは不明です。対照的に、ランク幅が最大でも定数であるかどうかをテストするには多項式時間かかり、ランク幅が定数でない場合でも、一定の近似率で多項式時間で近似できます。このため、ランク幅は、クリーク幅のより計算しやすい代替として使用できます。^[1]${\displaystyle k\leq c\leq 2^{k+1}-1}$${\displaystyle c}$${\displaystyle k}$${\displaystyle k}$

高いランク幅を持つグラフ族の例として、正方格子グラフが挙げられます。格子グラフの場合、ランク幅はちょうど です。^[2]${\displaystyle n\times n}$${\displaystyle n-1}$