# Parametrized reduction from 3-SAT to Independent Set to lower bound running time under ETH assumption

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:

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?

First, let me remark that $$n=O(m)$$ as in each clause only $$3$$ variables may appear, and that $$m=O(n^3)$$ without loss of generality as there can be at most $$(2n)^3$$ clauses up to repetition.
Your bound is not correct. Consider the case where some variable $$X$$ occurs positive in half the clauses and negative in the other half. This leads to roughly $$\frac{m^2}{4}$$ edges for $$X$$ alone. What is correct, however, is your suspicion that the parameter dependence is superlinear.
The reduction can be modified such that $$|V|=3m+2n$$ and $$|E|=6m+n$$. This would lead to a linear dependence of $$k_{IS}$$ on $$k_{3-SAT}$$. Consequently, with these parameterizations, independent set does not have a subexponential algorithm unless 3-SAT has.
• Thank you! Two questions: 1. You correctly pointed out that there is a case where my reduction leads to a quadratic number of edges. Wouldn't that mean that the bound I gave for the number of edges in $G$ is too low? 2. It follows from sparsification lemma that if ETH holds, $3$-SAT can also not be solved in $2^{o(m)} \cdot n^{O(1)}$ time. But this would not suffice to show the reduction either, correct? – MLStudent May 13 '19 at 23:16
• Ad question 2: With the interdependencies between $n$ and $m$ (that I added to the answer in the mean time) both your bound $2^{o(m)}\cdot n^{O(1)}$ and the bound $2^{o(m+n)}$ from the reduction become just $2^{o(m)}$. So you appear to be fine. – kne May 14 '19 at 12:12