カバーリングの問題

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

一部の被覆問題では、被覆が追加の要件を満たす必要があります。特に、レインボー被覆問題では、元の各オブジェクトに「色」があり、被覆には各色のオブジェクトがちょうど 1 つ (または最大 1 つ) 含まれていることが求められます。レインボー被覆は、例えば区間による点の被覆について研究されています。^{[ 5 ]}

• 実数直線上には、 n 個の色付き区間の集合Jと、実数直線上の点の集合Pが存在する。
• Jの部分集合Qは、各色の区間を最大で1つしか含まない場合、レインボー集合と呼ばれる。
• 区間の集合Jは、 Pの各点がQの少なくとも 1 つの区間に含まれる場合、 Pの被覆と呼ばれます。
• レインボーカバリング問題とは、 Pを覆うレインボー集合Qを見つける問題である。

この問題はNP困難である（線形SATからの還元による）。

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

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

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

• 幾何学的被覆問題が固定パラメータ扱い可能（FPT）である場合、衝突のない幾何学的被覆問題もFPTである。
• 幾何学的被覆問題がr近似アルゴリズムを許容する場合、衝突のない幾何学的被覆問題もFPT時間で同様の近似アルゴリズムを許容する。