Hitting Set Problem (HS) definieras enligt följande. Låt $ (C, k $)
- $ C = \ {S_1, S_2, …, S_m \} $ samling av delmängd av S dvs $ S_i \ subseteq S, \ forall i $
- $ k \ in \ mathbb {N} $
Vi vill veta om det finns $ {S} ”\ delmängd S $ där $ | {S} ”| < k $ så att $ S_i \ cap S ”\ neq \ emptyset $, $ i = 1,2, …, m. $
Visa att HS är Np-komplett.
Tips : När $ | S_i | = 2 $, HS blir Vertex Cover, vet redan att vara NP-komplett.
Kommentarer
- Vad försökte du? Var gjorde du fastnar? Vi ' hjälper dig gärna att förstå begreppen men det är osannolikt att bara lösa övningar åt dig. Du kanske hittar den här sidan till hjälp för att förbättra din fråga.
Svar
3SAT reduceras till Hitting Ställ in problem. Med en 3SAT $ \ phi $ med $ m $ -klausuler och $ n $ -variabler, definiera
$$ S = \ {x_1, \ dots x_n, \ overline {x_1}, \ dots, \ overline {x_n} \} $$ $$ S_i = \ {y_1, y_2, y_3 \}, \ text {if} y_1, y_2, y_3 \ i S \ text {och} (y_1 \ lor y_2 \ lor y_3) \ text {är en klausul.} $$ $$ S_x = \ {x, \ överlinje {x} \}, \ text {för alla variabel} x. $$ $$ $$ k = n $$
Antag att $ \ phi $ är tillfredsställande, då finns det en tilldelning av sant värde för $ n $ -variabler. Så lägg till $ x $ till $ S ”$ om $ x = true $, annars lägg till $ \ overline {x} $ till $ S” $.
Antag nu att HS-problemet har en lösning $ S ”$. Sedan sedan för varje variabel $ x $, $ S” \ cap S_x \ neq \ emptyset $, $ S ”$ har minst $ n $ bokstäver av formen $ x $ eller $ \ overline {x} $ för varje variabel $ x $. Dessutom får ingen $ x $ och $ \ overline {x} $ tillhöra $ S ”$ samtidigt eftersom storleken på $ S” $ är högst $ n $. varje sats $ C_i $, $ S ”\ cap S_i \ neq \ emptyset $ och så för varje sats väljer vi $ y_i \ i S” \ cap S_i $ och ställer in $ x = true $ om $ y_i = x $ och $ x = false $ om $ y_i = \ överlinje {x} $.
Kommentarer
- kan du visa en positiv och en negativ instans?
Svar
Det är lätt att visa att Hitting Set är i NP. En lösning behöver bara visa uppsättningen H – man kan enkelt verifiera i polynomtid om H är av storlek k och skär var och en av uppsättningarna B1, …, Bm.
Vi minskar från toppkåpan. Tänk på en förekomst av toppunkten täckproblem – diagram G = (V, E) och ett positivt heltal k. Vi kartlägger det till en instans av träffuppsättningsproblemet enligt följande. Uppsättningen A är uppsättningen av hörn V. För varje kant e ∈ E har vi en uppsättning Se som består av de två slutpunkterna för e. Det är lätt att se att en uppsättning hörn S är ett topphölje på G iff motsvarande element bildar en träffuppsättning i träffuppsättningen.
Kommentarer
- Välkommen till ComputerScience @ SE. Intressant användning av specialsymbol
∈– det är vanligt att använda MathJax, vilket tillåter till exempel korrekt prenumeration: $ B_1, \ dots, B_m $. - vad händer om storleken på Se är större än 2? Kommer det att fungera?
Svar
Hitting Set Problemet motsvarar Set Cover Problem, det är definierat enligt följande:
INGÅNG: en samling C av underuppsättningar av en ändlig uppsättning S.
LÖSNING: En uppsättning omslag för S, dvs en delmängd $ C ”\ subseteq C $ sådan att varje element i S tillhör minst en medlem av $ C ”$.
Med tanke på $ k $ finns det en uppsättning täcker $ C” $ så att $ \ vert C ”\ vert \ leq k $?
Detta ser ut som en läxa, så jag låter dig ta reda på hur, med en instans av Set Cover kan du konvertera den till en motsvarande instans av Hitting Set.
Annars, om du vill följa ledtråden, först visar du att Hitting Set in i $ NP $, som ges en lösning som du kan verifiera den i polynom-tid.
Sedan visar du att med en graf $ G = (V, E) $, att hitta ett topplock i storlek $ k $ motsvarar att hitta en träffsats med storlek $ k $. Det vill säga, om $ | E | = m $, kan du skapa en träffsatsinstans med samma mängd uppsättningar.