עבור U V בגרף מכוון G=(V,E), החתך המושרה על ידי U, המסומן (U), הוא קבוצת הקשתות היוצאות מ-U: זנבן ב-U וראשן ב-…

עבור $U\subseteq V$ בגרף מכוון $G=(V,E)$, החתך המושרה על ידי $U$, המסומן $\delta(U)$, הוא קבוצת הקשתות היוצאות מ-$U$: זנבן ב-$U$ וראשן ב-$\bar U$. בגרף מכוון $\delta(U)$ ו-$\delta(\bar U)$ אינם בהכרח שווים.

קלט: גרף פשוט מכוון $G=(V,E)$.
מטרה: למצוא $U\subseteq V$ שעבורה $|\delta(U)|$ מקסימלי.

הוכיחו שקיים אלגוריתם פולינומי בעל יחס קירוב $1/4$.