רדוקציות

HAMPATH ≤p HAMCYCLE

רדוקציית מיפוי בזמן פולינומיאלי המראה שאם HAMCYCLE כריעה בזמן פולינומיאלי, אז גם HAMPATH. יחד עם הכיוון ההפוך, זה חלק מהאופן שבו ידוע ששתי הבעיות NP-שלמות.

שתי הבעיות

HAMPATH
מופע: גרף לא מכוון G ושני צמתים s, t.
שאלה: האם G מכיל מסלול המילטוני מ־s ל־t (מסלול המבקר בכל צומת בדיוק פעם אחת)?
HAMCYCLE
מופע: גרף לא מכוון G′.
שאלה: האם G′ מכיל מעגל המילטוני (מעגל המבקר בכל צומת בדיוק פעם אחת)?

הבנייה

בהינתן מופע HAMPATH ⟨G, s, t⟩, בנו מופע HAMCYCLE ‏G′ באופן הבא:

  1. קחו את כל הצמתים והקשתות של G.
  2. הוסיפו צומת חדש u (שאינו ב־G).
  3. הוסיפו בדיוק שתי קשתות: u–s ו־u–t.

הבנייה מוסיפה צומת אחד ושתי קשתות, כך שהיא רצה בזמן O(|V| + |E|) — פולינומיאלי בגודל של G.

המחשה

שלב 1 / 4מופע HAMPATH
sv₁v₂t

קלט ⟨G, s, t⟩. הקשתות העבות יוצרות מסלול המילטוני מ־s ל־t. קשתות מקווקוות הן קשתות אחרות של G שהמסלול אינו משתמש בהן.

נכונות

(⇒) אם ל־G יש מסלול המילטוני s → … → t, אז ב־G′ ניתן להאריך אותו דרך הצומת החדש: s → … → t → u → s. זה מבקר בכל צומת של G בדיוק פעם אחת, ובנוסף ב־u פעם אחת, וסוגר חזרה ל־s — מעגל המילטוני ב־G′.
(⇐) אם ל־G′ יש מעגל המילטוני, אז u חייב להופיע בו. השכנים היחידים של u ב־G′ הם s ו־t, כך שהמעגל משתמש בקשתות u–s ו־u–t. מחיקת u מהמעגל משאירה מסלול בין s ל־t המבקר בכל צומת אחר בדיוק פעם אחת — מסלול המילטוני מ־s ל־t ב־G.
לפיכך ⟨G, s, t⟩ ∈ HAMPATH אם ורק אם G′ ∈ HAMCYCLE, וההעתקה ⟨G, s, t⟩ ↦ G′ ניתנת לחישוב בזמן פולינומיאלי. ∎