始めるのが難しいと感じている宿題の問題があります。扱いにくいことを示すために、Karp (シングル コール) 削減に取り組んでいます。この課題では、問題は意図的にあいまいです。ここの誰かがそれを知っているか、私が始めるのに役立つ解決策の例を提供できることを望んでいました.
問題は、提供されたコードでのみ説明されています。次のコンポーネントがあります。
B = (G, T, k) ここで、B は「Blah」問題のインスタンス、G = (V,E) はグラフ (重みなし、無向)、T は V の頂点のサブセット、k は整数。B の証明書は、G のサブグラフ S = (V', E') を返します。yes インスタンスの検証子も提供されます。
はいのインスタンス
forall [t in T], there exists some edge [e in E'] s.t. t is an endpoint of e
and, the number of edges of S is at most k (|E'| <= k)
and, S is a connected graph
この問題と Independent-Set または Vertex-Cover の問題との間にいくつかの類似点があります。これらは扱いにくいことを示すために還元するのに適した候補だと思いますが、まだ問題を十分に理解していません。この問題に関する議論がどこかにある場合、または誰かがいくつかの例を提供できる場合は、大いに感謝します。ありがとうございました！