13
$\begingroup$

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.

$\endgroup$

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.