ハイパーグラフにおける頂点被覆

すべてのハイパーエッジが接続されているハイパーグラフノードのセット

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

同義語としてヒッティング集合があります。集合の集合が与えられたとき、その集合内のすべての集合と少なくとも1つの要素で交差する集合をヒッティング集合と呼びます。この同義性は、集合内の集合をハイパーエッジに写像することで確認できます。

組み合わせ論的な文脈でより多く用いられる同義語として、横断的（transversal）という用語があります。しかし、横断的の定義によっては、ハイパーグラフのすべてのハイパーエッジに、その集合の頂点が1つだけ含まれていることが求められる場合もあります。

意味

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

$H$ の頂点被覆（別名、ヒッティング集合または横断集合）は $T$ $\subseteq$ $V$ と設定され、すべてのハイパーエッジ $e$ $\in$ $Eに対して$ $T$ $\cap$ $e$ $\neq$ $\emptyset$ が成り立ちます。

ハイパーグラフ $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]$ 完全である。つまり、最小のヒッティングセットの基数 $OPT$ に対して、時間 $f$ $(OPT)$ $n$ $O$ $(1)$ で実行されるアルゴリズムは存在しない可能性が高い。ヒッティングセット問題は、パラメータ $OPT +$ $d$ に対して固定パラメータで扱える。ここで、 $dはハイパーグラフの最大辺のサイズである。より具体的には、時間$ $d$ $OPT$ $n$ $O$ $(1)$ で実行されるヒッティングセットアルゴリズムが存在する。

ヒットセットとセットカバー

ヒッティング集合問題は集合被覆問題と同等である。集合被覆の例は任意の二部グラフとして捉えることができ、集合は左側の頂点で表され、集合の要素は右側の頂点で表され、辺は集合への要素の包含を表す。この場合の課題は、右側の頂点をすべて被覆する左側の頂点の最小基数部分集合を見つけることである。ヒッティング集合問題では、右側の頂点の最小基数部分集合を用いて左側の頂点を被覆することが目的である。したがって、ある問題から別の問題への変換は、2つの頂点集合を交換することによって実現される。

アプリケーション

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

分数頂点被覆

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

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

頂点被覆は分数頂点被覆の特殊なケースであるため、すべてのハイパーグラフ $H$ に対して次の式が成り立ちます。

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

記号で表すと:

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

ハイパーグラフの分数頂点被覆数は、一般にその頂点被覆数よりも小さい。ラースロー・ロヴァースの定理は、それらの比の上限を与えている。^[7]

各頂点が最大 $d 本の$ ハイパーエッジに含まれる場合（つまり、ハイパーグラフの次数が最大 $d$ の場合）、
${\frac {\tau (H)}{\tau ^{*}(H)}}\leq 1+\ln(d).$

有限射影平面における横線

有限射影平面とは、2つの超辺が交差する超グラフである。任意の有限射影平面は、ある整数 $rに対して$ $r$ -一様射影平面となる。r $-一様射影平面を$ $H$ $r$ で表す。以下の射影平面の存在が知られている。

$H 2$ : 単純な三角形のグラフです。
$H 3$ :ファノ平面です。
$p$ が素数のべき乗である $ときはいつでも、 H$ $p$ $+1$ が存在します。

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

$r 2 - r + 1 個$ の頂点と $r 2 - r + 1 個$ のハイパーエッジがあります。
これは $r$ 一様であり、各ハイパーエッジには正確に $r$ 個の頂点が含まれます。
これは $r$ 正則です。つまり、各頂点はちょうど $r$ 個のハイパーエッジに含まれます。
$τ (H r) = r$ :各ハイパーエッジ $eの$ $r頂点は$ $H$ $r$ の頂点カバーです(他のすべてのハイパーエッジは $e$ と交差するため)。
$サイズr$ の横断線はハイパーエッジのみであり、他のすべての横断線のサイズは少なくとも $r + 2$ です。
$τ *( H r ) = ν *( H ) = r – 1 + .mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num{display:block;line-height:1em;margin:0.0em 0.1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0.1em 0.1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}⁠1/r⁠$ 。
$ν (H r) = 1 :$ $H r$ 内のすべてのマッチングには最大で1つのハイパーエッジが含まれます。

