Il Hitting Set Problem (HS) è definito come segue. Sia $ (C, k $)
- $ C = \ {S_1, S_2, …, S_m \} $ raccolta del sottoinsieme di S cioè $ S_i \ subseteq S, \ forall i $
- $ k \ in \ mathbb {N} $
Vogliamo sapere se esiste $ {S} “\ subset S $ dove $ | {S} “| < k $ tale che $ S_i \ cap S “\ neq \ emptyset $, $ i = 1,2, …, m. $
Dimostra che HS è Np-Complete.
Suggerimento : Quando $ | S_i | = 2 $, HS diventa Vertex Cover, sappiamo già essere NP-complete.
Commenti
- Cosa hai provato? Dove lhai ti blocchi? ' siamo lieti di aiutarti a capire i concetti, ma è improbabile che risolvendo gli esercizi per te ci riesca. Potresti trovare questa pagina è utile per migliorare la tua domanda.
Risposta
3SAT è ridotto a Colpire Imposta problema. Dato che 3SAT $ \ phi $ ha clausole $ m $ e $ n $ variabili, definire
$$ 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 \ in S \ text {e} (y_1 \ lor y_2 \ lo y_3) \ text {è una clausola.} $$ $$ S_x = \ {x, \ overline {x} \}, \ text {per tutti variabile} x. $$ $$ k = n $$
Supponendo che $ \ phi $ sia soddisfacente, allora cè unassegnazione di valore vero per $ n $ variabili. Quindi, aggiungi $ x $ a $ S “$ if $ x = true $, altrimenti aggiungi $ \ overline {x} $ a $ S” $.
Ora, supponiamo che il problema HS abbia una soluzione $ S “$. Allora poiché per ogni variabile $ x $, $ S” \ cap S_x \ neq \ emptyset $, $ S “$ ha almeno $ n $ letterali della forma $ x $ o $ \ overline {x} $ per ogni variabile $ x $. Inoltre, nessun $ x $ e $ \ overline {x} $ possono appartenere contemporaneamente a $ S “$ poiché la dimensione di $ S” $ è al massimo $ n $. Inoltre, per ogni clausola $ C_i $, $ S “\ cap S_i \ neq \ emptyset $ e quindi per ogni clausola selezioniamo $ y_i \ in S” \ cap S_i $ e impostiamo $ x = true $ if $ y_i = x $ e $ x = false $ if $ y_i = \ overline {x} $.
Commenti
- puoi mostrare unistanza positiva e una negativa?
Risposta
È facile mostrare che Hitting Set è in NP. Una soluzione deve solo mostrare linsieme H – si può facilmente verificare in tempo polinomiale se H è di dimensione k e interseca ciascuno degli insiemi B1, …., Bm.
Riduciamo dalla copertura del vertice. Considera unistanza del vertice problema di copertura – grafo G = (V, E) e un intero positivo k. Lo mappiamo a unistanza del problema del set di colpi come segue. Linsieme A è linsieme dei vertici V. Per ogni arco e ∈ E, abbiamo un insieme Se costituito dai due estremi di e. È facile vedere che un insieme di vertici S è una copertura di vertici di G se e solo se gli elementi corrispondenti formano un insieme di colpi nellistanza dellinsieme di colpi.
Commenti
- Benvenuto in ComputerScience @ SE. Uso interessante del simbolo speciale
∈– è comune usare MathJax, consentendo, ad esempio, la corretta scrittura: $ B_1, \ dots, B_m $. - e se la dimensione di Se è maggiore di 2? Funzionerà?
Risposta
Il problema del set di colpi è equivalente al problema del set di copertura, che è definito come segue:
INPUT: una raccolta C di sottoinsiemi di un insieme finito S.
SOLUZIONE: una copertura dellinsieme per S, cioè un sottoinsieme $ C “\ subseteq C $ tale che ogni elemento in S appartiene ad almeno un membro di $ C “$.
Dato $ k $ esiste un insieme cover $ C” $ tale che $ \ vert C “\ vert \ leq k $?
Questo sembra un compito a casa, quindi ti lascio capire come, data unistanza di Set Cover puoi convertirla in unistanza equivalente di Hitting Set.
Altrimenti, se vuoi seguire il suggerimento, prima mostri che Premendo Set in $ NP $, che è data una soluzione puoi verificarlo in tempo polinomiale.
Quindi, lo mostri dato un grafico $ G = (V, E) $, trovare una copertura di vertici di dimensione $ k $ è equivalente a trovare un insieme di percussioni di dimensione $ k $. Cioè, se $ | E | = m $, puoi costruire unistanza di set di successo con la stessa quantità di set.