グラフGと整数Kの形式で入力を受け取り、GがK頂点接続されているかどうかを判断する多項式時間アルゴリズムを考え出すことを検討しています。これは深さ優先探索を利用する可能性が高いと思います。多項式のないソリューションでは、どのようにゼロになるかがわかります。つまり、K個のランダムな頂点を削除し、DFSを実行して接続を確認してから、別の頂点のグループで再度実行します。ただし、〜O（n ^ K）の実行時間は少し長く、これを多項式時間に下げることは明らかに可能です。私がここで何を見逃しているのか分かりますか？DFSを実行した後に取得する非ツリー頂点と関係があると思いますが、何を探しているのか完全にはわかりません。前もって感謝します！
編集：明確にするために、私はグラフの接続性を決定することを探していません。むしろ、入力に数値kが与えられ、グラフがk接続されているかどうかを確認しようとしています。グラフの接続性を示す答えは生成されません。「はい」または「いいえ」だけです。