特性試験

グラフ特性テストの分野は、Goldreich、Goldwasser、およびRonによって初めて導入されました。1998年に発表された彼らの画期的な論文では、抽象的なグラフ分割問題が分析され、いくつかのテスターが提供されています。これらには、二部グラフ性、k彩色可能性、大きなクリークを持つこと、大きなカットを持つことなど、いくつかの重要なグラフ特性が特殊なケースとして含まれています。^{[ 4 ]}特に、部分グラフをサンプリングしてそれが特性を満たすかどうかをチェックする自然なアルゴリズムはすべて正しいですが、クエリの複雑さは最適ではない可能性があります。

それ以来、関連するいくつかの発見がなされてきた。

• 1992年に、Alon、Duke、Lefmann、Rödl、およびYusterは、任意のグラフHに対して、 Hを部分グラフとして含まないという性質がテスト可能であることを示した。^{[ 6 ]}
• 1999年に、Alon、Fischer、Krivelevich、およびSzegedyは、任意のグラフHに対して、誘導部分グラフとしてHを含まないという性質がテスト可能であることを示した。 ^{[ 7 ]}
• 2005年に、AlonとShapiraは、任意の単調グラフ特性（頂点と辺の削除の下で保持される特性）は片側誤差でテスト可能であることを示した。^{[ 8 ]}
• 2008年、アロンとシャピラは、すべての遺伝的グラフ特性に対して片側誤差を持つテスターを示した。彼らはまた、テストしやすい特性も特徴づけた。つまり、これらの自然な特性は半遺伝的である。これらの記述については、以下で詳しく説明する。^{[ 2 ]}

グラフの性質は、頂点の削除によって保持される場合、または同等に、誘導部分グラフを取っても保持される場合に、遺伝的性質であると言います。重要な遺伝的性質としては、H-フリー性（あるグラフHについて）、k-彩色可能性、平面性などがあります。すべての遺伝的性質はテスト可能です。

定理（Alon & Shapira 2008）。すべての遺伝的グラフ特性は片側誤差でテスト可能である。^{[ 2 ]}

この証明は、誘導部分グラフの無限族に対するグラフ除去補題のバージョンに基づいています。この正則性アプローチを用いたクエリの複雑さは、Szemerédiの正則性補題におけるタワー関数の上限のために大きくなります。

定理（無限グラフ除去補題）。任意の（おそらく無限の）グラフの集合Hとε > 0に対して、 h ₀とδ > 0が存在し、G が、頂点数が最大h _{0であるすべての}H ∈ Hに対して、 Hのコピーがδ n ^{v ( H )}より少ないn頂点グラフである場合、G はε n ²未満のエッジを追加/削除することによって誘導Hフリーにすることができる。^{[ 9 ]}

非公式には、無頓着なテスターは入力のサイズを認識しません。グラフプロパティPの場合、それはパラメータεとグラフGを入力として受け取り、近接パラメータεを持つプロパティPに対してG上でプロパティ テスト アルゴリズムとして実行され、 Gに対して正確にq ( ε )回のクエリを実行するアルゴリズムです。

定義。オブリビアス・テスターは、パラメータεを入力として受け取るアルゴリズムです。整数q ( ε )を計算し、オラクルに、一様にランダムに選択されたGから正確にq ( ε )個の頂点を持つ誘導部分グラフHを要求します。次に、 εとHに従って (おそらくランダムに) 受け入れるか拒否します。プロパティPを持つGに対して少なくとも2/3 の確率で受け入れ、プロパティPからε遠いGに対して少なくとも2/3 の確率で拒否する場合、プロパティ P をテストしていると言います。^{[ 2 ] [ 1 ] [ 10 ]}

重要な点として、無知なテスターが行うクエリの数は、入力グラフGのサイズではなく、εのみに依存する定数です。プロパティテストアルゴリズムと完全に類似しており、片側エラーを持つ無知なテスターに​​ついて議論することができます。

テスターが頂点の数にアクセスする必要があるようなグラフの特性をいくつか考案することができる。

