二部グラフ \(G = (L \cup R, E)\) の最小重み辺被覆として定式化することができます。 この問題を \(L \cup R \cup \lbrace S, T \rbrace\) を頂点集合とする最小費用流問題に帰着しましょう。

まず、\(E\) に対応するように \(L\) から \(R\) へ容量 \(1\)、重み \(C_i\) の辺を張ります。 この辺にフローが流れることは、この辺を被覆として選ぶことと対応しています。

次に、\(S\) から \(L\)、\(R\) から \(T\) に容量 \(\infty\)、重み \(0\) の辺を張ることを考えます。 \(S\) から \(T\) に流す時、辺被覆の条件は「\(S\) から出る辺、\(T\) に入る辺、のいずれも \(1\) 以上のフローが流れる」と表現されます。 したがって、容量下限付きで、流す量が自由な最小費用流問題の解法を適用することで、この問題を解くことができます。