There are studies about approximation algorithms for NP complete problems in Polynomial time and exact algorithms in exponential time. Are there studies about approximation algorithms for NP complete problems in subexponential time of form $2^{n^{\delta_2}}$ where $\delta_2\in(0,1)$?

I am particularly interested in what is known about hard to polynomial time approximable problems such as Independence number and Clique number in subexponential time? Note that ETH only prohibits exact computation in such a time frame. Say Independence number is $\alpha(G)=2^{r(n)n}$ on a graph with vertex count $|V|=2^{s(n)n}$ for some $0<r(n)<s(n)$. Is an $2^{(r(n)n)^{\delta_1}}$-factor approximation scheme possible for Independence number in time $2^{|V|^{\delta_2}}=2^{2^{\delta_2s(n) n}}$ where $0<\delta_1<1$ and $0<\delta_2<1$ are some fixed positive reals?

That is for every $\delta_1\in(0,1)$ is there a $\delta_2\in (0,1)$ such that $\alpha(G)$ can be approximated within $2^{\log_2^{\delta_1}(\alpha(G))}=2^{(r(n)n)^{\delta_1}}$ factor in time $2^{|V|^{\delta_2}}=2^{2^{\delta_2s(n) n}}$?

  • $\begingroup$ did you actually mean to ask for running time sublinear in the independent number? $\endgroup$ – Sasho Nikolov Nov 4 '13 at 2:49
  • $\begingroup$ No, running time is sub-exponential. Fully exponential would be $2^{|V|}$. Here running time is of form $2^{|V|^{\delta_1}}$ and here $\alpha(G)=2^{r(n)n}=|V|^{\frac{r(n)}{s(n)}}<|V|=2^{s(n)n}$. $\endgroup$ – 1.. Nov 4 '13 at 5:18
  • $\begingroup$ It should be $\delta_2$ in previous comment and we have $\alpha(G)<|V|<2^{|V|^{\delta_2}}<2^{|V|}$. $\endgroup$ – 1.. Nov 4 '13 at 5:26
  • $\begingroup$ I think I had typos before. $\endgroup$ – 1.. Nov 4 '13 at 5:41
  • $\begingroup$ Is it Clear now? $\endgroup$ – 1.. Nov 4 '13 at 5:41

One paper that gives an answer to this question is Chalermsook, Laekhanukit, & Nanongkai (2013).

There are also related works in the context of Fixed Parameter Tractability such as Hajiaghayi, Khandekar, & Kortsarz (2013) and Chitnis, Hajiaghayi, Kortsarz (2013). These hardness results are proven under various assumptions such as ETH or existence of very strong PCPs.

  • 1
    $\begingroup$ arxiv.org/pdf/1308.2617v2.pdf says "For any $r$ larger than some constant, any $r$-approximation algorithm for the maximum independent set problem must run in at least $2^{{n^{1-\epsilon}}/{r^{1+\epsilon}}}$ time. This nearly matches the upper bound of $2^{n/r}$". So approximation ratio $r=2^{({s(n)n})^{\delta_1}}$ can be achieved in $2^{2^{r(n)n - ({s(n)n})^{\delta_1}}} = 2^{2^{1 - \frac{({s(n)n})^{\delta_1}}{r(n)n}r(n)n}}=2^{2^{\delta_2 r(n)n}}$ time for some $\delta_2 >1 - \frac{({s(n)})^{\delta_1}{n}^{\delta_1-1}}{r(n)}$? $\endgroup$ – 1.. Nov 4 '13 at 0:14

You have many $FPA$ (fixed parameter approximation) algorithms for which a sublinear parameter translates into subexponential time in the length of the input.

For example, approximating the number of simple paths of length $k$, for some $k=n^c$ (where $c<1$), gives you a running time of:

$O((2e)^{n^c}\cdot 2^{polylog(n)})$.


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.