結果的に巡回セールスマン問題になって、NPであることを言えるように思うが。
NP問題に多項式時間解が存在するかどうかは、オレは知らん。