¿Podemos encontrar un ciclo Hamiltoniano en un gráfico denso con una complejidad mejor que O (n ^ 2)?

Dado un grafo denso (según el teorema de Ore, “denso” significa que la suma de los grados de cualquier par de nodos no adyacentes es al menos N, donde N es el número total de nodos), podemos encontrar un ciclo Hamiltoniano en dicho grafo utilizando el algoritmo de Palmer con una complejidad temporal de O(n^2). Mi pregunta es: ¿Podemos hacerlo mejor que esto? (en términos de complejidad temporal).