問題を隠す

組合せ論とコンピュータ サイエンスにおいて、被覆問題とは、ある組合せ構造が別の組合せ構造を「被覆」するかどうか、または被覆するにはその構造がどの程度の大きさでなければならないかを問う計算問題です。被覆問題は最小化問題であり、通常は整数線形計画問題であり、その双対問題はパッキング問題と呼ばれます。

被覆問題の最も顕著な例は、ヒット集合問題と同等の集合被覆問題と、その特殊なケースである頂点被覆問題および辺被覆問題である。

被覆問題では、被覆プリミティブの重なりが許可されます。重なり合わないプリミティブで何かを覆うプロセスは、分解と呼ばれます。

線形計画法の文脈では、制約行列、目的関数、右辺の係数が非負であれば、任意の最小化線形計画法を被覆問題として考えることができます。^{[1]より正確には、次の一般的な}整数線形計画法を考えます。

このような整数線形計画法は、すべてのおよびに対して である場合、被覆問題と呼ばれます。 ${\displaystyle a_{ji},b_{j},c_{i}\geq 0}$${\displaystyle i=1,\dots ,n}$${\displaystyle j=1,\dots ,m}$

直感:オブジェクトの型があり、 の各オブジェクトにはの関連コストがあると仮定します。この数字は、購入するのオブジェクトの数を示します。制約が満たされている場合、 は被覆であると言えます(被覆される構造は、組み合わせコンテキストによって異なります)。最後に、上記の整数線形計画法の最適解は、最小コストの被覆です。 ${\displaystyle n}$${\displaystyle i}$${\displaystyle c_{i}}$${\displaystyle x_{i}}$${\displaystyle i}$${\displaystyle A\mathbf {x} \geq \mathbf {b} }$${\displaystyle \mathbf {x} }$

グラフ理論、計算幾何学などにはさまざまな種類の被覆問題があります。カテゴリ:被覆問題を参照してください。この問題の他の確率的関連バージョンも見つかります。^[2]

ペトリ ネットの場合、被覆問題は、特定のマーキングに対して、より大きな (または同等の) マーキングに到達できるようなネットの実行が存在するかどうかという問題として定義されます。ここで「より大きい」とは、すべてのコンポーネントが特定のマーキングのコンポーネントと少なくとも同じ大きさであり、少なくとも 1 つが適切に大きいことを意味します。

いくつかの被覆問題では、被覆はいくつかの追加要件を満たす必要がある。特に、虹被覆問題では、元のオブジェクトのそれぞれが「色」を持ち、被覆には各色のオブジェクトが正確に1つ（または最大で1つ）含まれている必要がある。虹被覆は、例えば区間による点の被覆について研究された：^[3]

• 実数直線上にはn 個の色付き区間の集合Jがあり、実数直線上には点の集合P があります。
• JのサブセットQ は、 各色の間隔が最大で 1 つだけ含まれる場合、レインボー セットと呼ばれます。
• P内の各点がQの少なくとも 1 つの区間に含まれる場合、区間の集合JはPの被覆と呼ばれます。
• レインボーカバーリング問題は、 PのカバーであるレインボーセットQを見つける問題です。

この問題はNP 困難です (線形 SATからの削減により)。

より一般的な概念は衝突のない被覆である。^[4]この問題では、

• m 個のオブジェクトの集合Oと、 O上の競合グラフG _Oが存在します。
• OのサブセットQがG _O内の独立セットである場合、つまりQ内の 2 つのオブジェクトがG _O内のエッジで接続されていない場合、そのサブセットは競合がないと呼ばれます。
• レインボー セットは、 G _{O が}互いに素なクリークで構成され、各クリークが色を表す特殊なケースにおける競合のないセットです。

衝突のない集合被覆は、 Pの被覆であるOの衝突のない部分集合を見つける問題である。Banik、Panolan、Raman、Sahlot、Saurabh ^{[5]は、衝突グラフが有界}樹状性を持つ特別なケースについて以下を証明する。

• 幾何学的カバー問題が固定パラメータで処理可能 (FPT) である場合、競合のない幾何学的カバー問題は FPT です。
• 幾何学的カバー問題が r 近似アルゴリズムを許容する場合、競合のない幾何学的カバー問題も FPT 時間で同様の近似アルゴリズムを許容します。