漢米頓路徑問題（Hamiltonian path problem）

想像規劃一趟觀光散步，要把城市裡每個地標都「恰好」造訪一次，不重複也不遺漏，且只能走真實存在的街道。漢米頓路徑正是這樣一條穿越圖的路線：它把每個頂點都恰好碰一次。若這條路線還回到起點，就是漢米頓迴路。「這樣的路線存在嗎？」這問題看似無邪，卻是工具箱裡最難的之一。

形式上，給定一張圖 G，漢米頓路徑是一條恰好造訪每個頂點一次的路徑；漢米頓迴路則額外閉合回到起點。判定問題問 G 是否含有這樣一條。它屬於 NP：證書是頂點的一個排序，驗證器在多項式時間內檢查這份清單是所有頂點的一個排列、且每相鄰一對都有邊相連。當心一個著名的近親：歐拉路徑，它把每條「邊」走一次，很容易（只要檢查度數即可），但漢米頓路徑把每個「頂點」造訪一次，卻是 NP 完全。表面的相似掩蓋了難度上的鴻溝。

漢米頓性是 NP 完全，從 3-SAT 經由這領域最巧妙的小元件歸約之一抵達，它用可往兩個方向走過的變數小元件（編碼真／假），接線到強制每個子句被滿足的子句小元件。從漢米頓迴路問題到旅行推銷員判定問題只有一小步：給既有的邊權重 1、其餘邊很大的權重，則總權重為 n 的路線存在，恰恰當漢米頓迴路存在時。這就是為何漢米頓性是圖問題與路由問題之間歸約地圖上的標準中繼點。