Riduzione parametrizzata da 3-SAT a impostato indipendente a un tempo di esecuzione limitato inferiore in assunzione di ETH

Question

Voglio dimostrare che, supponendo che l'ipotesi del tempo esponenziale sia vera, non esiste un algoritmo che risolva l'insieme indipendente $ 2^{o (| v |+| e |)} $ volta. Voglio applicare la seguente forte riduzione parametrizzata $ f $ Da 3-Sat a set indipendente. Permettere $ psi $ essere l'input a 3-sat con parametro $ kappa_ {3-sat} = #variables + # clauss $ e lascia $ (G = (v, e), k) $ essere l'input per il set indipendente con il parametro $ kappa_ {is} = | v | + | E | $

Per ogni clausola nella formula di input $ psi $, Aggiungi tre vertici al grafico, corrispondenti ai rispettivi letterali. Aggiungi un bordo tra due vertici se:

a) corrispondono ai letterali nella stessa clausola o

b) corrispondono a una variabile e al suo inverso

Quindi 3-Sat ha un incarico soddisfacente se e solo se il grafico definito da questa riduzione ha un insieme indipendente di dimensioni $ m $, dove $ m $ è il numero di clausole in $ psi $. Per esempio:

Ora mi chiedo se questa riduzione è sufficiente per dimostrare che (supponendo ETH), il set indipendente non può essere risolto $ 2^{o (| v |+| e |)} $ volta. Se capisco correttamente, il numero di vertici $ | V | = 3m $ e il numero di bordi $ | E | leq 3m+nm $, poiché per ogni clausola, abbiamo $3$ bordi tra i rispettivi vertici e quindi per ogni variabile che abbiamo al massimo $ m $ bordi tra una variabile e il suo inverso. Tuttavia, questo non è lineare in $ kappa_ {3-sat} $ più.

Il mio limite superiore sul numero di bordi è sbagliato o ho una riduzione diversa per mostrare il risultato desiderato?