Question

I want to prove that, assuming Exponential Time Hypothesis is true, there is no algorithm that solves Independent Set in $2^{o(|V|+|E|)}$ time. I want to apply the following strong parameterized many-one reduction $f$ from 3-Sat to Independent set. Let $\psi$ be the input to 3-SAT with parameter $\kappa_{3-SAT} = \#variables + \# clauses$ and let $(G=(V,E),k)$ be the input for Independent Set with parameter $\kappa_{IS} = |V| + |E|$

For every clause in the input formula $\psi$, add three vertices to the Graph, corresponding the the respective literals. Add an edge between two vertices if:

a) They correspond to literals in the same clause or

b) they correspond to a variable and its inverse

Then 3-Sat has a satisfying assignment if and only if the graph defined by this reduction has an independent set of size $m$, where $m$ is the number of clauses in $\psi$. For example: enter image description here

I am now wondering whether this reduction suffices to show that (assuming ETH), Independent Set cannot be solved in $2^{o(|V|+|E|)}$ time. If I understand correctly, the number of vertices $|V| = 3m$ and the number of edges $|E| \leq 3m+nm$, since for each clause, we have $3$ edges between the respective vertices and then for each variable we have at most $m$ edges between a variable and its inverse. However, this is not linear in $\kappa_{3-Sat}$ anymore.

Is my upper bound on the numer of edges wrong or do I a different reduction to show the desired result?

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top