UHC ≤p TSP | Complexity Atlas

הבנייה

אלגוריתם $R''$ . על קלט $G=(V,E)$ — גרף פשוט לא מכוון:

יהי $\hat G=(V,\hat E)$ הגרף המלא על $V$ .
הגדר $w:\hat E\to[0,\infty)$ על ידי $w(e)=\begin{cases}1 & e\in E\\ 2 & e\notin E\end{cases}$
החזר $\left(\hat G,\;w,\;|V|\right)$ .

למה דווקא מ- $UHC$ . אפשר היה לצאת גם ממסלול המילטוני — יש רדוקציות בין כל הגרסאות — אבל $TSP$ שואלת על מעגל בגרף לא מכוון, ולכן $UHC$ היא הבעיה הקרובה ביותר. אותו עיקרון חוזר: להתחיל מהבעיה הקרובה.

הערה על שלב 1. ברגע שנקבע $V$ , קיים גרף מלא יחיד עליו; אין כאן שום בחירה. בפועל שלב 1 פירושו "לכתוב את כל הקשתות", כולל אלה שלא היו ב- $G$ .

המחשה

קשת מקורית של G — עלות 1

נכונות — שני הכיוונים

UHC ∈ ⟹ TSP ∈

נניח $G\in UHC$ ; אז קיים ב- $G$ מעגל המילטוני $C$ . מכיוון ש- $E\subseteq\hat E$ , אותו $C$ עצמו הוא מעגל בגרף $\hat G$ , והוא המילטוני גם שם — קבוצת הקודקודים לא השתנתה, רק הוספנו קשתות.

מעגל המילטוני על $|V|$ קודקודים מכיל בדיוק $|V|$ קשתות, וכל אחת מהן היא קשת של $E$ ולכן משקלה $1$ . לכן $w(C)=|V|\cdot1=|V|\le|V| ,$ ומכאן $(\hat G,w,|V|)\in TSP$ .

TSP ∈ ⟹ UHC ∈

בהרצאה ניתנו שתי גרסאות של הכיוון השני, במכוון — כדי להראות שאין שום קדושה בשאלה אם מוכיחים "שייך $\Rightarrow$ שייך" או "לא שייך $\Rightarrow$ לא שייך". שתיהן נכונות.

גרסה א (בדרך השלילה). נניח $G\notin UHC$ , ויהי $C$ מעגל המילטוני כלשהו ב- $\hat G$ (כזה קיים, שהרי $\hat G$ מלא). ל- $C$ יש בדיוק $|V|$ קשתות ומשקל כל אחת לפחות $1$ . כמו כן ב- $C$ קיימת קשת שאינה ב- $E$ — אחרת כל קשתותיו היו ב- $E$ ו- $C$ היה מעגל המילטוני ב- $G$ , בסתירה להנחה. משקלה של אותה קשת הוא $2$ . לכן $w(C)\ge(|V|-1)\cdot1+2=|V|+1>|V| .$ זה נכון לכל מעגל המילטוני ב- $\hat G$ , ולכן אין מעגל במשקל $\le|V|$ , כלומר $(\hat G,w,|V|)\notin TSP$ .

גרסה ב (ישירה, ושתי שורות קצרה יותר). נניח $(\hat G,w,|V|)\in TSP$ ; אז קיים מעגל המילטוני $C$ ב- $\hat G$ עם $w(C)\le|V|$ . מכיוון שמשקל כל קשת הוא לפחות $1$ ול- $C$ יש בדיוק $|V|$ קשתות, מתקיים $w(C)\ge|V|$ . משתי אי-השוויונות $w(C)=|V|$ בדיוק. כעת $w(C)$ הוא סכום של $|V|$ מחוברים שכל אחד $\ge1$ וסכומם בדיוק $|V|$ ; אילו מחובר אחד היה $>1$ הסכום היה עולה על $|V|$ . לכן משקל כל אחת מ- $|V|$ הקשתות הוא בדיוק $1$ , ולפי הגדרת $w$ כל אחת מהן ב- $E$ . לכן $C$ הוא מעגל המילטוני ב- $G$ , כלומר $G\in UHC$ .

סיבוכיות הרדוקציה

זמןO(|V|²)

מקוםO(|V|²)

גודל הפלטO(|V|²)

זהו ניתוח שדורש זהירות. העבודה היא מעבר על כל קשתות $\hat E$ וכתיבת משקל לכל אחת, כלומר $\Theta(|\hat E|)$ . הפיתוי הוא לומר "זה ליניארי" — אבל ליניארי במה? זה ליניארי בגודל הגרף החדש, ואת זמן הריצה חייבים לחסום בגודל הקלט.

הבעיה: איננו יודעים כמה קשתות היו ב- $G$ ; תיאורטית ייתכן שהיו מעט מאוד, אפילו אפס. לכן אי אפשר לחסום את $|\hat E|$ באמצעות $|E|$ . מה שכן ידוע בוודאות הוא $|\hat E|=\binom{|V|}{2}\le|V|^2$ , ומספר הקודקודים אינו משתנה ברדוקציה וחסום בגודל הקלט. לכן זמן הריצה הוא $O(|V|^2)=O(|x|^2)$ — ריבועי בגודל הקלט.

מה זה קונה

$TSP$ היא NP-שלמה. ובונוס: משקלים בערכים $\{1,2\}$ מקיימים את אי-שוויון המשולש, שכן לכל $u,x,v$ מתקיים $w(u,v)\le2=1+1\le w(u,x)+w(x,v)$ . לכן אותה רדוקציה בדיוק מוכיחה ש- $TSP$ נשארת NP-קשה גם בגרסה המטרית — וזו הגרסה שעבורה קיים אלגוריתם קירוב (עץ פורש כפול, יחס $2$ ).

מלכודות

למה $\{1,2\}$ ולא $\{0,1\}$ . הבנייה הטבעית הראשונה שעלתה בכיתה הייתה משקל $0$ לקשתות המקוריות ו- $1$ לחדשות, עם $K=0$ . הבנייה הזאת נכונה לחלוטין והיא עובדת — אבל היא מפסידה את הבונוס: עם משקלי $0$ ו- $1$ אי-שוויון המשולש נשבר ( $1\not\le0+0$ ), ולכן היא אינה מוכיחה דבר על הגרסה המטרית.
"ליניארי" בגודל הפלט אינו "ליניארי" בגודל הקלט. זו הנקודה שהמרצה עמד עליה באריכות: אי אפשר לחסום את $|\hat E|$ באמצעות $|E|$ , כי ייתכן ש- $G$ היה כמעט ריק מקשתות. החסימה חייבת לעבור דרך $|V|$ .

השרשרת

נשענת על

DHP/DHC/UHC/UHP ≤p each other

משמשת בהמשך ל

UHC ≤p TSP-OPT

מאיפה זה נקרא

שיעור 12משפט 8: $UHC \le_p TSP$ , ולכן $TSP$ היא NP-hard
תרגיל מודרךhamiltonian-cycle-to-tsp
2026 '1 מועד 1אלגוריתם המחזיר גרף שלם עם משקלים $x$ לקשתות קיימות ו- $y$ לחסרות — איזו טענה על הרדוקציה נכונה.