NP完全問題を証明する

次の問題があるとします。

無向グラフG =(V、E)が与えられると、頂点集合Vの部分集合V
‘を選択することが可能であり、それにより、削除は全ての三角形(長さ3のサイクル)を除去する。多くてもkですか?

どのようにして頂点カバー問題からそのような問題に縮小することができますか?

ベストアンサー

元のVCインスタンスのすべてのエッジ$(e_1、e_2)$に対して、エッジに$(e_1、e_2)$、$(e_1、e_
{12})$、$(e_ {12}、e_2)あなたの問題のインスタンスの

問題にサイズKの解が存在する場合、元のVCインスタンスにサイズKの頂点カバーが存在します。我々はそれを見る:

=> : any vertex cover necessarily breaks all triangles
already existing in the original graph of the VC instance, and also
all newly created triangles in the new instance of your
problem.

<= : given a set of nodes breaking all triangles in the new
instance of your problem, for all nodes of the form $e_{ij}$
included in the set, replace it by $e_i$ or $e_j$. The resulting
set of nodes will cover all edges in the original graph.

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です