Gọi ~w(x,y)~ là độ dài cạnh từ x đến y.

Ta duyệt để cố định ~\frac{k}{2}-1~ đỉnh ở vị trí lẻ (đỉnh còn lại là ~1~).

Với mỗi cặp đỉnh lẻ cạnh nhau ~x~, ~y~, tìm ~k-2~ đỉnh ~u~ thỏa mãn ~w(x,u) + w(u,y)~ ngắn nhất. Loại bỏ các đỉnh thuộc tập đỉnh lẻ, ta còn ít nhất ~\frac{k}{2}~ đỉnh. Sau đó ta giữ lại đúng ~\frac{k}{2}~ đỉnh có ~w(x,u) + w(u,y)~ ngắn nhất. Cuối cùng, ta duyệt để tìm ra tập ~\frac{k}{2}~ đỉnh tại các vị trí lẻ.

Độ phức tạp: ~O(n^k)~, ~T(n^{\frac{k}{2}-1}*\frac{k}{2}^{\frac{k}{2}})~