I am reading the paper Slightly Superexponential Parameterized Problems at the moment and have two questions about it:

First question: The paper gives a proof of the following statement

Theorem 2.1: Assuming ETH, there is no $2^{o(klogk)}$ time algorithm for $k \times k$-Clique.

They prove this statement by sophisticated reduction from $3$-coloring. They then state that this construction runs in time polynomial in $k$. They state:

The graph $G$ has $k^2$ vertices and the time required to construct G is polynomial in $k$. [...] Therefore, the total running time is $2^{o(k \log(k)} \cdot k^{O(1)}$

Why is this not $2^{o(k \log(k)}) + k^{O(1)}$ instead? As far as I can see, we have only have to construct the graph once, and then we can run the presumed $2^{o(k \log(k)}$ algorithm.

Second question: From this theorem, it follows that $k \times k$-Clique can not have a $k^{o(k)}$ algorithm under the Exponential Time Hypothesis. This follows from the abstract, which states that $k^{O(k)} = 2^{O(k \log(k))}$. What is a good way to proof this statement?

  • $\begingroup$ Regarding your first question, it might be a typo. It doesn't make a huge difference anyway. $\endgroup$ – Yuval Filmus Aug 25 '19 at 21:12
  • 1
    $\begingroup$ Regarding the second question, try using $k^k = 2^{k\log k}$ (assuming the base of the logarithm is 2, which doesn't matter for something like $2^{o(k\log k)}$ or even $2^{O(k\log k)}$). $\endgroup$ – Yuval Filmus Aug 25 '19 at 21:12

Your Answer

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

Browse other questions tagged or ask your own question.