בעיית המסלול הארוך ביותר

בתורת הגרפים, בעיית המסלול הארוך ביותר היא בעיה המתייחסת לגרף נתון ועניינה מציאת המסלול הפשוט (שאינו חוזר לאותו צומת פעמיים), שאורכו מרבי מבחינת מספר הקשתות בו או מבחינת סכום משקלי הקשתות (במקרה של גרף משוקלל).

בעיית המסלול הארוך היא בעיה NP-קשה; לא ידוע אלגוריתם יעיל (אלגוריתם עם זמן ריצה פולינומי) שפותר את בעיית המסלול הארוך ביותר, ומציאת אלגוריתם כזה תוכיח ש-P=NP (ולכן הסברה היא שאלגוריתם כזה לא קיים). בעיית ההכרעה המתאימה: השאלה האם קיים מסלול פשוט בגרף ארוך יותר ממספר מסוים היא בעיה NP שלמה.

מבוא בלתי פורמלי

כמו מושגים רבים אחרים במתמטיקה, גרף הוא מושג מופשט, המוגדר באופן פורמלי, ואשר עשוי לייצג מערכות ראליות מן המציאות החומרית (כגון, כבישים, רשתות מחשבים, רשתות חברתיות, ועוד) ובעצם כך לשמש לפתרון בעיות מעשיות.

כהגדרה פשטנית, גרף הוא אוסף של צמתים או מקומות נקודתיים (הנקראים גם קדקודים), המחוברים ביניהם באמצעות "ענפים" הנקראים צלעות או קשתות. החיבור בין כל שני צמתים עשוי להיעשות על ידי קשתות שונות, בעלות משקל או אורך שונה, וגרף עשוי להיבדל ממשנהו רק בקשתות המחברות את הצמתים בו. חיבור כל הקשתות בגרף נתון נקרא מסלול.

גרף נקרא פשוט אם ניתן לחבר את כל הקשתות בו למסלול העובר בכל קדקוד פעם אחת בלבד.

מציאת המסלול הקצר ביותר המחבר בין כל קדקודי הגרף, כמו גם המסלול הארוך ביותר, אינה אפשרית תמיד ותלויה בסוג הגרף.

ידוע כי ניתן למצוא את המסלול הקצר ביותר באופן יעיל (בזמן ריצה פולינומי). לעומת זאת, מציאת המסלול הארוך ביותר, היא בעיה NP קשה - שאפשרות פתרונה בסיבוכיות זמן פולינומית מוטלת בספק ושמציאת פתרון יעיל עבורה משמעה פתרון יעיל עבור כל בעיות מחלקת NP.

רדוקציה של הבעיה

נראה כי בעיית המסלול הארוך ביותר היא בעיית NP קשה (קשה לפתרון מבחינה חישובית לפחות כמו כל בעיה השייכת ל-NP), על ידי רדוקציה פולינומית של הבעיה (המרה אלגוריתמית בסיבוכיות פולינומית) לבעיית מציאת המסלול ההמילטוני שהיא בעיה NP שלמה.

א. נציג טרנספורמציה שתיקח כל מופע של הבעיה המוכרת, ותהפוך אותו למופע של הבעיה החדשה. הטרנספורמציה הרדוקציה היא זו: ניקח את הגרף, נסמן ב-V את מספר הקדקודים בו, ונגדיר שמשקל כל צלע בו שווה ל-1; כעת נשאל האם משקל המסלול הארוך ביותר שווה למספר הקדקודים בגרף V.

ב. נוכיח כי תשובה חיובית לבעיה החדשה שקולה (כלומר: נכונה אם ורק אם) לתשובה חיובית גם לבעיה המוכרת:

• אם יש בגרף הנתון מסלול המילטוני, אזי יש מסלול שעובר בכל הקדקודים בגרף פעם אחת בדיוק. כלומר, למסלול יש V קדקודים וצלעות. כיוון שמשקל כל צלע הוא 1, אז משקל המסלול הוא V, ולכן התשובה חיובית גם לבעיה החדשה.
• אם יש בגרף מסלול באורך V, הרי שהמסלול עובר ב V קדקודים; אבל V הוא מספר הקדקודים בגרף, ולכן יש גם מסלול המילטוני.

ג. מכיוון שלא משנים את הגרף, אלא רק סופרים את מספר הקדקודים בו, הרי שזמן הספירה הדרוש כדי לעבור את כל הקדקודים יהיה לכל היותר V. לכן, הטרנספורמציה ניתנת לביצוע בזמן ליניארי והרדוקציה היא אכן פולינומית.