# 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?

## 3 Answers

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 – ivmihajlin 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. – Serge Gaspers Mar 16 '16 at 4:25

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].