Réduction paramétrée de 3-SAT à l'ensemble indépendant à un temps d'exécution de borne inférieure en vertu de l'hypothèse d'ETH

Question

Je veux prouver que, en supposant que l'hypothèse de temps exponentielle est vraie, il n'y a pas d'algorithme qui résout un ensemble indépendant 2 $ ^ {o (| v | + | e |)} $ temps. Je veux appliquer la forte réduction paramétrée suivante $ f $ De 3-SAT à l'ensemble indépendant. Laisser $ psi $ être l'entrée de 3-SAT avec le paramètre $ kappa_ {3-sat} = #variables + # clauses $ et laisser $ (G = (v, e), k) $ être l'entrée pour l'ensemble indépendant avec paramètre $ kappa_ {is} = | v | + | E | $

Pour chaque clause de la formule d'entrée $ psi $, ajoutez trois sommets au graphique, correspondant aux littéraux respectifs. Ajoutez un bord entre deux sommets si:

a) Ils correspondent aux littéraux dans la même clause ou

b) Ils correspondent à une variable et à son inverse

Alors 3-SAT a une affectation satisfaisante si et seulement si le graphique défini par cette réduction a un ensemble indépendant de taille $ m $, où $ m $ est le nombre de clauses dans $ psi $. Par exemple:

Je me demande maintenant si cette réduction suffit pour montrer que (en supposant que ETH), l'ensemble indépendant ne peut pas être résolu dans 2 $ ^ {o (| v | + | e |)} $ temps. Si je comprends correctement, le nombre de sommets $ | V | = 3m $ et le nombre d'arêtes $ | E | leq 3m + nm $, depuis pour chaque clause, nous avons $3$ bords entre les sommets respectifs, puis pour chaque variable, nous avons au plus $ m $ bords entre une variable et son inverse. Cependant, ce n'est pas linéaire dans $ kappa_ {3-sat} $ plus.

Ma limite supérieure sur le nombre des bords est-elle erronée ou est-ce que je suis une réduction différente pour montrer le résultat souhaité?