從頂點覆蓋減少來證明NP完全

Question

我們定義ROMAN-SUBSET如下面的問題：

INPUT：向圖G =（V，E）和一個正整數k

OUTPUT：如果有一個V的子集R，使得| R |使得G中的每個定向電路包括來自R的至少一個頂點 ，那麼輸出應該是「真」，否則它應該是 「假」。

假設頂點覆蓋（VC）問題是NP完全的，我必須證明ROMAN-SUBSET也是NP-完全的。根據我的理解，這意味着接受VC輸入，修改它，然後顯示將它插入ROMAN-SUBSET算法會產生VC問題的結果。

我正在經歷一段非常艱難的時期。我知道VC輸入是圖G和整數k，問題在於是否存在覆蓋G中每個邊的V的子集R，使得| R | < = k。很明顯，R和k在ROM和VC之間是相似的，但是我的困難在於確定如何變換圖形，使得每個定向週期（對於ROM）中的1個頂點對應於每個邊緣（對於VC）。我怎樣才能修改圖形來證明VC可以簡化爲ROM？

謝謝！

Answer 1

這是施工。

以VC中無向圖G = (V, E)爲準。 現在定義有向圖G1 = (V, E1)，其中對於E中的每個邊緣(u,v)，在E1中存在兩條邊(u,v)和(v,u)。

換句話說，新圖形與舊圖形相同，但是每個無向邊緣被替換爲形成2個週期的兩個有向邊緣。

聲明是從ROM上G1跟在G VC上。

事實上，假設G1上ROM的答案爲FALSE。然後，對於一組小於k頂點的每個選擇，存在不在該組中的循環。所以存在一個邊緣的終點不在集合中。但是這意味着對於在中對於小於k頂點集合的相同選擇存在邊緣，其端點不在集合中，所以VC的答案是FALSE。

相反，假設G1上ROM的答案爲TRUE。那麼存在一個包含小於k頂點的子集，因此給定任何循環，在該循環中至少存在一個頂點。但是這意味着對於該集合中的其中一個端點，因爲E中的邊緣對應於E1中的2個週期。因此VC的答案是TRUE。