頂点被覆
頂点被覆はハイパーグラフにも自然に一般化でき、単に「ハイパーグラフの頂点被覆」とも呼ばれるが、ヒッティングセット (hitting set) という呼び方が一般化している。また、組合せ論的には横断 (transversal) とも呼ぶ。さらに言えば、ヒッティングセットと集合被覆は等価である。
形式的には、ハイパーグラフ H=(V,E) は頂点集合 V とハイパーエッジ集合 E から成る。集合 S ⊆ V がヒッティングセットとなるのは、全てのハイパーエッジ e ∈ E について S ∩ e ≠ ∅ が成り立つ場合である。計算問題としての「最小ヒッティングセット」と「ヒッティングセット問題」はグラフの場合と同様に定義される。
なお、ハイパーエッジの最大サイズが2のハイパーグラフは普通のグラフと同じである。ハイパーエッジの大きさを d までに制限すると、最小d-ヒッティングセットを求める問題にはd-近似アルゴリズムがある。
ヒッティングセット問題は集合被覆問題と等価である。集合被覆問題の具体例は、左側に集合を頂点として置き、右側に全ての元を頂点として置き、元と集合の包含関係を辺で表した2部グラフで表すことができる。すると問題は、右側の頂点を全て被覆する左側の頂点の最小濃度の部分集合を求めることとなる。ヒッティングセット問題では、左側の頂点を全て被覆する右側の頂点の最小濃度の部分集合を求めることである。したがって、頂点の左右を入れ替えると全く同じ問題であることがわかる。