Две проблемы совершенно разные. Представьте, что минимальное связующее дерево - это проблема соединения мест, где вам нужно заплатить только один раз, чтобы построить дорогу, но вы можете использовать ее столько раз, сколько захотите. Легко придумать самую дешевую конфигурацию дорог (например, по алгоритму Крускала), которая позволяет вам путешествовать из любого места в любое другое.
Гамильтонов цикл, с другой стороны, требует, чтобы вы минимизировали фактическое расстояние перемещения, то есть каждое перемещение из одного места в другое считается. (Он также просит вас никогда не посещать место дважды, но это незначительная деталь.) Эта проблема принципиально нелокальна, в том смысле, что вы не можете определить, правильно ли вы поступаете, просто локально исследуя варианты следующий шаг. Для сравнения, алгоритм жадного MST гарантированно выберет правильное следующее ребро для добавления к дереву на каждом шаге.
Кстати, никто не говорит, что «у нас не может быть эффективных алгоритмов для HP». Возможно, мы просто еще не нашли: -)