クリーク幅

グラフ理論において、グラフGのクリーク幅は、グラフの構造的複雑さを表すパラメータです。これはツリー幅と密接に関連していますが、ツリー幅とは異なり、密なグラフでは小さくなることがあります。クリーク幅は、次の4つの操作によってGを構築するために必要な最小ラベル数として定義されます。 

1. ラベルiを持つ新しい頂点vを作成します ( i ( v )と表記)。
2. 2 つのラベル付きグラフGとHの非交和(以下で表す)${\displaystyle G\oplus H}$）
3. iというラベルの付いたすべての頂点とjというラベルの付いたすべての頂点を辺で結ぶ（η ( i , j )と表記される）。ただし、i ≠ jである。
4. ラベルiをラベルjに名前変更する ( ρ ( i , j )と表記)

クリーク幅が制限されているグラフには、コグラフや距離継承グラフなどが含まれます。クリーク幅が制限されていない場合、その計算はNP困難であり、制限されている場合に多項式時間で計算できるかどうかは不明ですが、クリーク幅の効率的な近似アルゴリズムは知られています。これらのアルゴリズムとクールセルの定理に基づき、任意のグラフに対してNP困難な多くのグラフ最適化問題を、クリーク幅が制限されているグラフ上では迅速に解いたり近似したりすることができます。

クリーク幅の概念の根底にある構築手順は、 1990 年にCourcelle、Engelfriet、Rozenberg ^{[ 1 ]}およびWanke (1994 )によって定式化されました。 「クリーク幅」という名称は、Chlebíková (1992 )によって別の概念に使用されました。 1993 年までに、この用語はすでに現在の意味を持つようになりました。^{[ 2 ]}

コグラフは、クリーク幅が最大で2であるグラフです。^{[ 3 ]} すべての距離遺伝グラフは、クリーク幅が最大で3です。ただし、単位区間グラフのクリーク幅は（グリッド構造に基づいて）無制限です。^{[ 4 ]} 同様に、二部順列グラフのクリーク幅は（同様のグリッド構造に基づいて）無制限です。^{[ 5 ]} 4つの頂点を持つパスと同型な誘導部分グラフを持たないグラフとしてコグラフを特徴付けることにより、禁止された誘導部分グラフによって定義される多くのグラフクラスのクリーク幅が分類されています。^{[ 6 ]}

有界クリーク幅を持つ他のグラフには、 kの有界値に対するk葉べき乗が含まれます。これらは、グラフべき乗T ^kにおける木Tの葉の誘導部分グラフです。ただし、指数が有界でない葉べき乗は有界クリーク幅を持ちません。^{[ 7 ]}

Courcelle & Olariu (2000)およびCorneil & Rotics (2005)は、特定のグラフのクリーク幅に関する以下の境界を証明した。

• グラフのクリーク幅が最大でkであれば、そのグラフのすべての誘導部分グラフも最大で k である。^{[ 8 ]}
• クリーク幅がkのグラフの補グラフのクリーク幅は最大で2kである。^{[ 9 ]}
• 木幅wのグラフのクリーク幅は最大で3 · 2 ^{w − 1}です。この境界における指数関数的な依存性は必要不可欠です。クリーク幅が木幅よりも指数関数的に大きいグラフが存在するからです。^{[ 10 ]}反対に、クリーク幅が制限されているグラフは、木幅が制限されない場合があります。例えば、n頂点の完全グラフはクリーク幅が 2 ですが、木幅はn − 1 です。しかし、部分グラフとして完全二部グラフK _t、tを持たないクリーク幅kのグラフは、木幅が最大で3 k ( t − 1) − 1です。したがって、疎グラフのすべての族について、木幅が制限されていることは、クリーク幅が制限されていることと同等です。^{[ 11 ]}
• もう1つのグラフパラメータであるランク幅は、クリーク幅によって両方向に制限されます。ランク幅 ≤ クリーク幅 ≤ 2^{ランク幅 + 1}。^{[ 12 ]}

さらに、グラフG のクリーク幅がkである場合、グラフのべき乗G ^{c の}クリーク幅は最大で2 kc ^kです。^{[ 13 ]}ツリー幅からのクリーク幅の上限とグラフのべき乗のクリーク幅の上限の両方に指数的なギャップがありますが、これらの上限は互いに合成されません。グラフGのツリー幅がwである場合、G ^{c の}クリーク幅は最大で2( c + 1) ^{w + 1} − 2であり、ツリー幅に対して単指数的です。^{[ 14 ]}

より一般的なグラフのクラスではNP困難である多くの最適化問題は、これらのグラフの構成手順が既知であれば、有界クリーク幅のグラフ上で動的計画法によって効率的に解決できる。 ^{[ 15 ] [ 16 ]}特に、 MSO ₁単項二階論理（頂点の集合に対する量化を可能にする論理形式）で表現できるすべてのグラフ特性は、クールセルの定理の一形式により、有界クリーク幅のグラフに対して線形時間アルゴリズムを持つ。^{[ 16 ]}

構築手順が既知の場合、有界クリーク幅のグラフの最適なグラフ彩色やハミルトン閉路を多項式時間で見つけることも可能だが、多項式の指数はクリーク幅とともに増加し、計算複雑性理論からの証拠は、この依存性が必要である可能性が高いことを示している。 ^{[ 17 ]} 有界クリーク幅のグラフはχ有界であり、その彩色数は最大クリークのサイズの関数であることを意味する。^{[ 18 ]}

クリーク幅が 3 のグラフは、分割分解に基づくアルゴリズムを使用して多項式時間で認識でき、それらの構築シーケンスも見つけることができます。^{[ 19 ]} クリーク幅が無制限のグラフの場合、クリーク幅を正確に計算することはNP 困難であり、加算誤差が線形未満である近似値を得ることも NP 困難です。 ^{[ 20 ]}しかし、クリーク幅が制限されている場合は、制限された幅 (実際のクリーク幅よりも指数関数的に大きい) の構築シーケンスを多項式時間で得ることができます。 ^{[ 21 ]}特に、頂点の数の 2 乗時間で得られます。^{[ 22 ]}正確なクリーク幅、またはそれに対するより厳密な近似値を固定パラメータ扱いやすい時間で計算できるかどうか、クリーク幅の任意の固定境界に対して多項式時間で計算できるかどうか、あるいはクリーク幅が 4 のグラフを多項式時間で認識できるかどうかは未解決です。^{[ 20 ]}

有界クリーク幅のグラフの理論は有界ツリー幅のグラフの理論に似ているが、ツリー幅とは異なり、密なグラフを許容する。グラフの族が有界クリーク幅を持つ場合、その族は有界ツリー幅を持つか、またはすべての完全二部グラフがその族のグラフの部分グラフである。^{[ 11 ]}ツリー幅とクリーク幅は、線グラフの理論によっても関連付けられている。グラフの族が有界ツリー幅を持つのは、その線グラフが有界クリーク幅を持つ場合のみである。^{[ 23 ]}

有界クリーク幅のグラフは有界ツイン幅も持つ。^{[ 24 ]}