4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I think if $f(v)$ bounded IS is NP-hard for $f(v) = v^{o(1)}$ then the ETH fails $\endgroup$ – daniello May 23 '17 at 21:17
  • $\begingroup$ @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? $\endgroup$ – András Salamon May 23 '17 at 23:14
  • $\begingroup$ 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) $\endgroup$ – Gamow May 24 '17 at 7:25
  • 1
    $\begingroup$ @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. $\endgroup$ – daniello May 24 '17 at 15:51
  • $\begingroup$ @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. $\endgroup$ – András Salamon May 24 '17 at 22:30
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – András Salamon May 25 '17 at 15:31
  • $\begingroup$ I don't remember this class having any name, but it's pretty natural so it might well be hidden away somewhere. $\endgroup$ – daniello May 25 '17 at 16:51
  • $\begingroup$ Have asked a new question cstheory.stackexchange.com/q/38299 about the name for this class. $\endgroup$ – András Salamon May 25 '17 at 18:39
  • 1
    $\begingroup$ 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. $\endgroup$ – daniello May 25 '17 at 20:35

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.