Problems with Unknown Single Exponential Time Agorithms

I'm looking for examples of problems for which it is easy to get algorithms running in time $2^{O(n\log n)}$, or $2^{O(n^c)}$ for some $c>1$ but for which it is not known whether there is an algorithm running in time $2^{O(n)}$.

I'm mostly interested on graph theoretic problems, but other nice examples would also be welcome.

For instance, it is trivial to develop an algorithm running in time $O(n!) = 2^{O(n\log n)}$ for the Hamiltonian path problem. Just test all permutations. Using dynamic programming however, one can achieve time $2^{O(n)}$. Are there other natural connectivity problems, or variations of the Hamiltonian path problem for which no algorithm running in time $2^{O(n)}$ is known?

In the Graph Homomorphism problem, the input is two graphs $G$ and $H$ and the question is whether there is a mapping $h$ from the vertices of $G$ to the vertices of $H$ such that for every edge $uv\in E(G)$ we have that $h(u) h(v)\in E(H)$.

The problem can be solved in time $O^*(|V(H)|^{|V(G)})$ by a brute-force algorithm (the $O^*$-notation hides factors polynomial in the input size).

However it is open whether it can be solved in time $O^*(c^{|V(H)|+|V(G)|})$, and this appears as an open question in

• In fact, assuming Exponential Time Hypothesis, one can prove that there is no $O^*(c^{|V(H)|+|V(G)|})$ time algorithm: Tight Lower Bounds on Graph Embedding Problems Mar 15 '16 at 17:25
• Thanks for the pointer! The last section of that paper also contains more concrete embedding problems for which it is not clear whether single-exponential time algorithms can be obtained. Mar 16 '16 at 4:25

Update 28 Sep 2020: This has been resolved by Wiebking in SODA '20, where he gave a $$2^{O(n)}$$-time algorithm, with no remaining dependence on $$|G|$$. (I'll leave up the rest of the answer for historical purposes.)

Permutational Isomorphism of Permutation Groups, aka Permutation Group Conjugacy:

Input: Two lists of permutations in $$S_n$$, say $$(\pi_1, \dotsc, \pi_k)$$ and $$(\rho_1, \dotsc, \rho_\ell)$$

Output: A permutation $$\pi \in S_n$$ such that $$\pi^{-1} \langle \pi_1, \dotsc, \pi_k \rangle \pi = \langle \rho_1, \dotsc, \rho_\ell \rangle$$, or "NOT ISOMORPHIC"

(where $$\langle \pi_1, \dotsc, \pi_k \rangle$$ means the subgroup generated by the $$\pi_i$$).

As with the Hamiltonian path example, there is a trivial $$n! = 2^{O(n \log n)}$$ algorithm. The best currently known is $$2^{O(n)} |G|^{O(1)}$$ where $$G = \langle \pi_1, \dotsc, \pi_k \rangle$$. Note that $$|G|$$ can be as large as $$n!$$ (trivially: $$G = S_n$$) or even $$n! / n^{O(1)}$$ for nontrivial $$G$$ (see, e.g., the O'Nan-Scott Theorem).* Removing the dependence on $$|G|$$ was left there as an important open problem.

* - Despite the fact that $$G$$ can be large, so in the worst case this appears to be asymptotically no better than trivial, it turns out that $$2^{O(n)}|G|^{O(1)}$$ was exactly what was needed for the polynomial-time isomorphism test of groups with no Abelian normal subgroups.

Computing the crossing number of a graph. Existing exact algorithms involve formulating it as an integer linear program with a number of variables cubic in the number of edges [Chimani et al, ESA 2008]. Even for the restricted one-page crossing number, in which the vertices are placed on the boundary of a disk and the edges interior to the disk, known algorithms are exponential in $O(n\log n)$ rather than singly-exponential [Bannister et al, GD 2013].

Tensor Isomorphism. The best-known algorithm for 3-Tensor Isomorphism over $$\mathbb{F}_q$$ takes time $$q^{\Theta(n^2)}$$, and over $$\mathbb{R}$$ or $$\mathbb{C}$$ takes times $$2^{\Theta(n^2)}$$. (The same is true for $$d$$-Tensor Isomorphism for $$d \geq 3$$, where a factor of $$d-2$$ is hidden in the $$\Theta(\cdot)$$ in the exponent. But the $$d=3$$ case is already TI-complete.) In the first case: brute force over $$GL_n(\mathbb{F}_q)$$, which has size roughly $$q^{n^2}$$, and in the second case using quantifier elimination to find the $$n^2$$ unknowns of an element of $$GL_n(\mathbb{R})$$, which takes time simply-exponential in the number of unknowns.

Solving TI over $$\mathbb{F}_p$$ in time $$p^{\Theta(n)}$$ instead would put isomorphism of for some of the hardest cases of Group Isomorphism into $$\mathsf{P}$$ (namely, $$p$$-groups of exponent $$p$$ and nilpotency class $$2$$). The reductions between these problems imply that getting time $$p^{\Theta(n^c)}$$ for TI corresponds to solving isomorphism for this class of groups in time $$|G|^{\Theta((\log |G|)^{c-1})}$$, and the current record for Group Iso for this class of groups stands at $$c=2$$, which is the same as the best for general GroupIso.

I don't know direct surprising/difficult consequences of solving in $$2^{\Theta(n)}$$ time over $$\mathbb{R}$$ or $$\mathbb{C}$$, except that doing so would be seen as a significant step towards getting $$q^{\Theta(n)}$$-time over finite fields.

This same issue arises in many other $$\mathsf{TI}$$-complete problems.

The problem of testing whether a given integer linear program $$L$$ with $$n$$ variables has a feasible solution can be solved using $$n^{2.5n+o(n)}\cdot |L|$$ arithmetic operations. It is a major open problem in combinatorial optimization and parameterized algorithms whether this can be improved to a running time of $$2^{O(n)}\cdot |L|^{O(1)}$$.

It can be easily seen that a running time of $$(2-\epsilon)^n \cdot |L|^{O(1)}$$ would imply that the Strong Exponential Time Hypothesis (SETH) is false. I am not aware of any better conditional lower bounds for the problem.

In a recent paper by Fomin et al. (Computation of Hadwiger Number and Related Contraction Problems: Tight Lower Bounds) it is shown that computing the Hadwiger number of a graph has the complexity profile this question is looking for. Namely, the problem can be solved in $$n^{O(n)}$$ fairly easily, but cannot be solved in $$n^{o(n)}$$ unless the ETH is false. The Hadwiger number of a graph $$G$$ is the size of the largest clique minor contained in $$G$$.