Время полного обхода графа

На интервью попался интересный вопрос.

Точная формулировка:

Существует ли алгоритм не выше O(N^k), где k - некоторое натуральное число (константа), получающий на вход произвольный связный граф с N вершинами (одну из них назовем особой) и строящий маршрут минимальной длинны, который начинается и заканчивается в особой вершине и включает все остальные вершины ровно по одному разу? Если да, то можете ли вы указать k?

Возможности задавать уточняющие вопросы у меня не было, так что это все что есть.

Есть подозрение что такого алгоритма вообще нет, так как если граф произвольный, то не факт что возможность обойти его полностью пройдя по каждой вершине только 1 раз вообще существует.

Я на вопрос ответить не смог, но правильный ответ меня все же интересует. Есть идеи?