最小横断線

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

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

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

参照

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

参考文献

^ ab ロヴァース、ラースロー;プラマー医学博士(1986 年)、『マッチング理論』、『離散数学年報』、第 1 巻。 29、北オランダ、ISBN 0-444-87916-1、MR 0859549
^ ベルゲ、クロード (1973). 『グラフとハイパーグラフ』アムステルダム: 北ホラント.
^ Khot, Subhash ; Regev, Oded (2008). 「頂点被覆を2−ε以内に近似することは難しいかもしれない」. Journal of Computer and System Sciences . 74 (3): 335– 349. doi : 10.1016/j.jcss.2007.06.019 .
^ フルム、ヨルグ;グローエ、マーティン(2006)。パラメータ化された複雑性理論。スプリンガー。ISBN 978-3-540-29952-3. 2025年7月30日閲覧。
^ O'Callahan, Robert; Choi, Jong-Deok (2003). 「ハイブリッド動的データ競合検出」. ACM SIGPLAN Notices . 38 (10): 167– 178. doi :10.1145/966049.781528.
^ O'Callahan, Robert; Choi, Jong-Deok (2003). 「ハイブリッド動的データ競合検出」.第9回ACM SIGPLANシンポジウム「並列プログラミングの原理と実践」の議事録. pp. 167– 178. doi :10.1145/781498.781528. ISBN 1-58113-588-2。
^ L. Lovász (1975). 「最適積分被覆と最適分数被覆の比について」.離散数学. 13 (4): 383– 390. doi :10.1016/0012-365X(75)90058-8. ISSN 0012-365X. Zbl 0323.05127. Wikidata Q56391140.
^ Füredi, Zoltán (1981-06-01). 「一様ハイパーグラフにおける最大次数と分数マッチング」 . Combinatorica . 1 (2): 155– 162. doi :10.1007/BF02579271. ISSN 1439-6912. S2CID 10530732.

[lp2-1] ロヴァース、ラースロー;プラマー医学博士(1986 年)、『マッチング理論』、『離散数学年報』、第 1 巻。 29、北オランダ、ISBN 0-444-87916-1、MR 0859549

[2] ベルゲ、クロード (1973). 『グラフとハイパーグラフ』アムステルダム: 北ホラント.

[kr08-3] Khot, Subhash ; Regev, Oded (2008). 「頂点被覆を2−ε以内に近似することは難しいかもしれない」. Journal of Computer and System Sciences . 74 (3): 335– 349. doi : 10.1016/j.jcss.2007.06.019 .

[4] フルム、ヨルグ;グローエ、マーティン(2006)。パラメータ化された複雑性理論。スプリンガー。ISBN 978-3-540-29952-3. 2025年7月30日閲覧。

[5] O'Callahan, Robert; Choi, Jong-Deok (2003). 「ハイブリッド動的データ競合検出」. ACM SIGPLAN Notices . 38 (10): 167– 178. doi :10.1145/966049.781528.

[6] O'Callahan, Robert; Choi, Jong-Deok (2003). 「ハイブリッド動的データ競合検出」.第9回ACM SIGPLANシンポジウム「並列プログラミングの原理と実践」の議事録. pp. 167– 178. doi :10.1145/781498.781528. ISBN 1-58113-588-2。

[7] L. Lovász (1975). 「最適積分被覆と最適分数被覆の比について」.離散数学. 13 (4): 383– 390. doi :10.1016/0012-365X(75)90058-8. ISSN 0012-365X. Zbl 0323.05127. Wikidata Q56391140.

[:2-8] Füredi, Zoltán (1981-06-01). 「一様ハイパーグラフにおける最大次数と分数マッチング」 . Combinatorica . 1 (2): 155– 162. doi :10.1007/BF02579271. ISSN 1439-6912. S2CID 10530732.