The connection between $c^kn^{O(1)}$ for $c<4$ and exact exponential-time algorithms beating brute-force $O(2^n)$ algorithms has been known for a long time. However, when $c\geq 4,$ there are not many known results. Fomin et al. [1] showed a technique to handle this case, can improved a lot of exact exponential-time algorithms. For example, for the Interval Vertex Deletion Problem, the fastest previously known exponential-time algorithm is $O((2-\epsilon)^n)$ for $\epsilon <10^{-20}$ [2]. The fastest parameterized algorithm is $8^kn^{O(1)}$ [3]. Combined them together, Fomin et al. [1] got a $1.875^{n+o(n)}$ time algorithm.

Do you known any other techniques and known results to improve the exact exponential-time algorithms using parameterized algorithms when $c\geq 4$?

[1] Fomin, Fedor V., et al. "Exact algorithms via monotone local search." arXiv preprint arXiv:1512.01621 (2015).

[2] Bliznets, Ivan, et al. "Largest chordal and interval subgraphs faster than 2 n." European Symposium on Algorithms. Springer Berlin Heidelberg, 2013.

[3] Cao, Yixin. "Linear recognition of almost interval graphs." Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 2016.


Your Answer

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