יהא קלט עבור בעיית העץ של שטיינר הכללית, ללא הדרישה שהקלט מקיים את אי-שוויון המשולש: גרף שלם G=(V,E), חלוקה V=…

יהא קלט עבור בעיית העץ של שטיינר הכללית, ללא הדרישה שהקלט מקיים את אי-שוויון המשולש: גרף שלם $G=(V,E)$, חלוקה $V=R\cup S$ ופונקציית משקל $w:E\to\mathbb R^+$ על הקשתות. נגדיר $w':E\to\mathbb R^+$ כך שלכל קשת $e=\{u,v\}\in E$, הערך $w'(e)$ הוא המשקל המינימלי של מסלול ב-$G$ מ-$u$ ל-$v$ לפי פונקציית המשקל $w$.

1. הוכיחו כי $w'$ מקיימת את אי-שוויון המשולש.
2. יהא $T$ פתרון של בעיית העץ של שטיינר על הקלט $(G,w,R,S)$. הוכיחו כי $T$ הוא גם פתרון של בעיית העץ של שטיינר על הקלט $(G,w',R,S)$ ושמתקיים $$w'(T)\le w(T).$$
3. יהא $T'$ פתרון של בעיית העץ של שטיינר על הקלט $(G,w',R,S)$. הוכיחו כי קיים פתרון $T$ של בעיית העץ של שטיינר על הקלט $(G,w,R,S)$ שמקיים $$w(T)\le w'(T').$$
4. הסיקו כי משקל פתרון אופטימלי של בעיית העץ של שטיינר על הקלט $(G,w,R,S)$ שווה למשקל פתרון אופטימלי על הקלט $(G,w',R,S)$.
5. הוכיחו כי קיים אלגוריתם $2$-קירוב בזמן ריצה פולינומיאלי לבעיית העץ של שטיינר הכללית.