HALF Clique - NP Problema Complete

Question

Lasciatemi cominciare con l'osservare questo è un problema compiti a casa, si prega di fornire unico consiglio e le relative osservazioni, RISPOSTE NO DIRECT piacimento . Detto questo, qui è il problema che sto guardando:

Let MEZZA CLIQUE = {$ \ langle G \ rangle $ | $ G $ è un grafo non orientato avere una completa sottografo con almeno $ n / 2 $ nodi, dove n è il numero di nodi in $ G $ }. Mostrare che MEZZA CLIQUE è NP-completo.

Inoltre, so quanto segue:

• In termini di tale problema costituisce cricca , è definito come un sottografo non orientato del grafo di input, in cui ogni due nodi sono collegati da un bordo. A $ k $ -clique è una cricca che contiene $ k $ nodi.
• Secondo il nostro libro di testo, Michael Sipser di " Introduzione alla teoria della computazione ", pag 268, che il problema della cricca = {$ \ Langle G, k \ rangle $ | $ G $ è un grafo non orientato con un $ k $ -clique} è in NP
• Inoltre, secondo la stessa fonte (a pag 283) osserva che CLIQUE è in NP-Complpete (quindi anche ovviamente in NP).

Credo di avere il kernel di una risposta qui, però potrei usare qualche indicazione di ciò che è sbagliato con esso o eventuali punti correlate che potrebbero essere rilevanti per una risposta . Questa è l'idea generale che ho finora,

Ok, mi piacerebbe prima nota che un certificato sarebbe semplicemente un mezzo QLIQUE di $ \ text {size} \ geq n / 2 $. Ora sembra che quello che avrebbe bisogno di fare è quello di creare un verificatore che è una riduzione tempo polinomiale da Clique (che come sappiamo è NP-completo) per MEZZA CLIQUE. La mia idea sarebbe che questo sarebbe stato fatto con la creazione di una macchina di Turing che gestisce la macchina di Turing verificatore nel libro per CLIQUE con il vincolo aggiuntivo per Half-CLIQUE.

Questa suoni corretti per me, ma io in realtà non si fidano di me ancora in questo argomento. Ancora una volta, vorrei ricordare a tutti Questo è un problema LAVORO in modo cerca di evitare di rispondere alla domanda. Qualsiasi guida che è a corto di questo sarebbe il benvenuto!

Answer 1

A giudicare dalla descrizione e commenti, si potrebbe essere aiutato al meglio da una descrizione precisa di come le riduzioni possono essere utilizzate per dimostrare la NP-completo:

Un problema NP-completo se e solo se è in NP ed è NP-hard. Ciò significa che qualsiasi prova di NP-completo ha due parti: una prova che il problema sta nella NP e una prova che è NP-hard

.

Per la prima parte, si deve dimostrare che sì, le istanze possono essere verificati in tempo polinomiale utilizzando alcuni certificato adatto. In alternativa, è possibile mostrare il problema può essere risolto in tempo polinomiale da una macchina di Turing non deterministica, ma questo non è di solito fatto come gli errori sono fatti facilmente.

Nel vostro caso, questo si riduce a dimostrare che per ogni grafico con un $ n / 2 $ -clique, è possibile trovare qualche prova che c'è davvero una tale cricca, in modo tale che, armato di una tale prova, si può il check-in tempo polinomiale che esiste effettivamente una tale cricca.

Per la seconda parte, si deve dimostrare che il problema è NP-hard. Questo è in quasi tutti i casi mostrati dimostrando che il tuo problema è almeno altrettanto difficile come qualche altro problema NP-hard. Se MEZZA CLIQUE è almeno altrettanto difficile come CLIQUE, deve anche essere NP-hard.

A tale scopo, dimostrando una riduzione del DA CLIQUE, a MEZZA CLIQUE. Si 'ridurre' il problema, rendendo più 'facile'. Tu dici "Risoluzione CLIQUE è dura, ma ho dimostrato che solo è necessario risolvere MEZZA CLIQUE per risolvere CLIQUE". (Molte persone, anche gli esperti, dicono che a volte questo nel modo sbagliato:))

Ci sono diversi tipi di riduzioni: riduzione che è più comunemente usata è quella dove si mappa istanze di in questo caso CLIQUE alle istanze di Half-CLIQUE la cui dimensione è al massimo polinomialmente più grande, in un tempo polinomiale. Questo significa che se possiamo risolvere HALF-CLIQUE, allora possiamo anche risolvere CLIQUE concatenando l'algoritmo e la riduzione.

In altre parole, dobbiamo dimostrare che possiamo risolvere CLIQUE se siamo in grado di risolvere MEZZA CLIQUE. Facciamo questo dimostrando che per ogni istanza per Cricca, possiamo progettare un esempio di MEZZA CLIQUE in modo tale che l'istanza di CLIQUE è un 'sì' esempio se e solo se l'istanza di Half-CLIQUE è un 'sì' istanza.

La prova inizia quindi così: dato un grafo $ G = (V, E) $, posso creare qualche grafico $ H = (V 'E') $ tale che $ G $ contiene $ $ k - cricca se e solo se $ H $ contiene un $ n / 2 $ -clique. Lascio questa parte a voi (questa è la parte che richiede creatività, la parte che riguarda il problema specifico a portata di mano).

Answer 2

È sembrano un po 'perso. Si vuole dimostrare che MEZZA CLIQUE $ \ ge $ Cricca, il che significa che siete alla ricerca di un algoritmo di poli-tempo che prende le istanze cricca come le istanze di input e output MEZZA cricca con la proprietà che "sì" ingressi mappa a " sì "ES e "no" input mappano "no" s.

Quindi, in sostanza, il compito è quello di prendere un grafo $ G $ e un numero $ k $ e uscita un nuovo grafico $ H $ (e nessun numero) in modo che $ H $ ha una cricca su almeno metà della sua vertici ogniqualvolta $ G $ contiene una cricca di dimensione $ k $.

Lo spoiler di seguito contiene un suggerimento su come eseguire questa riduzione:

Prova a fare $ H $ allegando (in qualche modo) una cricca di dimensioni adeguate a $ G $, più un certo numero di vertici non collegato a nulla.

Answer 3

È possibile ridurre il problema della copertura dei vertici. Se il grafo complemento del grafico proposta ha una copertura dei vertici meno di n / 2 nodi allora questo grafico avrà una cricca di più di n / 2 nodi che sarà un mezzo cricca. Stato solo che è difficile da risolvere il problema Vertex coperchio in modo è questo.