# Slightly Superexponential Parameterized Problems

arXiv: https://arxiv.org/abs/1902.08723 · HTML: https://mlsanity.com/paper/1902.08723/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Feb 2019.

## Built on by (most cited first, 4 of 4)

- [Treewidth-aware Reductions of Normal ASP to SAT -- Is Normal ASP Harder than SAT after All?](https://mlsanity.com/paper/2210.03553/) (2022)
- [Solving Infinite-Domain CSPs Using the Patchwork Property](https://mlsanity.com/paper/2107.01428/) (2021)
- [Characterizing Structural Hardness of Logic Programs: What makes Cycles and Reachability Hard for Treewidth?](https://mlsanity.com/paper/2301.07472/) (2023)
- [Extended Version of: On the Structural Hardness of Answer Set Programming: Can Structure Efficiently Confine the Power of Disjunctions?](https://mlsanity.com/paper/2402.03539/) (2024)

## Abstract (arXiv)

A central problem in parameterized algorithms is to obtain algorithms with running time f(k)· nO(1) such that f is as slow growing function of the parameter k as possible. In particular, a large number of basic parameterized problems admit parameterized algorithms where f(k) is single-exponential, that is, ck for some constant c, which makes aiming for such a running time a natural goal for other problems as well. However there are still plenty of problems where the f(k) appearing in the best known running time is worse than single-exponential and it remained ``slightly superexponential'' even after serious attempts to bring it down. A natural question to ask is whether the f(k) appearing in the running time of the best-known algorithms is optimal for any of these problems. In this paper, we examine parameterized problems where f(k) is kO(k)=2O(klog k) in the best known running time and for a number of such problems, we show that the dependence on k in the running time cannot be improved to single exponential. (See paper for the longer abstract.)