4
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

However, there appears to be a further problem: The ETH uses a different parameterization. Namely just the number of variables, disregarding the number of clauses. I am not an expert in ETH. Possibly the sparsification lemma can help here.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – MLStudent May 13 at 23:16
  • $\begingroup$ Ad Question 1: You are right, I was sloppy and did not check your bound in detail. I only verified that there is no linear bound. Fixed now. $\endgroup$ – kne May 14 at 11:26
  • $\begingroup$ 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. $\endgroup$ – kne May 14 at 12:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.