ハイパーグラフの頂点被覆

グラフ理論において、ハイパーグラフの頂点被覆とは、ハイパーグラフのすべてのハイパーエッジがその集合の頂点を少なくとも1つ含むような頂点の集合である。これはグラフの頂点被覆の概念の拡張である。 ^{[1] : 466–470  [2]}

同義語は「ヒット セット」です。セットのコレクションが与えられたとき、コレクション内のすべてのセットと少なくとも 1 つの要素で交差するセットはヒット セットと呼ばれます。コレクション内のセットをハイパーエッジに マッピングすると、同義であることが分かります。

組み合わせ論的な文脈で使用される別の同等の用語は、横断的です。ただし、横断の定義によっては、ハイパーグラフのすべてのハイパーエッジに、その集合の頂点が 1 つだけ含まれていることが要求されます。

ハイパーグラフ Hは( V、E )のペアであり、Vは頂点の集合、E はハイパーエッジと呼ばれるVのサブセットの集合であることを思い出してください。各ハイパーエッジには 1 つ以上の頂点が含まれます。

Hの頂点被覆（別名、ヒッティング集合または横断集合）はT ⊆ Vにセットされ、すべてのハイパーエッジe ∈ Eに対して、 T ∩ e ≠ ∅が成り立ちます。

ハイパーグラフHの頂点被覆数（横断数ともいう）は、 Hにおける頂点被覆の最小サイズである。これはτ ( H )と表記されることが多い。^{[1] : 466}

たとえば、H が次の 3 次元均一ハイパーグラフである場合:

{ {1,2,3}、{1,4,5}、{4,5,6}、{2,3,6} }

すると、H にはサイズ 2 の頂点被覆が複数存在します。たとえば、次のようになります。

{1, 6}

しかし、サイズ 1 のサブセットはHのすべてのハイパーエッジにヒットしません。したがって、 Hの頂点カバー数は2 です。

ハイパーエッジの最大サイズが 2 の場合、単純なグラフの頂点カバーのケースに戻ることに注意してください。

計算問題である最小ヒットセットとヒットセットは、グラフの場合と同様に定義されます。

ハイパーエッジの最大サイズがdに制限されている場合、最小のdヒットセットを見つける問題はd近似アルゴリズムを可能にします。ユニークゲーム予想を仮定すると、これは可能な最良の定数因子アルゴリズムであり、そうでない場合はd − 1への近似を改善する可能性があります。^[3]

ヒッティングセット問題では、異なるパラメータ化が意味をなします。^[4]ヒッティングセット問題は、パラメータOPTに対してW [2]完全です。つまり、f (OPT) n ^{O (1)}の時間で実行されるアルゴリズムが存在する可能性は低いです。ここで、OPT は最小のヒッティングセットの基数です。ヒッティングセット問題は、パラメータOPT + dに対して固定パラメータで扱いやすいです。ここで、d はハイパーグラフの最大エッジのサイズです。より具体的には、 d ^OPT n ^{O (1)}の時間で実行されるヒッティングセットのアルゴリズムが存在します。

ヒット集合問題は、集合被覆問題と同等です。集合被覆のインスタンスは、任意の二部グラフとして考えることができます。集合は左側の頂点で表され、ユニバースの要素は右側の頂点で表され、エッジは集合内の要素の包含を表します。この場合のタスクは、右側の頂点をすべてカバーする左側の頂点の最小基数サブセットを見つけることです。ヒット集合問題では、右側の頂点の最小サブセットを使用して左側の頂点をカバーすることが目的です。したがって、1 つの問題から別の問題への変換は、2 つの頂点セットを交換することによって実現されます。

ヒッティングセット問題に関する実際の応用例として、競合状態の効率的な動的検出が挙げられます。^{[5] [6]}この場合、グローバルメモリが書き込まれるたびに、現在のスレッドとそのスレッドが保持するロックのセットが保存されます。ロックセットベースの検出では、後で別のスレッドがその場所に書き込み、競合がない場合、それは以前の書き込みのそれぞれと共通のロックを少なくとも 1 つ保持しているためです。したがって、ヒッティングセットのサイズは、競合が発生しない最小のロックセットサイズを表します。これは、実際には大きなロックセットは発生しないと考えられるため、冗長な書き込みイベントを排除するのに役立ちます。

分数頂点カバーは、Eのすべてのハイパーエッジeについて、 eの頂点の分数の合計が少なくとも 1 になるように、 Vの各頂点に[0,1]の重みを割り当てる関数です。頂点カバーは、すべての重みが 0 または 1 である分数頂点カバーの特殊なケースです。分数頂点カバーのサイズは、すべての頂点の分数の合計です。

ハイパーグラフHの分数頂点被覆数は、Hにおける分数頂点被覆の最小サイズである。これはτ *( H )と表記されることが多い。

頂点被覆は分数頂点被覆の特殊なケースなので、すべてのハイパーグラフHに対して次のようになります。

頂点被覆数( H ) ≤ 頂点被覆数( H );

記号で表すと:

${\displaystyle \tau^{*}(H)\leq \tau(H).}$

ハイパーグラフの分数頂点被覆数は、一般にその頂点被覆数よりも小さい。László Lovászの定理は、それらの比率の上限を示している。^[7]

• 各頂点が最大d個のハイパーエッジに含まれる場合（つまり、ハイパーグラフの次数が最大dの場合）、

  ${\displaystyle {\frac {\tau (H)}{\tau ^{*}(H)}}\leq 1+\ln(d).}$

有限射影平面は、2 つのハイパーエッジがすべて交差するハイパーグラフです。すべての有限射影平面は、ある整数rに対してr一様です。r 一様射影平面を H r で表します。次の_射影平面が存在することが知られています。

• H ₂ : 単純な三角形のグラフです。
• H ₃ : それはファノ平面です。
• p が素数の累乗であるときはいつでもH _{p +1}が存在する。

Hr_が存在する場合、それは以下の性質を持つ：^[8]

• r ² – r + 1 個の頂点とr ² – r + 1 個のハイパーエッジがあります。
• これはr一様であり、各ハイパーエッジには正確にr 個の頂点が含まれます。
• これはr正則です。つまり、各頂点はちょうどr個のハイパーエッジに含まれます。
• τ ( H _r ) = r :各ハイパーエッジ eのr頂点はH _rの頂点カバーです(他のすべてのハイパーエッジはe と交差するため)。
• サイズrの横断線はハイパーエッジのみです。他のすべての横断線のサイズは少なくともr + 2です。
• τ *( H _r ) = ν *( H ) = r – 1 + ⁠1/r⁠ .
• ν ( Hr )=1 : Hr内のすべてのマッチング_には最大で1つのハイパーエッジが含まれます。

頂点被覆 (横断的) T は、 Tの適切な部分集合が横断的で ない場合に極小であると呼ばれます。

Hの横断ハイパーグラフは、ハイパーエッジ集合FがHのすべての最小横断で構成されるハイパーグラフ( X、F )です。

横断的ハイパーグラフの計算は、組み合わせ最適化、ゲーム理論、機械学習、データベースのインデックス作成、満足度問題、データマイニング、コンピュータプログラムの最適化など、コンピュータサイエンスのさまざまな分野で応用されています。

• ハイパーグラフにおけるマッチング- 頂点カバーとマッチングの二重性についても説明します。