# Limits of variants of Independent Set?

Independent Set (IS) is the $\mathsf{NP}$-complete decision problem

Input: graph $G$ with $v=|V(G)|$, integer $k$
Question: is there an independent set $S \subseteq V(G)$ with at least $k$ vertices?

Similarly, we can define $f(v)$-bounded IS as the promise version of IS, where the promise is that $k \le f(v)$. Note that the function parameter depends only on the number of vertices in the input graph.

It is straightforward to show that when $f(v) = v/c$ for some constant $c$, then $f(v)$-bounded IS remains $\mathsf{NP}$-hard. This is because IS can be reduced to $f(v)$-bounded IS by blowing up the number of vertices by at most a factor of $c$. Similarly, when $f(v)=v^{1/c}$ for some constant $c$, then $f(v)$-bounded IS is also still $\mathsf{NP}$-hard, by blowing up the number of vertices by a power of $c$.

On the other hand, when $k$ is a constant, then $k$-bounded IS can be decided in polynomial time by exhaustively checking each of the $\binom{v}{k} = \Theta(v^k)$ different $k$-subsets, in at most $O(v^{k+2})$ steps.

This suggests that there is a spectrum of hardness defined via functions restricting the largest independent set that is sought in any instance. This is, in fact, the case: Bodirsky and Grohe 2008 (preprint) and Chen, Thurley, Weyer 2008 (preprint) established such results non-constructively via versions of Ladner's theorem, conditional on $\mathsf{P} \ne \mathsf{NP}$.

Keeping in mind that asymptotic behaviour does not induce a total order on functions,

what is a "smallest" function $f(v)$ such that $f(v)$-bounded IS is $\mathsf{NP}$-hard?

