ISを使用してexact2isを解く

Question

私は次の問題を検出しました：

expey2is= {Gは正確に2つの独立したセットを持っています}

グラフGを与えられたと仮定して、Gが独立したセットを見つけることができるのは、Gが正確に2つの独立したセットを持っているかどうかをチェックすることができます。

（グラフがO（1）で独立した設定を含むかどうかを確認でき、O（1）

でも独立したセットを見つけることができます。

私はサイズkのいくつかの独立したセット（ある場合）を見つけて、セットから1つの頂点を削除し、それでもグラフのサイズkの独立したセットがあるかどうかを確認しています。 - 私はそれがあったのとおりに頂点をグラフに戻すことをチェックします。

問題の問題点は、グラフGに少なくとも2つの独立したセットが含まれておらず、正確にはない場合にのみチェックします。

だれでも、グラフが正確に2つの独立したセットを持っているかどうかを確認する方法を考えています（多項式の時間内に、独立したセットがあるかどうかを見つけて確認し、チェックして確認しているという事実を考えると、（1））。

手がかりやアイデアが高く評価されます:) ありがとう

Answer 1

まず、グラフ $ g $ のどちらがin独立したサイズのセットを含む $ k $ 、そのような設定を効率的に見つけることもできます。これは「検索対決定縮小」として知られています。これが基本的な考えです。任意の頂点 $ v $ を選択して、それを削除します。まだグラフに依然として $ k $ の独立したセットがある場合は、続きます。それ以外の場合は、すべての独立したサイズ $ k $ に含まれています $ v $ が含まれています。したがって、 $ v $ とそのすべての隣人を削除し、独立したサイズのセットを見つけ、 $ k-1 $ 残りのグラフに。このようにして、独立したサイズのセットを回復することができます $ k $ 。

2次、グラフに少なくとも 2つの独立したサイズ $ k $ を含むかどうかを確認する方法 $ k \ geq 2 $ 。まず、INに少なくとも1つが含まれているかどうかを判断します。 $ i $ を指定するとします。 $ J $ の場合、 $ i \ setminus j $ と $ J \ SetMinus i $ の両方がensettyです（ $ |= | j | $ ）。特に、 $ x \ in i \ setminus j $ および $ Y $ の場合、その他の頂点 $ i $ 、それでもエッジ $（x、y）$ を追加した後でも、set $ J $ は独立したセットを構成します。

これは次のアルゴリズムにつながります。 $ x、y \ in i $ の各ペアの場合は、には、独立したサイズ $ k $ が含まれています。もしそうであれば、この独立したセットは必然的に $ i $ とは異なります。逆に、 $ k $ の独立したセットが存在する場合は、必ず必ずそれが必ず $ g +（x、y）$ の独立したセットになる $ x、y \ in i $ 。

3番目のグラフにが含まれているかどうかを確認する方法 2つの独立したサイズ $ k $ 。これは、グラフが少なくとも 3つの独立したセットを含むかどうかを確認するのと同じです。この時点で、上記の議論を2つから3つの独立したセットに一般化しようとすると、それが良いと思います。あなたは立ち往生するかもしれませんが、あなたが試すまであなたはわかりません。

Answer 2

find ANを許可されている場合 $ \ \ \ \ \ \ \ \Mathcal O（1）$ 、それであなたが書いたことは の解決策です。2回わずかANはサイズ $ k $ 、その後、まだ別のものがあるかどうかを確認するためのチェックの後に2回です。

通常、Oracleマシンの場合は、（この例では） $ \ mathcal o（1）$ 時間内にあります。 $ \ mathcal o（1）$ 内のが存在する場合にのみチェック>。

これが助けになることを願っています！