前にこのようなNPグラフの問題を見たことがある人がいますか？

Question

次のグラフベースの問題があります。

1. 入力：正整数kとl、無向グラフG
2. このグラフからk個の頂点を選択する必要があります
3. 選択されたk頂点の各対の経路では、少なくともl頂点がなければならない、i。e。少なくともL個の頂点からなる選択された頂点のうちの2つの2つの2つの間のスペースがなければならない。

上記の問題点の一部の例では不可能な場合があります。この問題は、長さ制約を持つパスと関係がある必要があるため、この問題はNPまたはNP完了であることを非常に確信しています。あなたは同様の問題を満たしたことがありますか？あなたはそれをいくつかのよりよく知られている問題に縮小する方法、おそらくnp、e。g。頂点カバーまたはグラフの着色？

また、私のグラフはグリッドグラフで、これは完全な長方形のグリッドのサブグラフです。

Answer 1

これは距離 $ d $ 独立したセット、つまり、あなたは独立したサイズのセットを探しています $ K $ 解決策内の2つの要素ごとの間の距離は、少なくとも $ d $ です。

問題は[1]に準拠した平面グラフでもNP-Completeですが、部分的なグリッドの複雑さについてはわかりません。

削減に関しては、おそらく $ d $ 'th グラフの電源とその中に独立した（距離-1）を見つけます。クレームは、ここでの解決策が距離 $ d $ 独立したセットであるということですが、これを検証する必要があります。

---

[1] Eto、Hiroshi、Fengrui Guo、宮野恵平。 "距離 $ d $ バイパリットおよび弦グラフの独立した設定の問題。」コンビナトリアル最適化のジャーナル27、NO。 1（2014）：88-99。

Answer 2

$ L= 1 $ の特別な場合では、これは最大独立セットの問題は、一般的なグラフではNPハードです。したがって、あなたの問題は一般的なグラフでもNPハードです。

あなたが持っているグラフのクラスに固有のアルゴリズムを願うことを試みることができました（最大の独立したセットバイパリットグラフで効率的に計算することができ、グリッドグラフはバイアルタイトであるため、そのアルゴリズムを一般化するか、または最大限の独立したセット/クリークのために標準アルゴリズムを使用してみることができます。ソルバー。これをMAXSATインスタンスとして定式化するのは簡単なはずです。距離 $ L + 1 $ （またはそれ以降）内にある頂点の各ペアの句があります。 TRUEに設定されている変数の数を最小限に抑えるためにSATソルバーに依頼します。

Answer 3

グラフの色素問題の規則を使用して、gのk頂点サブグラフがあるかどうかをチェックするようです。すべてのk個の頂点が同じ色で着色されている場合は、UR状態を満たしています。

NP完成品でのグラフの着色は、多項式時刻の所与の解を検証することができます。

だから、たぶん、これは最初の視力の答え、uは

1チェックURグラフがL色付け可能な場合

2 - k個の頂点を有する色を探す