In particular, is there some function $f(v)=o(v^{1/c})$ for every constant $c>0$ for which bounded IS is hard? (I'd be happy with an argument that is conditional on a common hypothesis such as ETH or $W[1] \ne \mathsf{FPT}$.)

Note that while $f(v) = v^{1/\lg v} = 2$ yields a polynomial upper bound on time, the somewhat faster growing function $f(v)=v^{1/\lg\lg v}$ yields a bound for exhaustive search that is superpolynomial but subexponential. It would therefore also be interesting to establish whether there is a function $f(v) = \omega(1)$ such that $f(v)$-bounded IS is still in $\mathsf{P}$.

• I think if $f(v)$ bounded IS is NP-hard for $f(v) = v^{o(1)}$ then the ETH fails – daniello May 23 '17 at 21:17
• @daniello, I wasn't able to prove that $\sqrt{v}$-bounded IS is not NP-hard unless the ETH fails, although this was the original aim that led to this question. A slightly padded NP-hard problem may have a subexponential algorithm even in terms of its natural parameters, purely because of its inefficient representation. If my statement about NP-hardness of $\sqrt{v}$-bounded IS is right, then perhaps the structure of 3SAT can't be embedded inside $f(v)$-bounded IS without some kind of deformation in the reduction, that acts like padding? – András Salamon May 23 '17 at 23:14
• Closely related questions are discussed in Christos H. Papadimitriou, Mihalis Yannakakis: On Limited Nondeterminism and the Complexity of the V-C Dimension. J. Comput. Syst. Sci. 53(2): 161-170 (1996) – Gamow May 24 '17 at 7:25
• @AndrasSalamon what I mean is that if the NP-hardness reduction takes $n$-variable $3$-SAT instances to $f(v)$ bounded instances of size $n^c$ then brute forcing the output instances will take time $(n^c)^{f(n^c)}$. If $f(n) = n^{1/g(n)}$ with $g(n)$ tending to infinity with $n$ then 3-SAT gets solved in time $(n)^{c \cdot n^{c/g(n)}}$ which for sufficiently large $n$ is $O(n^{n^{1/2}})$ which is subexponential. – daniello May 24 '17 at 15:51
• @daniello so the bound $v^{1/c}$ yields an NP-hard problem, but $v^{o(1)}$ cannot (unless the ETH fails). I'm not sure this is enough to conclude there is no function that is $o(v^c)$ for all $c>0$, but seems close enough for an answer. – András Salamon May 24 '17 at 22:30

## 1 Answer

Question 1: For a function $f(n)$ lets say that $f$ is sub-polynomial if $\forall \epsilon > 0, f(n) = O(n^\epsilon)$. The Exponential Time Hypothesis (ETH) states that 3-SAT needs $2^{\epsilon n}$ time for some $\epsilon > 0$. Let's postulate a much weaker version, Weak Exponential Time Hypothesis'' (WETH): There exists an $\epsilon > 0$ such that $3$-SAT requires $2^{\epsilon n^\epsilon}$ time.

Claim: If $f$-bounded Independent Set is NP-hard for any sub-polynomial function $f$ then the WETH fails.

Proof: Supose $f$-bounded Independent Set is NP-hard under Turing-reductions for some any sub-polynomial function $f$. Then there exists a constant $c$ and an $O(n^c)$ time algorithm for $3$-SAT with $n$-variables that makes at most $O(n^c)$ oracle calls to $f$-bounded Independent Set with at most $O(n^c)$ vertices.

From this algorithm we make an algorithm for $3$-SAT where the oracle calls to $f$-bounded Independent Set are replaced by the $O(|V(G)|^{k+2})$ time brute force algorithm. The running time of this algorithm is upper bounded by $O((n^c) \cdot (n^c)^{f(n^c)+2}) = 2^{O(\log n \cdot f(n^c))}$. For any $\epsilon > 0$, pick $\delta = \epsilon / 2c$. Since $f$ is sub-polynomial we have that $f(n^c) = O((n^c)^\delta) = O(n^{\epsilon / 2})$. Therefore the running time of the algorithm is upper bounded by $2^{O(\log n \cdot n^{\epsilon / 2})} = 2^{O(n^{\epsilon})}$, contradicting the WETH.

Question 2: Let's say that $f$ computably tends to infinity if there exists a computable function $g : \mathbb{N} \rightarrow \mathbb{N}$ such that for every $c$ and every $n \geq g(c)$, $f(n) \geq c$.

Claim: If $f$-bounded Independent Set is in P for any function $f$ that computably tends to infinity, then FPT = W[1].

Proof: Assuming the existence of a polynomial time algorithm for $f$-bounded Independent Set we will give an FPT algorithm for Independent Set, proving FPT=W[1].

Given as input $G$ and $k$, set $n = |V(G)|$ and compute $g(k)$. Note that computing $g(k)$ takes time that is only a function of $k$. If $g(k) \leq n$ run the polynomial time algorithm for $f$-bounded Independent Set, this will output the correct answer because $k \leq f(n)$. If $g(k) > n$ then run the brute force $n^{k+2}$ algorithm, this takes time $g(k)^{k+2}$. In total the running time is bounded by $O(n^c + h(k))$ for some constant $c$ independent of $k$ and some function $h$.

Remark: Note that nothing here is specific to Independent Set. The first argument works for any problem with a $O(n^{k^c})$ time algorithm for some $c$, while the second argument works for any decidable problem.

• Nice exposition, thanks! Is there a name in the FPT community for the subclass of XP where the running time is $|x|^{\text{poly}(k)}$ as you suggest for the first argument, as a kind of polynomial version of XP? – András Salamon May 25 '17 at 15:31
• I don't remember this class having any name, but it's pretty natural so it might well be hidden away somewhere. – daniello May 25 '17 at 16:51
• Have asked a new question cstheory.stackexchange.com/q/38299 about the name for this class. – András Salamon May 25 '17 at 18:39
• The running time of an algorithm A that decides a problem P is always computable -- run A on all inputs of size $n$, count the number of steps, and output the maximum. For the same reason the running time of the algorithm that computes $g( k)$ is computable. – daniello May 25 '17 at 20:35