Построение кратчайшего вершинно непересекающегося пути, проходящего через обязательные вершины

[wataru]

Я почти ничего не понял. Есть несколько вопросов/комментариев.

Могли бы вы описать, что конкретно вы сделали? Нашли полиномиальное приближенное решение? Придумали эвристику, ускоряющую перебор?

Стоит в начале указать, почему задача NP-трудна. Вы во введении обещаете рассмотреть этот вопрос, но забываете о нем. Например, надо какую-нибудь известную задачу свести к этой.

Потом вы какую-то рыбу вводитите и тут я нить повествования потерял. Что вы вкладываете в термин "релаксация"?