Limits of variants of Independent Set?

Question

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}$.

Answer 1

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.