例。グラフGは、頂点数が偶数の場合は二部グラフ、奇数の場合は完全グラフである場合に、性質Pを満たす。 ^{[ 2 ]}

この場合、テスターは頂点の数を知らない限り、どの特性（二部グラフ性または完全性）をテストすべきかを区別することさえできません。このような不自然な特性の例は数多く存在します。実際、片側誤差を持つ無知なテスターに​​よってテスト可能なグラフ特性の特徴付けは、自然な特性のクラスにつながります。

定義。グラフ特性Hは、遺伝的グラフ特性Hが存在し、 P を満たす任意のグラフがH を満たし、任意のε > 0に対して、 M ( ε )が存在し、P を満たすことから ε 遠ざかる少なくともM ( ε )のサイズのすべてのグラフがH を満たさない誘導部分グラフを含む場合、半遺伝的であるという。^{[ 2 ]}

自明なことに、遺伝的性質は半遺伝的でもある。この特徴付けは、上記のアロンとシャピラの定理の逆、すなわち、容易にテストできる性質（片側誤差を持つ無自覚なテスターを持つ性質）はほぼ遺伝的であるということに部分的に答える。同じ論文で、彼らは次のことを示した。

定理（Alon & Shapira 2008）。グラフ特性Pが片側エラーテスターを秘匿するのは、 Pが半遺伝的である場合に限る。 ^{[ 2 ]}

このセクションでは、三角形フリー性、二部グラフ性、およびk彩色可能性に対する、片側誤差を持つ自然なオブリビアス テスト アルゴリズムをいくつか紹介します。これらのアルゴリズムは、グラフGの頂点のサブセットX をランダムにサンプリングし、総当たり探索によってXによって張られる部分グラフ上でグラフ特性が成り立つかどうかを確認するという自然なアイデアに従っているという意味で自然です。これらの特性は実際には遺伝的であるため、片側誤差となります。つまり、 G がその特性を満たす場合、 Xによって張られる誘導部分グラフもその特性を満たすはずなので、テスターは常に受け入れます。

三角形フリー性については、このテスターは三角形除去補題の応用です。具体的には、グラフGが三角形フリーからεだけ離れている場合、 G が少なくともδ n ³個の三角形を持つような(計算可能な) 定数δ = δ ( ε )が存在することを示しています。

例（三角形不存在性判定アルゴリズム）。

1. グラフGが与えられたとき、 q ( ε ) = 1/ δ個の頂点のトリプルからなるランダムな集合 X を独立にランダムに選択します。ここでδは上記のとおりです。
2. Xの任意の 3 つの頂点について、その 3 つの頂点のペアすべてがGで隣接しているかどうかを問い合わせます。
3. このアルゴリズムは、どの3つの頂点も三角形を形成しない場合は受理し、そうでない場合は拒否する。^{[ 1 ]}

二部グラフ性およびk彩色性については、δ を以下のテスターのエラー確率の望ましい上限とします。クエリの複雑さと実行時間を混同しないように注意してください。後者は、誘導された部分グラフ上の特性をテストするための多項式時間決定アルゴリズムがないため、多くの場合指数関数的になります (両方の場合に当てはまります)。代わりに、総当たり探索によってチェックします。^{[ 4 ]}

例（二部グラフテストアルゴリズム）

1. グラフGが与えられたとき、 q ( ε ) = O (log(1/( ε δ ))/ ε ² )個の頂点からなるランダムな集合X を選択します。
2. Xのすべての頂点のペアについて、それらがGで隣接しているかどうかを問い合わせます。
3. GのX上の誘導部分グラフが二部グラフであれば受理し、そうでなければ拒否する。^{[ 4 ]}

例（k彩色可能性テストアルゴリズム）。

1. グラフGが与えられたとき、 q ( ε ) = O ( k ⁴ log ² ( k / δ )/ ε ³ )個の頂点からなるランダムな集合X を選択します。
2. Xのすべての頂点のペアについて、それらがGで隣接しているかどうかを問い合わせます。
3. GのX上の誘導部分グラフが k-彩色可能であれば受理し、そうでなければ拒否する。^{[ 4 ]}