Многогранники в задаче коммивояжера

Каждому ребру полного графа на $n$ вершинах присвоено число, называемое расстоянием; требуется найти гамильтонов цикл наибольшей длины. Эта задача является $NP$-трудной. Однако известны способы задания расстояний такие, что задача коммивояжера становится разрешимой за полиномиальное по $n$ время. Существует ли простая шкала, позволяющая оценить меру трудности входных данных?
Предлагается классификация входных данных, основанная на изучении комбинаторной структуры многогранников, инвариантных относительно симметрической группы $S_n$. Возникающие на этом пути классы находятся во взаимно однозначном соответствии с разбиениями числа $n$ на нечетные части, в которых часть, равная единице, имеет четную кратность. Обсуждается связь между такими разбиениями и оптимальными гамильтоновыми циклами.