存在の複雑さ：重み付けされたサイクル

Question

重み付けされたグラフGを仮定し、頂点と辺に重みを付け、定数kを与え、決定問題Aの複雑さは？

1-A：総重量Kを有する用量Gの連続サイクル。
2 Gが平面グラフである場合、Aの複雑さは何ですか？

どのようなアイデアや論文や書籍を指しても大丈夫です！

Answer 1

ユニットウェイトとk = nの平面Hamiltonian cycleから減らすことができるのでNP完成です。