小集合拡張仮説

計算複雑性理論における小集合拡張仮説（または小集合拡張予想）は、証明されていない計算困難性の仮定である。小集合拡張仮説の下では、「小集合拡張グラフ」と呼ばれる特定のクラスの拡張グラフと、小集合拡張グラフとはかけ離れた他のグラフを区別することは、計算上不可能であると仮定されている。この仮定は、他のいくつかの計算問題の困難性、および既知の近似アルゴリズムの最適性を暗示している。

小集合拡張仮説は、ユニークゲーム予想と関連している。ユニークゲーム予想とは、特定のゲームの値を正確に近似することは計算上不可能であるという、もう一つの未証明の計算困難性仮説である。小集合拡張仮説が正しいならば、ユニークゲーム予想も正しいことになる。

集合の辺の拡張${\displaystyle X}$グラフの頂点の数${\displaystyle G}$は次のように定義される。$${\displaystyle {\frac {|\partial X|}{|X|}},}$$ ここで縦棒は集合の要素数を表し、${\displaystyle \partial X}$は、1 つの端点が${\displaystyle X}$そしてその補数におけるもう一方の端点。^{[ a ]}この数値は、0 まで小さくなることがあります。${\displaystyle X}$これはグラフの連結成分です。なぜなら、この場合、接続するエッジがないからです。${\displaystyle X}$グラフの他の部分へ。グラフは正則または${\displaystyle d}$-すべての頂点が同じ数の辺に接続されている場合は正則、${\displaystyle d}$グラフの次数。${\displaystyle d}$-正則グラフの場合、最大可能なエッジ拡張は${\displaystyle d}$この拡張は任意の部分集合によって達成される。${\displaystyle X}$これは独立集合を誘導する。この場合、頂点に接するすべての辺が独立集合となる。${\displaystyle X}$に属する${\displaystyle \partial X}$[ ^{1 ] [ 2 ]​}

グラフのエッジ拡張${\displaystyle n}$頂点は、最大で のサブセットの中で最小のエッジ拡張として定義されます。${\displaystyle n/2}$頂点。^{[ b ]}代わりに、小集合拡張は同じ最小値として定義されますが、最大でより小さな部分集合のみを対象とします。${\displaystyle n/\log _{2}n}$頂点。非公式には、小集合拡張グラフとは、小集合拡張が大きいグラフのことである。^{[ 1 ] [ c ]}

小集合拡張仮説は実数を使用する${\displaystyle \varepsilon }$グラフの小集合拡張が大きいか小さいかを形式化するためのパラメータとして。これは、すべての${\displaystyle \varepsilon >0}$を区別するのはNP困難である${\displaystyle d}$-少なくとも小さな集合拡張を持つ正則グラフ${\displaystyle (1-\varepsilon )d}$（優れた小型セット拡張版）${\displaystyle d}$-最大で小さな集合拡張を持つ正則グラフ${\displaystyle \varepsilon d}$（小さな集合拡張器とは程遠い）。ここで、次数は${\displaystyle d}$は、選択によって変わる可能性のある変数です。${\displaystyle \varepsilon }$次数が固定定数であると仮定される多くのエキスパンダーグラフの応用とは異なります。^{[ 1 ] [ c ]}

小集合拡張仮説は、他のいくつかの計算問題がNP困難であることを示唆している。これは仮説に過ぎないため、これらの問題が実際にNP困難であることを証明するものではない。しかし、これらの問題のいずれかを解けば、これまで解けていない他の問題（小集合拡張問題自体を含む）も解けることになるため、これらの問題に対する効率的な解法を見つけるのは難しいことを示唆している。逆に、この示唆は、小集合拡張仮説を攻撃できる他の問題を提供することで、小集合拡張仮説を反証する道を開く。^{[ 1 ]}

特に、小集合拡張子の認識からユニークゲームの近似値を決定する問題への多項式時間還元が存在し、小集合拡張仮説がユニークゲーム予想を含意することを示している。^{[ 1 ] [ 2 ]}ボアズ・バラクは、これら2つの仮説が同等であるとより強く示唆している。^{[ 1 ]}実際、小集合拡張仮説は、基となるグラフが小集合拡張子であるユニークゲームインスタンスの困難性を主張する、ユニークゲーム予想の制限された形式と同等である。^{[ 3 ]}一方、グラフが「確実に」小集合拡張子であるユニークゲームインスタンスは、その拡張が二乗和最適化によって検証できるという意味で、迅速に解くことができる。^{[ 4 ]}

小集合拡張仮説のもう1つの応用例は、グラフのツリー幅を近似する計算問題に関するもので、ツリー幅は拡張と密接に関連する構造パラメータです。ツリー幅が のグラフの場合${\displaystyle w}$多項式時間近似アルゴリズムで知られている最良の近似比は${\displaystyle O({\sqrt {\log w}})}$[ ^{5 ]}小集合拡張仮説が真であれば、この問題に対して一定の近似比を持つ近似アルゴリズムは存在しないことを意味する。^{[ 6 ]また}、より大きなグラフにおいて、最大数のエッジを持つ完全な二部グラフ（二部グラフの両側の頂点数が等しいという制約がある場合も含む）を見つけることが近似不可能であることを示唆するためにも使用できる。^{[ 7 ]}

小集合拡張仮説は、グラフ内の与えられた数のエッジを覆うためにできるだけ少ない頂点を選択する必要があるエッジ被覆問題の特定の変種に対して、既知の近似比が最適であることを示唆している。^{[ 8 ]}

小集合拡張仮説は、2010年にプラサード・ラガヴェンドラとデイビッド・シュトゥーラーによって定式化され、ユニークゲーム予想と関連付けられました^{[ 2 ]。}これは、彼らが2018年に米国科学アカデミーのマイケル・アンド・シーラ・ヘルド賞を受賞した一連の研究の一部です^{[ 9 ]}。

小集合拡張仮説を解決する一つのアプローチは、仮説における2種類のグラフを区別するのに十分な精度を持つ、小さな頂点集合の辺拡張に対する近似アルゴリズムを探すことである。この観点から、最大で のサブセットの辺拡張に対する既知の最良の近似は、${\displaystyle n/\log n}$頂点${\displaystyle d}$-正則グラフ、近似比は${\displaystyle O({\sqrt {\log n\log \log n}})}$これは仮説を反証するには十分強力ではない。反証するには、近似比が制限されたアルゴリズムを見つける必要がある。^{[ 10 ]}