רדוקציות

HAMCYCLE ≤p HAMPATH

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

שתי הבעיות

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

הבנייה

בהינתן מופע HAMCYCLE ‏G, בחרו צומת כלשהו v ∈ G ובנו מופע HAMPATH ⟨G′, s, t⟩ באופן הבא:

  1. קחו את כל הצמתים והקשתות של G.
  2. הוסיפו צומת חדש v′ שהשכנוּת שלו תואמת ל־v: עבור כל שכן u של v ב־G, הוסיפו קשת u–v′ ב־G′.
  3. הוסיפו שני צמתים חדשים נוספים s ו־t.
  4. הוסיפו קשתות s–v ו־v′–t. (s שכן רק ל־v; t שכן רק ל־v′.)

הבנייה מוסיפה שלושה צמתים ולכל היותר deg(v) + 2 קשתות — פולינומיאלי בגודל של G.

המחשה

שלב 1 / 4מופע HAMCYCLE
vabc

קלט: גרף G. הקשתות העבות יוצרות מעגל המילטוני v → a → b → c → v. בחרו צומת כלשהו של G — כאן בחרנו ב־v.

נכונות

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