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&gt;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


Fedor V. Fomin, Pinar Heggernes, Dieter Kratsch:
Exact Algorithms for Graph Homomorphisms. Theory Comput. Syst. 41(2): 381-393 (2007)