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

בשיעורים הגדרנו חתך בגרף לא מכוון. באופן דומה, נגדיר חתך בגרף מכוון כחלוקה של קודקודי הגרף לשתי קבוצות זרות $(S,\bar S)$.

במקרה של גרף מכוון, קבוצת החתך מוגדרת כך: קשת $(u,v)$ שייכת לקבוצת החתך אם ורק אם $u\in S$ וגם $v\in\bar S$; כלומר, הקשת מכוונת מ-$S$ ל-$\bar S$. גודל חתך הוא גודלה של קבוצת החתך שלו.

נגדיר את בעיית החתך המרבי עבור גרפים מכוונים:

קלט: $\langle G\rangle$, כאשר $G$ גרף מכוון.
פלט: חתך בגודל מקסימלי ב-$G$.

כתבו אלגוריתם קירוב לבעיה זו, הרץ בזמן פולינומי, בעל יחס קירוב

$$\alpha=\frac14.$$