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? 
Problems with Unknown Single Exponential Time Agorithms
exp time algorithms;hamiltonian paths